oj.uz

Submission #158273

# Submission time Handle Problem Language Result Execution time Memory
158273 2019-10-16T01:53:51 Z kig9981 Highway Tolls (IOI18_highway) C++17
46 / 100
 289 ms 15648 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<N;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;
	}
  assert(0<=e && e<D/A);
	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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3112 KB Output is correct
2 Correct 4 ms 3076 KB Output is correct
3 Runtime error 10 ms 6264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

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 3704 KB Output is correct
3 Correct 190 ms 8036 KB Output is correct
4 Correct 200 ms 8036 KB Output is correct
5 Correct 180 ms 8052 KB Output is correct
6 Correct 211 ms 8048 KB Output is correct
7 Correct 203 ms 8124 KB Output is correct
8 Correct 204 ms 8000 KB Output is correct
9 Correct 196 ms 7964 KB Output is correct
10 Correct 206 ms 8100 KB Output is correct
11 Correct 207 ms 7740 KB Output is correct
12 Correct 208 ms 7788 KB Output is correct
13 Correct 205 ms 7848 KB Output is correct
14 Correct 211 ms 7784 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3704 KB Output is correct
2 Correct 41 ms 4088 KB Output is correct
3 Correct 59 ms 4656 KB Output is correct
4 Correct 179 ms 7844 KB Output is correct
5 Correct 165 ms 7796 KB Output is correct
6 Correct 174 ms 7804 KB Output is correct
7 Correct 151 ms 7860 KB Output is correct
8 Correct 156 ms 7740 KB Output is correct
9 Correct 172 ms 7796 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 24 ms 3704 KB Output is correct
3 Correct 149 ms 6896 KB Output is correct
4 Correct 182 ms 7992 KB Output is correct
5 Correct 182 ms 7904 KB Output is correct
6 Correct 191 ms 8044 KB Output is correct
7 Correct 190 ms 7912 KB Output is correct
8 Correct 186 ms 7856 KB Output is correct
9 Correct 190 ms 8048 KB Output is correct
10 Correct 208 ms 8080 KB Output is correct
11 Correct 208 ms 7928 KB Output is correct
12 Correct 208 ms 7792 KB Output is correct
13 Correct 208 ms 7736 KB Output is correct
14 Correct 201 ms 7788 KB Output is correct
15 Correct 178 ms 7896 KB Output is correct
16 Correct 187 ms 7980 KB Output is correct
17 Correct 207 ms 7852 KB Output is correct
18 Correct 212 ms 7784 KB Output is correct
19 Correct 184 ms 7944 KB Output is correct
20 Correct 207 ms 7776 KB Output is correct
21 Correct 192 ms 9164 KB Output is correct
22 Correct 184 ms 9160 KB Output is correct
23 Correct 209 ms 9000 KB Output is correct
24 Correct 218 ms 8864 KB Output is correct
25 Correct 225 ms 7968 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3704 KB Output is correct
2 Correct 29 ms 3704 KB Output is correct
3 Correct 217 ms 8284 KB Output is correct
4 Correct 244 ms 8588 KB Output is correct
5 Correct 287 ms 9008 KB Output is correct
6 Correct 276 ms 9020 KB Output is correct
7 Correct 261 ms 9064 KB Output is correct
8 Correct 285 ms 8984 KB Output is correct
9 Runtime error 231 ms 14832 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 3852 KB Output is correct
2 Correct 29 ms 3644 KB Output is correct
3 Correct 227 ms 8352 KB Output is correct
4 Correct 235 ms 8412 KB Output is correct
5 Correct 245 ms 8456 KB Output is correct
6 Correct 275 ms 9112 KB Output is correct
7 Correct 199 ms 8404 KB Output is correct
8 Correct 220 ms 8356 KB Output is correct
9 Correct 230 ms 8400 KB Output is correct
10 Correct 266 ms 8920 KB Output is correct
11 Correct 283 ms 9100 KB Output is correct
12 Correct 289 ms 9124 KB Output is correct
13 Runtime error 252 ms 15648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -