# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
158162 | 2019-10-15T06:44:21 Z | kig9981 | Highway Tolls (IOI18_highway) | C++17 | 238 ms | 14292 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=1, gnum=1; vector<int> W(M); long long dist=ask(W); for(int b=1;;b<<=1) { for(int i=0;i<M;i++) W[i]=(U[i]^V[i])&b ? 1:0; if((ask(W)-dist)/(B-A)&1) { for(int i=0;i<N;i++) gv[g[i]=(i&b) ? 1:0].insert(i); break; } } while(gv[sg].size()>1) { ++gnum; for(auto c: gv[sg]) { gv[gnum].insert(c); g[c]=gnum; if(2*gv[gnum].size()>=gv[sg].size()) break; } for(auto c: gv[gnum]) gv[sg].erase(c); 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)&1) sg=gnum; } while(gv[tg].size()>1) { ++gnum; for(auto c: gv[tg]) { gv[gnum].insert(c); g[c]=gnum; if(2*gv[gnum].size()>=gv[tg].size()) break; } for(auto c: gv[gnum]) gv[tg].erase(c); 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)&1) tg=gnum; } answer(*gv[sg].begin(),*gv[tg].begin()); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 6648 KB | Output is correct |
2 | Correct | 7 ms | 6648 KB | Output is correct |
3 | Correct | 8 ms | 6648 KB | Output is correct |
4 | Correct | 8 ms | 6652 KB | Output is correct |
5 | Correct | 7 ms | 6648 KB | Output is correct |
6 | Correct | 8 ms | 6632 KB | Output is correct |
7 | Correct | 7 ms | 6744 KB | Output is correct |
8 | Correct | 8 ms | 6652 KB | Output is correct |
9 | Correct | 7 ms | 6668 KB | Output is correct |
10 | Correct | 7 ms | 6752 KB | Output is correct |
11 | Correct | 7 ms | 6748 KB | Output is correct |
12 | Correct | 7 ms | 6648 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 6648 KB | Output is correct |
2 | Correct | 27 ms | 7416 KB | Output is correct |
3 | Correct | 221 ms | 14164 KB | Output is correct |
4 | Correct | 230 ms | 14080 KB | Output is correct |
5 | Correct | 230 ms | 14104 KB | Output is correct |
6 | Correct | 231 ms | 14260 KB | Output is correct |
7 | Correct | 224 ms | 14088 KB | Output is correct |
8 | Correct | 229 ms | 14172 KB | Output is correct |
9 | Correct | 220 ms | 14084 KB | Output is correct |
10 | Correct | 222 ms | 14248 KB | Output is correct |
11 | Correct | 227 ms | 14124 KB | Output is correct |
12 | Correct | 226 ms | 14076 KB | Output is correct |
13 | Correct | 232 ms | 14116 KB | Output is correct |
14 | Correct | 227 ms | 14164 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 28 ms | 7464 KB | Output is correct |
2 | Correct | 50 ms | 8308 KB | Output is correct |
3 | Correct | 70 ms | 9196 KB | Output is correct |
4 | Correct | 217 ms | 14068 KB | Output is correct |
5 | Correct | 224 ms | 14032 KB | Output is correct |
6 | Correct | 205 ms | 14116 KB | Output is correct |
7 | Correct | 198 ms | 14084 KB | Output is correct |
8 | Correct | 208 ms | 14248 KB | Output is correct |
9 | Correct | 198 ms | 13996 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 6776 KB | Output is correct |
2 | Correct | 29 ms | 7416 KB | Output is correct |
3 | Correct | 182 ms | 12444 KB | Output is correct |
4 | Correct | 226 ms | 14116 KB | Output is correct |
5 | Correct | 223 ms | 14068 KB | Output is correct |
6 | Correct | 213 ms | 14116 KB | Output is correct |
7 | Correct | 225 ms | 14184 KB | Output is correct |
8 | Correct | 223 ms | 14176 KB | Output is correct |
9 | Correct | 224 ms | 14144 KB | Output is correct |
10 | Correct | 237 ms | 14176 KB | Output is correct |
11 | Correct | 218 ms | 14108 KB | Output is correct |
12 | Correct | 238 ms | 14072 KB | Output is correct |
13 | Correct | 222 ms | 14108 KB | Output is correct |
14 | Correct | 211 ms | 14068 KB | Output is correct |
15 | Correct | 197 ms | 14084 KB | Output is correct |
16 | Correct | 225 ms | 14084 KB | Output is correct |
17 | Correct | 217 ms | 14100 KB | Output is correct |
18 | Correct | 223 ms | 14072 KB | Output is correct |
19 | Correct | 210 ms | 14156 KB | Output is correct |
20 | Correct | 217 ms | 14144 KB | Output is correct |
21 | Correct | 212 ms | 14140 KB | Output is correct |
22 | Correct | 216 ms | 14068 KB | Output is correct |
23 | Correct | 219 ms | 14240 KB | Output is correct |
24 | Correct | 210 ms | 14196 KB | Output is correct |
25 | Correct | 227 ms | 14292 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 31 ms | 7544 KB | Output is incorrect: {s, t} is wrong. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 26 ms | 7472 KB | Output is incorrect: {s, t} is wrong. |
2 | Halted | 0 ms | 0 KB | - |