oj.uz

Submission #158277

# Submission time Handle Problem Language Result Execution time Memory
158277 2019-10-16T02:03:24 Z kig9981 Highway Tolls (IOI18_highway) C++17
51 / 100
 313 ms 15568 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 6 ms 3112 KB Output is correct
2 Correct 4 ms 3064 KB Output is correct
3 Correct 4 ms 3064 KB Output is correct
4 Correct 4 ms 3064 KB Output is correct
5 Correct 4 ms 3084 KB Output is correct
6 Correct 5 ms 3112 KB Output is correct
7 Correct 4 ms 3112 KB Output is correct
8 Correct 4 ms 3160 KB Output is correct
9 Correct 4 ms 3076 KB Output is correct
10 Correct 4 ms 3112 KB Output is correct
11 Correct 4 ms 3080 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 24 ms 3580 KB Output is correct
3 Correct 199 ms 8056 KB Output is correct
4 Correct 201 ms 8040 KB Output is correct
5 Correct 210 ms 8052 KB Output is correct
6 Correct 199 ms 7976 KB Output is correct
7 Correct 198 ms 8084 KB Output is correct
8 Correct 208 ms 7976 KB Output is correct
9 Correct 192 ms 7972 KB Output is correct
10 Correct 208 ms 8048 KB Output is correct
11 Correct 201 ms 7804 KB Output is correct
12 Correct 234 ms 7824 KB Output is correct
13 Correct 216 ms 7792 KB Output is correct
14 Correct 202 ms 7816 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3532 KB Output is correct
2 Correct 42 ms 4276 KB Output is correct
3 Correct 60 ms 4672 KB Output is correct
4 Correct 176 ms 7744 KB Output is correct
5 Correct 198 ms 7744 KB Output is correct
6 Correct 152 ms 7880 KB Output is correct
7 Correct 174 ms 7816 KB Output is correct
8 Correct 169 ms 7768 KB Output is correct
9 Correct 182 ms 7768 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3192 KB Output is correct
2 Correct 25 ms 3704 KB Output is correct
3 Correct 144 ms 6820 KB Output is correct
4 Correct 175 ms 7996 KB Output is correct
5 Correct 182 ms 7852 KB Output is correct
6 Correct 196 ms 7832 KB Output is correct
7 Correct 211 ms 8084 KB Output is correct
8 Correct 190 ms 7856 KB Output is correct
9 Correct 212 ms 8092 KB Output is correct
10 Correct 209 ms 8164 KB Output is correct
11 Correct 206 ms 7744 KB Output is correct
12 Correct 212 ms 7732 KB Output is correct
13 Correct 216 ms 7784 KB Output is correct
14 Correct 198 ms 7744 KB Output is correct
15 Correct 191 ms 8072 KB Output is correct
16 Correct 168 ms 7908 KB Output is correct
17 Correct 190 ms 7740 KB Output is correct
18 Correct 195 ms 7740 KB Output is correct
19 Correct 195 ms 8016 KB Output is correct
20 Correct 222 ms 7732 KB Output is correct
21 Correct 198 ms 9240 KB Output is correct
22 Correct 216 ms 9184 KB Output is correct
23 Correct 215 ms 8968 KB Output is correct
24 Correct 223 ms 8816 KB Output is correct
25 Correct 244 ms 8028 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3704 KB Output is correct
2 Correct 21 ms 3704 KB Output is correct
3 Correct 222 ms 8280 KB Output is correct
4 Correct 216 ms 8604 KB Output is correct
5 Correct 269 ms 8996 KB Output is correct
6 Correct 283 ms 9100 KB Output is correct
7 Correct 289 ms 9104 KB Output is correct
8 Correct 313 ms 8992 KB Output is correct
9 Runtime error 242 ms 14940 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 26 ms 3704 KB Output is correct
2 Correct 27 ms 3704 KB Output is correct
3 Correct 212 ms 8252 KB Output is correct
4 Correct 244 ms 8356 KB Output is correct
5 Correct 249 ms 8468 KB Output is correct
6 Correct 280 ms 9148 KB Output is correct
7 Correct 225 ms 8312 KB Output is correct
8 Correct 235 ms 8372 KB Output is correct
9 Correct 231 ms 8424 KB Output is correct
10 Correct 291 ms 9112 KB Output is correct
11 Correct 309 ms 8992 KB Output is correct
12 Correct 281 ms 9000 KB Output is correct
13 Runtime error 277 ms 15568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -