Submission #425591

#TimeUsernameProblemLanguageResultExecution timeMemory
425591MlxaComparing Plants (IOI20_plants)C++14
0 / 100
55 ms7012 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define all(x) x.begin(), x.end() #define mp make_pair #define mt make_tuple #define x first #define y second #include "plants.h" namespace my { const int N = 303; int n, k, kth[N], can[N]; vector<int> g[N]; struct tree_t { pair<int, int> arr[N]; void build() { for (int i = 0; i < N; ++i) { arr[i].x = kth[i]; arr[i].y = i; } } void range_add(int l, int r, int value) { for (int i = l; i < r; ++i) { arr[i].x += value; } } void cycle_add(int from, int value) { from %= n; from += n; from %= n; if (from + k <= n) { range_add(from, from + k, value); } else { range_add(from, n, value), range_add(0, from + k - n, value); } } pair<int, int> range_min(int l, int r) { return *min_element(arr + l, arr + r); } pair<int, int> cycle_min(int from) { from %= n; from += n; from %= n; if (from + k <= n) { return range_min(from, from + k); } else { return min(range_min(from, n), range_min(0, from + k - n)); } } int single(int i) { assert(0 <= i && i < n); return arr[i].x; } } tree; void edge(int v, int u) { assert(0 <= v && v < n); assert(0 <= u && u < n); cout << "edge " << v << " " << u << endl; g[v].push_back(u); } vector<int> topsort; void extract(int v) { tree.range_add(v, v + 1, N); while (1) { auto e = tree.cycle_min(v - k + 1); if (e.x) break; extract(e.y); } tree.cycle_add(v - k + 1, -1); topsort.push_back(v); } void bfs(int v, bool used[N]) { queue<int> q; q.push(v); used[v] = true; while (q.size()) { v = q.front(); q.pop(); for (int u : g[v]) { if (!used[u]) { q.push(u); used[u] = true; } } } } bool reach[N][N]; } void init(int _k, vector<int> _r) { using namespace my; n = (int)_r.size(); k = _k; copy(all(_r), kth); tree.build(); while (1) { auto e = tree.range_min(0, n); if (e.x) break; extract(e.y); } assert((int)topsort.size() == n); reverse(all(topsort)); for (int i = 0; i < n; ++i) { can[topsort[i]] = i; } for (int i = 0; i < n; ++i) { bfs(i, reach[i]); } } int compare_plants(int x, int y) { using namespace my; if (can[x] > can[y]) { return 1; } else { return -1; } } #ifdef LC #include "grader.cpp" #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...