본문 바로가기

Algorithm/Tree

 (7)
EDITOR WARS #include #include #include #include using namespace std; struct NaiveDisjointSet { vector parent; NaiveDisjointSet(int n) : parent(n) { for (int i = 0; i < n; i++) parent[i] = i; } int find(int u) const { if (u == parent[u]) return u; return find(parent[u]); } void merge(int u, int v) { u = find(u); v = find(v); if (u == v) return; parent[u] = v; } }; struct OptimizedDisjointSet { vector parent,..
MEASURETIME (FENWICK TREE) #include #include using namespace std; struct FenwickTree { vector tree; FenwickTree(int n) : tree(n + 1) {} int sum(int pos) { ++pos; int ret = 0; while (pos > 0) { ret += tree[pos]; pos &= (pos - 1); } return ret; } void add(int pos, int val) { ++pos; while (pos > cn;..
MORDOR #include #include #include using namespace std; const int int_max = numeric_limits::max(); typedef struct DifficultyNode { int min, max; DifficultyNode() { min = int_max; max = 0; } DifficultyNode(int _min, int _max) : min(_min), max(_max) {} } DifficultyNode; typedef struct DifficultyQuery { vector querySource; int n; DifficultyQuery(vector &array){ n = array.size(); querySource.resize(n * 4); ..
RUNNINGMEDIAN #include #include #include using namespace std; typedef int KeyType; // 이 함수들은 문제 풀 때 쓰이진 않지만 (C++ STL 의 priority_queue를 대신 사용) // 기왕 구현했으니 넣어둠 void push_heap(vector &heap, KeyType key); void pop_heap(vector &heap); void swap(int *a, int *b); typedef struct Rng { int seed, a, b; Rng(int _a, int _b) : a(_a), b(_b) { seed = 1983; } int next() { int prevSeed = seed; seed = (seed * (long long)a + b)..
TREAP_INSERTION #include #include using namespace std; typedef int KeyType; typedef struct Node { KeyType key; int priority, size; Node *left, *right; Node(const KeyType& _key) : key(_key), priority(rand()), size(1), left(nullptr), right(nullptr) {} void setLeft(Node* newLeft) { left = newLeft; calcSize(); } void setRight(Node* newRight) { right = newRight; calcSize(); } void calcSize() { size = 1; if (left) si..
FORTRESS #include #include #include using namespace std; typedef struct Node { int x, y, r; int idx; vector childs; Node(int _x, int _y, int _r, int _idx) : x(_x), y(_y), r(_r), idx(_idx) {} } Node; void getLongestLeafPath(Node* const root); int height(Node* const root); bool compareNode(Node* a, Node* b); void PrintPrefix(Node* const root); void Insert(Node* const root, Node* const node); bool IsInside(..
TRAVERSAL #include #include using namespace std; typedef struct node { node* left; node* right; int key; node() { left = nullptr; right = nullptr; key = 0; } } node; vector TraversalPostfix(const node* root); node* GetTree(const vector &prefix, const vector &infix); int main() { int caseNum = 0; cin >> caseNum; int nodeCnt = 0; vector prefix, infix; for (int cIter = 0; cIter < caseNum; cIter++) { prefix.c..

티스토리툴바