# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
377367 | 2021-03-14T06:15:46 Z | Thistle | Comparing Plants (IOI20_plants) | C++14 | 4000 ms | 2820 KB |
#include "plants.h" #include <vector> #include<algorithm> #include<set> #include<iostream> #include<random> #include<queue> #include<cassert> using namespace std; using ll=long long; using H=pair<ll, ll>; #define vec vector #define vi vec<ll> #define pb push_back #define all(a) (a).begin(),(a).end() #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++) #define rep(i,n) rng((i),0,(n)) #define siz(a) int((a).size()) int n; vec<vec<int>>e; void init(int k, std::vector<int> r) { //DAG kouchiku n=siz(r); rep(i,n) r.pb(r[i]); e.assign(n,vec<int>()); rep(i,n)rep(_,n){ if(i==_) continue; int j=_; if(j<i) j+=n; if(i+k<=j) continue; int t=j-i,mn,mx; if(j+k<=i+n){ mn=max(0,r[j]-t)+1; mx=k-1; } else{ assert(0); int step=i+k-j-1; mx=k-1; mn=max(0,(r[j]-(k-(2*step+2))))+1; } if(r[i]<mn||mx<r[i]){ e[_].pb(i); } if(j+k<=i+n){ mx=t-1+max(0,r[j]-t); mn=0; } else{ int step=i+k-j-1; mn=0; mx=n-k+min(2*step, r[j]-1); } if(r[i]<mn||mx<r[i]){ e[i].pb(_); } } return; } int compare_plants(int x, int y) { vec<bool>used(n,0); queue<int>q; q.push(x); used[x]=1; while(!q.empty()){ int t=q.front();q.pop(); for(auto g:e[t]){ if(!used[g]){ used[g]=1; q.push(g); } } } if(used[y]) return -1; used=vec<bool>(n,0); used[y]=1; q.push(y); while(!q.empty()){ int t=q.front();q.pop(); for(auto g:e[t]){ if(!used[g]){ used[g]=1; q.push(g); } } } if(used[x]) return 1; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 492 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 492 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 492 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Execution timed out | 4051 ms | 2820 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 492 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 492 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 492 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |