oj.uz

Submission #158162

# Submission time Handle Problem Language Result Execution time Memory
158162 2019-10-15T06:44:21 Z kig9981 Highway Tolls (IOI18_highway) C++17
51 / 100
 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

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:30:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   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;
                             ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
highway.cpp:41:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   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;
                             ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 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

Subtask #2
7.0 / 7.0

# 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

Subtask #3
6.0 / 6.0

# 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

Subtask #4
33.0 / 33.0

# 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

Subtask #5
0 / 18.0

# 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 -

Subtask #6
0 / 31.0

# 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 -