# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
203294 | 2020-02-20T06:59:13 Z | MKopchev | Tales of seafaring (POI13_mor) | C++14 | 2182 ms | 27384 KB |
#include<bits/stdc++.h> using namespace std; const int nmax=5e3+42,kmax=1e6+42,inf=1e9+42; int n,m,k; vector<int> adj[nmax]; struct query { int from,to,dist,id; }; query inp[kmax]; bool cmp(query a,query b) { return a.from<b.from; } bool output[kmax]; int dist[nmax][2]; queue< pair<int,bool> > active; void bfs(int start) { for(int i=1;i<=n;i++) { dist[i][0]=inf; dist[i][1]=inf; } active.push({start,0}); dist[start][0]=0; while(active.size()) { pair<int,bool> current=active.front(); active.pop(); int node=current.first; bool type=current.second; //cout<<node<<" "<<type<<" "<<dist[node][type]<<endl; for(auto k:adj[node]) if(dist[node][type]+1<dist[k][!type]) { dist[k][!type]=dist[node][type]+1; active.push({k,!type}); } } } int main() { scanf("%i%i%i",&n,&m,&k); int u,v; for(int i=1;i<=m;i++) { scanf("%i%i",&u,&v); adj[u].push_back(v); adj[v].push_back(u); } for(int i=1;i<=k;i++) { scanf("%i%i%i",&inp[i].from,&inp[i].to,&inp[i].dist); inp[i].id=i; } sort(inp+1,inp+k+1,cmp); int pointer=1; for(int i=1;i<=n;i++) { bfs(i); while(inp[pointer].from==i) { if(dist[inp[pointer].to][inp[pointer].dist%2]<=inp[pointer].dist) { if(dist[inp[pointer].to][inp[pointer].dist%2]==0&&adj[inp[pointer].to].size()==0)output[inp[pointer].id]=0; else output[inp[pointer].id]=1; } pointer++; } } for(int i=1;i<=k;i++) if(output[i])printf("TAK\n"); else printf("NIE\n"); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 504 KB | Output is correct |
2 | Correct | 5 ms | 376 KB | Output is correct |
3 | Correct | 5 ms | 504 KB | Output is correct |
4 | Correct | 517 ms | 21676 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 504 KB | Output is correct |
2 | Correct | 5 ms | 376 KB | Output is correct |
3 | Correct | 5 ms | 508 KB | Output is correct |
4 | Correct | 520 ms | 21624 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 504 KB | Output is correct |
2 | Correct | 6 ms | 504 KB | Output is correct |
3 | Correct | 6 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 504 KB | Output is correct |
2 | Correct | 8 ms | 504 KB | Output is correct |
3 | Correct | 25 ms | 508 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 41 ms | 760 KB | Output is correct |
2 | Correct | 16 ms | 888 KB | Output is correct |
3 | Correct | 64 ms | 864 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 165 ms | 1164 KB | Output is correct |
2 | Correct | 17 ms | 632 KB | Output is correct |
3 | Correct | 344 ms | 964 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 936 ms | 21840 KB | Output is correct |
2 | Correct | 24 ms | 632 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1783 ms | 21880 KB | Output is correct |
2 | Correct | 118 ms | 7036 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1848 ms | 21984 KB | Output is correct |
2 | Correct | 251 ms | 10880 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2182 ms | 21904 KB | Output is correct |
2 | Correct | 528 ms | 27384 KB | Output is correct |