# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
301289 | 2020-09-17T20:12:26 Z | joseacaz | Comparing Plants (IOI20_plants) | C++17 | 116 ms | 33492 KB |
#include "plants.h" #include <bits/stdc++.h> #define pb push_back #define all(x) x.begin(), x.end() using namespace std; typedef long long ll; typedef vector<int> vi; const int MAXN = 5e3 + 5; int N, k, vis[MAXN], memo[MAXN][MAXN], MP[MAXN][MAXN]; vi r, Graph[MAXN]; void sub(int idx) { int id = idx; for(int i = 1; i < k; i++) { id--; if(id < 0) id += N; if(r[id] > 0) { r[id]--; if(r[id] == 0 && !vis[id] && !MP[idx][id]) { Graph[idx].pb(id); MP[idx][id] = 1; } } } } int getnext(int idx) { int id = idx; for(int i = 1; i < N; i++) { id++; if(id > N) id -= N; if(i < k && !vis[id] && !MP[idx][id]) { Graph[idx].pb(id); MP[idx][i] = 1; } if(r[id] == 0 && !vis[id]) return id; } return idx; } void dfs(int root, int node) { memo[root][node] = 1; for(auto i : Graph[node]) if(i != node && !memo[root][i]) dfs(root, i); } void init(int _k, vi _r) { k = _k; swap(r, _r); N = r.size(); int maxIdx = 0; for(int i = 0; i < N; i++) { if(r[i] != 0) continue; int maxim = 1; int id = i; for(int j = 1; j < k; j++) { id--; if(id < 0) id += N; if(r[id] == 0) maxim = 0; } if(maxim) maxIdx = i; } while(!vis[maxIdx]) { vis[maxIdx] = 1; sub(maxIdx); maxIdx = getnext(maxIdx); } for(int i = 0; i < N; i++) dfs(i, i); return; } int compare_plants(int x, int y) { if(memo[x][y]) return 1; else if(memo[y][x]) return -1; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 512 KB | Output is correct |
2 | Correct | 1 ms | 512 KB | Output is correct |
3 | Incorrect | 1 ms | 512 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 512 KB | Output is correct |
2 | Correct | 1 ms | 512 KB | Output is correct |
3 | Correct | 1 ms | 512 KB | Output is correct |
4 | Incorrect | 1 ms | 544 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 512 KB | Output is correct |
2 | Correct | 1 ms | 512 KB | Output is correct |
3 | Correct | 1 ms | 512 KB | Output is correct |
4 | Incorrect | 1 ms | 544 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 512 KB | Output is correct |
2 | Correct | 1 ms | 640 KB | Output is correct |
3 | Incorrect | 116 ms | 33492 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 512 KB | Output is correct |
2 | Correct | 1 ms | 512 KB | Output is correct |
3 | Incorrect | 1 ms | 512 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 512 KB | Output is correct |
2 | Correct | 1 ms | 512 KB | Output is correct |
3 | Correct | 1 ms | 512 KB | Output is correct |
4 | Incorrect | 0 ms | 512 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 512 KB | Output is correct |
2 | Correct | 1 ms | 512 KB | Output is correct |
3 | Incorrect | 1 ms | 512 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |