# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
158155 | 2019-10-15T06:06:28 Z | kig9981 | Highway Tolls (IOI18_highway) | C++17 | 247 ms | 15792 KB |
#include "highway.h" #include <bits/stdc++.h> using namespace std; vector<int> adj[90000]; set<int> gv[90000]; int g[90000]; void find_pair(int N, vector<int> U, vector<int> V, int A, int B) { int M=U.size(), sg=0, tg=0, gnum=0; vector<int> W(M); long long dist=ask(W); queue<int> Q; for(int i=0;i<M;i++) { adj[U[i]].push_back(V[i]); adj[V[i]].push_back(U[i]); } for(int i=0;i<N;i++) gv[0].insert(i); while(gv[sg].size()>1) { int c=*gv[sg].begin(); Q.push(c); g[c]=++gnum; gv[sg].erase(c); gv[gnum].insert(c); while(!Q.empty()) { c=Q.front(); Q.pop(); for(auto n: adj[c]) if(gv[gnum].size()<gv[sg].size() && g[n]==sg) { g[n]=gnum; gv[sg].erase(n); gv[gnum].insert(n); Q.push(n); } } if(gv[gnum].size()==1) { for(int i=0;i<M;i++) W[i]=g[U[i]]==gnum || g[V[i]]==gnum; if(ask(W)==dist+B-A) sg=gnum; } else { for(int i=0;i<M;i++) W[i]=g[U[i]]==gnum && g[V[i]]!=gnum || g[U[i]]!=gnum && g[V[i]]==gnum; if(sg==tg) { if(ask(W)>dist) sg=gnum; else { for(int i=0;i<M;i++) W[i]=g[U[i]]==gnum && g[V[i]]==gnum; if(ask(W)>dist) sg=tg=gnum; } } else if(ask(W)==dist+B-A) sg=gnum; } } while(gv[tg].size()>1) { int c=*gv[tg].begin(); Q.push(c); g[c]=++gnum; gv[tg].erase(c); gv[gnum].insert(c); while(!Q.empty()) { c=Q.front(); Q.pop(); for(auto n: adj[c]) if(gv[gnum].size()<gv[tg].size() && g[n]==tg) { g[n]=gnum; gv[tg].erase(n); gv[gnum].insert(n); Q.push(n); } } if(gv[gnum].size()==1) { for(int i=0;i<M;i++) W[i]=g[U[i]]==gnum || g[V[i]]==gnum; if(ask(W)==dist+B-A) tg=gnum; } else { for(int i=0;i<M;i++) W[i]=g[U[i]]==gnum && g[V[i]]!=gnum || g[U[i]]!=gnum && g[V[i]]==gnum; if(ask(W)==dist+B-A) tg=gnum; } } answer(*gv[sg].begin(),*gv[tg].begin()); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 6652 KB | Output is correct |
2 | Correct | 8 ms | 6648 KB | Output is correct |
3 | Correct | 10 ms | 6648 KB | Output is correct |
4 | Correct | 9 ms | 6668 KB | Output is correct |
5 | Correct | 8 ms | 6648 KB | Output is correct |
6 | Correct | 8 ms | 6648 KB | Output is correct |
7 | Correct | 8 ms | 6648 KB | Output is correct |
8 | Correct | 7 ms | 6672 KB | Output is correct |
9 | Correct | 8 ms | 6652 KB | Output is correct |
10 | Correct | 8 ms | 6668 KB | Output is correct |
11 | Correct | 7 ms | 6748 KB | Output is correct |
12 | Correct | 8 ms | 6648 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 12 ms | 6776 KB | Output is incorrect: more than 100 calls to ask. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 7708 KB | Output is correct |
2 | Correct | 54 ms | 8600 KB | Output is correct |
3 | Correct | 78 ms | 9704 KB | Output is correct |
4 | Correct | 231 ms | 15664 KB | Output is correct |
5 | Correct | 247 ms | 15672 KB | Output is correct |
6 | Correct | 207 ms | 15792 KB | Output is correct |
7 | Correct | 220 ms | 15720 KB | Output is correct |
8 | Correct | 180 ms | 15748 KB | Output is correct |
9 | Correct | 221 ms | 15760 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 10 ms | 6648 KB | Output is incorrect: more than 100 calls to ask. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 37 ms | 7636 KB | Output is incorrect: more than 100 calls to ask. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 36 ms | 7672 KB | Output is incorrect: more than 100 calls to ask. |
2 | Halted | 0 ms | 0 KB | - |