oj.uz

Submission #158276

# Submission time Handle Problem Language Result Execution time Memory
158276 2019-10-16T02:02:13 Z kig9981 Highway Tolls (IOI18_highway) C++17
46 / 100
 1500 ms 9240 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;
	}
  while(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;
	}
  while(C1.empty() || C2.empty());
	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;
	}
  while(0>s && s>=C1.size());
	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;
	}
  while(0>s && s>=C2.size());
	T=C2[s];
	answer(S,T);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:55:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while(0>e && e>=D/A);
   ^~~~~
highway.cpp:56:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  for(int i=0;i<N;i++) {
  ^~~
highway.cpp:61:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while(C1.empty() || C2.empty());
   ^~~~~
highway.cpp:62:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  s=0; e=C1.size()-1;
  ^
highway.cpp:71:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(0>s && s>=C1.size());
                ~^~~~~~~~~~~
highway.cpp:71:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while(0>s && s>=C1.size());
   ^~~~~
highway.cpp:72:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  S=C1[s];
  ^
highway.cpp:82:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(0>s && s>=C2.size());
                ~^~~~~~~~~~~
highway.cpp:82:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while(0>s && s>=C2.size());
   ^~~~~
highway.cpp:83:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  T=C2[s];
  ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3192 KB Output is correct
2 Correct 4 ms 3064 KB Output is correct
3 Runtime error 11 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 3196 KB Output is correct
2 Correct 46 ms 3664 KB Output is correct
3 Correct 205 ms 8044 KB Output is correct
4 Correct 211 ms 8044 KB Output is correct
5 Correct 190 ms 8048 KB Output is correct
6 Correct 215 ms 8072 KB Output is correct
7 Correct 224 ms 8008 KB Output is correct
8 Correct 195 ms 7912 KB Output is correct
9 Correct 201 ms 8072 KB Output is correct
10 Correct 195 ms 8240 KB Output is correct
11 Correct 185 ms 7800 KB Output is correct
12 Correct 203 ms 7736 KB Output is correct
13 Correct 195 ms 7740 KB Output is correct
14 Correct 211 ms 7864 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3644 KB Output is correct
2 Correct 39 ms 4088 KB Output is correct
3 Correct 46 ms 4592 KB Output is correct
4 Correct 167 ms 7728 KB Output is correct
5 Correct 156 ms 7796 KB Output is correct
6 Correct 128 ms 7804 KB Output is correct
7 Correct 148 ms 7800 KB Output is correct
8 Correct 149 ms 7824 KB Output is correct
9 Correct 178 ms 7732 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3196 KB Output is correct
2 Correct 28 ms 3576 KB Output is correct
3 Correct 165 ms 6972 KB Output is correct
4 Correct 222 ms 7988 KB Output is correct
5 Correct 196 ms 7864 KB Output is correct
6 Correct 190 ms 7992 KB Output is correct
7 Correct 179 ms 8068 KB Output is correct
8 Correct 193 ms 8036 KB Output is correct
9 Correct 207 ms 8232 KB Output is correct
10 Correct 200 ms 8044 KB Output is correct
11 Correct 192 ms 7744 KB Output is correct
12 Correct 203 ms 7732 KB Output is correct
13 Correct 210 ms 7740 KB Output is correct
14 Correct 186 ms 7872 KB Output is correct
15 Correct 164 ms 8020 KB Output is correct
16 Correct 185 ms 8008 KB Output is correct
17 Correct 206 ms 7748 KB Output is correct
18 Correct 212 ms 7948 KB Output is correct
19 Correct 176 ms 7936 KB Output is correct
20 Correct 204 ms 7744 KB Output is correct
21 Correct 196 ms 9160 KB Output is correct
22 Correct 195 ms 9240 KB Output is correct
23 Correct 230 ms 9092 KB Output is correct
24 Correct 219 ms 8844 KB Output is correct
25 Correct 213 ms 7968 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3664 KB Output is correct
2 Correct 28 ms 3720 KB Output is correct
3 Correct 221 ms 8276 KB Output is correct
4 Correct 263 ms 8540 KB Output is correct
5 Correct 271 ms 9068 KB Output is correct
6 Correct 256 ms 9036 KB Output is correct
7 Correct 276 ms 8980 KB Output is correct
8 Correct 266 ms 9084 KB Output is correct
9 Execution timed out 3086 ms 7448 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 31.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 222 ms 8244 KB Output is correct
4 Correct 222 ms 8356 KB Output is correct
5 Correct 243 ms 8560 KB Output is correct
6 Correct 284 ms 9068 KB Output is correct
7 Correct 219 ms 8308 KB Output is correct
8 Correct 253 ms 8364 KB Output is correct
9 Correct 241 ms 8468 KB Output is correct
10 Correct 303 ms 8984 KB Output is correct
11 Correct 290 ms 8992 KB Output is correct
12 Correct 269 ms 9040 KB Output is correct
13 Execution timed out 3071 ms 7764 KB Time limit exceeded
14 Halted 0 ms 0 KB -