oj.uz

Submission #158178

# Submission time Handle Problem Language Result Execution time Memory
158178 2019-10-15T08:41:34 Z kig9981 Highway Tolls (IOI18_highway) C++17
69 / 100
 352 ms 15132 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,1);
	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 ? 0:1;
		if((dist-ask(W))/(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);
		if((dist-ask(W))/(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);
		if((dist-ask(W))/(B-A)&1) tg=gnum;
	}
	answer(*gv[sg].begin(),*gv[tg].begin());
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6648 KB Output is correct
2 Correct 8 ms 6648 KB Output is correct
3 Correct 7 ms 6648 KB Output is correct
4 Correct 8 ms 6648 KB Output is correct
5 Correct 8 ms 6744 KB Output is correct
6 Correct 8 ms 6648 KB Output is correct
7 Correct 9 ms 6648 KB Output is correct
8 Correct 9 ms 6648 KB Output is correct
9 Correct 8 ms 6648 KB Output is correct
10 Correct 9 ms 6672 KB Output is correct
11 Correct 9 ms 6672 KB Output is correct
12 Correct 8 ms 6648 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6776 KB Output is correct
2 Correct 32 ms 7444 KB Output is correct
3 Correct 233 ms 14208 KB Output is correct
4 Correct 230 ms 14076 KB Output is correct
5 Correct 232 ms 14164 KB Output is correct
6 Correct 229 ms 14132 KB Output is correct
7 Correct 212 ms 14080 KB Output is correct
8 Correct 228 ms 14088 KB Output is correct
9 Correct 222 ms 14088 KB Output is correct
10 Correct 234 ms 14088 KB Output is correct
11 Correct 227 ms 14084 KB Output is correct
12 Correct 222 ms 14104 KB Output is correct
13 Correct 241 ms 14140 KB Output is correct
14 Correct 233 ms 14272 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 7544 KB Output is correct
2 Correct 51 ms 8428 KB Output is correct
3 Correct 80 ms 9132 KB Output is correct
4 Correct 201 ms 14080 KB Output is correct
5 Correct 205 ms 14180 KB Output is correct
6 Correct 209 ms 14172 KB Output is correct
7 Correct 231 ms 14092 KB Output is correct
8 Correct 214 ms 14120 KB Output is correct
9 Correct 218 ms 14208 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6776 KB Output is correct
2 Correct 29 ms 7376 KB Output is correct
3 Correct 179 ms 12448 KB Output is correct
4 Correct 250 ms 14140 KB Output is correct
5 Correct 229 ms 14156 KB Output is correct
6 Correct 234 ms 14088 KB Output is correct
7 Correct 222 ms 14088 KB Output is correct
8 Correct 224 ms 14080 KB Output is correct
9 Correct 239 ms 14084 KB Output is correct
10 Correct 212 ms 14236 KB Output is correct
11 Correct 217 ms 14076 KB Output is correct
12 Correct 235 ms 14208 KB Output is correct
13 Correct 226 ms 14120 KB Output is correct
14 Correct 207 ms 14092 KB Output is correct
15 Correct 222 ms 14180 KB Output is correct
16 Correct 230 ms 14132 KB Output is correct
17 Correct 215 ms 14140 KB Output is correct
18 Correct 223 ms 14088 KB Output is correct
19 Correct 223 ms 14088 KB Output is correct
20 Correct 212 ms 14088 KB Output is correct
21 Correct 216 ms 14076 KB Output is correct
22 Correct 211 ms 14080 KB Output is correct
23 Correct 219 ms 14160 KB Output is correct
24 Correct 218 ms 14120 KB Output is correct
25 Correct 235 ms 14096 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 7396 KB Output is correct
2 Correct 32 ms 7416 KB Output is correct
3 Correct 252 ms 14300 KB Output is correct
4 Correct 271 ms 14500 KB Output is correct
5 Correct 314 ms 14928 KB Output is correct
6 Correct 328 ms 14944 KB Output is correct
7 Correct 304 ms 15132 KB Output is correct
8 Correct 311 ms 14884 KB Output is correct
9 Correct 247 ms 11280 KB Output is correct
10 Correct 286 ms 10876 KB Output is correct
11 Correct 262 ms 12080 KB Output is correct
12 Correct 312 ms 13780 KB Output is correct
13 Correct 311 ms 14280 KB Output is correct
14 Correct 352 ms 14876 KB Output is correct
15 Correct 314 ms 14976 KB Output is correct
16 Correct 258 ms 11732 KB Output is correct
17 Correct 224 ms 14084 KB Output is correct
18 Correct 230 ms 14104 KB Output is correct
19 Correct 225 ms 14224 KB Output is correct
20 Correct 229 ms 14224 KB Output is correct
21 Correct 309 ms 14972 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 7672 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -