oj.uz

Submission #158280

# Submission time Handle Problem Language Result Execution time Memory
158280 2019-10-16T02:16:46 Z kig9981 Highway Tolls (IOI18_highway) C++17
51 / 100
 317 ms 15492 KB 
#include "highway.h"
#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> adj[90000];
int dist1[90000], dist2[90000];
bool chk[90000];
 
void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
	int M=U.size(), S, T, s, e, E;
	vector<int> W(M,0), C1, C2;
	queue<int> Q;
	long long D=ask(W);
	for(int i=0;i<M;i++) {
		adj[U[i]].push_back(V[i]);
		adj[V[i]].push_back(U[i]);
	}
	s=0; e=N-1;
	while(s<=e) {
		int m=(s+e)>>1;
		for(int i=0;i<M;i++) W[i]=i<=m;
		if(ask(W)!=D) e=m-1;
		else s=m+1;
	}
	E=s;
	memset(dist1,0x7f,sizeof(dist1));
	memset(dist2,0x7f,sizeof(dist2));
	dist1[U[E]]=0; Q.push(U[E]);
	while(!Q.empty()) {
		int c=Q.front();
		Q.pop();
		for(auto n: adj[c]) if(dist1[n]>dist1[c]+1) {
			dist1[n]=dist1[c]+1;
			Q.push(n);
		}
	}
	dist2[V[E]]=0; Q.push(V[E]);
	while(!Q.empty()) {
		int c=Q.front();
		Q.pop();
		for(auto n: adj[c]) if(dist2[n]>dist2[c]+1) {
			dist2[n]=dist2[c]+1;
			Q.push(n);
		}
	}
	s=0; e=D/A-1;
	while(s<=e) {
		int m=(s+e)>>1;
		for(int i=0;i<M;i++) W[i]=(dist1[U[i]]<dist2[U[i]] && dist1[U[i]]>=m)^(dist1[V[i]]<dist2[V[i]] && dist1[V[i]]>=m);
		if(ask(W)!=D) s=m+1;
		else e=m-1;
	}
	for(int i=0;i<N;i++) {
		if(dist1[i]<=dist2[i] && dist1[i]==e) C1.push_back(i);
		if(dist1[i]>=dist2[i] && dist2[i]==D/A-s) C2.push_back(i);
		chk[i]=false;
	}
	s=0; e=C1.size()-1;
	while(s<=e) {
		int m=(s+e)>>1;
		for(int i=0;i<N;i++) chk[i]=false;
		for(int i=0;i<=m;i++) chk[C1[i]]=true;
		for(int i=0;i<M;i++) W[i]=chk[U[i]]^chk[V[i]];
		if(ask(W)!=D) e=m-1;
		else s=m+1;
	}
	S=C1[s];
	s=0; e=C2.size()-1;
	while(s<=e) {
		int m=(s+e)>>1;
		for(int i=0;i<N;i++) chk[i]=false;
		for(int i=0;i<=m;i++) chk[C2[i]]=true;
		for(int i=0;i<M;i++) W[i]=chk[U[i]]^chk[V[i]];
		if(ask(W)!=D) e=m-1;
		else s=m+1;
	}
	T=C2[s];
	answer(S,T);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3192 KB Output is correct
2 Correct 5 ms 3064 KB Output is correct
3 Correct 5 ms 3192 KB Output is correct
4 Correct 5 ms 3112 KB Output is correct
5 Correct 5 ms 3164 KB Output is correct
6 Correct 5 ms 3192 KB Output is correct
7 Correct 4 ms 3064 KB Output is correct
8 Correct 4 ms 3112 KB Output is correct
9 Correct 5 ms 3112 KB Output is correct
10 Correct 5 ms 3112 KB Output is correct
11 Correct 5 ms 3192 KB Output is correct
12 Correct 4 ms 3080 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3192 KB Output is correct
2 Correct 25 ms 3664 KB Output is correct
3 Correct 220 ms 8080 KB Output is correct
4 Correct 198 ms 8036 KB Output is correct
5 Correct 195 ms 8048 KB Output is correct
6 Correct 184 ms 8068 KB Output is correct
7 Correct 226 ms 8044 KB Output is correct
8 Correct 200 ms 7960 KB Output is correct
9 Correct 205 ms 7960 KB Output is correct
10 Correct 203 ms 8264 KB Output is correct
11 Correct 246 ms 7744 KB Output is correct
12 Correct 265 ms 7748 KB Output is correct
13 Correct 208 ms 7832 KB Output is correct
14 Correct 212 ms 7728 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3576 KB Output is correct
2 Correct 41 ms 4216 KB Output is correct
3 Correct 59 ms 4604 KB Output is correct
4 Correct 167 ms 7816 KB Output is correct
5 Correct 164 ms 7748 KB Output is correct
6 Correct 177 ms 7804 KB Output is correct
7 Correct 161 ms 7836 KB Output is correct
8 Correct 165 ms 7720 KB Output is correct
9 Correct 160 ms 7812 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3096 KB Output is correct
2 Correct 26 ms 3684 KB Output is correct
3 Correct 158 ms 6824 KB Output is correct
4 Correct 205 ms 7996 KB Output is correct
5 Correct 191 ms 7944 KB Output is correct
6 Correct 195 ms 7912 KB Output is correct
7 Correct 194 ms 7960 KB Output is correct
8 Correct 207 ms 7908 KB Output is correct
9 Correct 215 ms 8040 KB Output is correct
10 Correct 233 ms 8040 KB Output is correct
11 Correct 243 ms 7804 KB Output is correct
12 Correct 224 ms 7748 KB Output is correct
13 Correct 223 ms 7728 KB Output is correct
14 Correct 209 ms 7796 KB Output is correct
15 Correct 190 ms 8060 KB Output is correct
16 Correct 201 ms 7928 KB Output is correct
17 Correct 217 ms 7736 KB Output is correct
18 Correct 211 ms 7788 KB Output is correct
19 Correct 192 ms 8060 KB Output is correct
20 Correct 230 ms 7740 KB Output is correct
21 Correct 194 ms 9148 KB Output is correct
22 Correct 189 ms 9168 KB Output is correct
23 Correct 199 ms 9072 KB Output is correct
24 Correct 208 ms 8876 KB Output is correct
25 Correct 230 ms 7964 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3612 KB Output is correct
2 Correct 29 ms 3704 KB Output is correct
3 Correct 205 ms 8272 KB Output is correct
4 Correct 232 ms 8612 KB Output is correct
5 Correct 297 ms 8988 KB Output is correct
6 Correct 290 ms 9044 KB Output is correct
7 Correct 274 ms 9032 KB Output is correct
8 Correct 277 ms 9032 KB Output is correct
9 Runtime error 247 ms 14836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3800 KB Output is correct
2 Correct 29 ms 3780 KB Output is correct
3 Correct 229 ms 8304 KB Output is correct
4 Correct 234 ms 8344 KB Output is correct
5 Correct 258 ms 8472 KB Output is correct
6 Correct 317 ms 9120 KB Output is correct
7 Correct 218 ms 8416 KB Output is correct
8 Correct 223 ms 8348 KB Output is correct
9 Correct 246 ms 8420 KB Output is correct
10 Correct 270 ms 8924 KB Output is correct
11 Correct 300 ms 9008 KB Output is correct
12 Correct 300 ms 9000 KB Output is correct
13 Runtime error 248 ms 15492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -