oj.uz

Submission #158275

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

Compilation message

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from highway.cpp:2:
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:71:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(0<=s && s<C1.size());
                  ~^~~~~~~~~~
highway.cpp:82:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(0<=s && s<C2.size());
                  ~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3160 KB Output is correct
2 Correct 4 ms 3064 KB Output is correct
3 Runtime error 11 ms 6352 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 24 ms 3704 KB Output is correct
3 Correct 211 ms 8048 KB Output is correct
4 Correct 206 ms 8048 KB Output is correct
5 Correct 212 ms 8040 KB Output is correct
6 Correct 200 ms 8012 KB Output is correct
7 Correct 225 ms 7992 KB Output is correct
8 Correct 192 ms 7972 KB Output is correct
9 Correct 223 ms 7968 KB Output is correct
10 Correct 192 ms 8040 KB Output is correct
11 Correct 206 ms 7736 KB Output is correct
12 Correct 192 ms 7740 KB Output is correct
13 Correct 213 ms 7716 KB Output is correct
14 Correct 211 ms 7776 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3612 KB Output is correct
2 Correct 41 ms 4124 KB Output is correct
3 Correct 58 ms 4660 KB Output is correct
4 Correct 166 ms 7744 KB Output is correct
5 Correct 164 ms 7800 KB Output is correct
6 Correct 175 ms 7796 KB Output is correct
7 Correct 166 ms 7732 KB Output is correct
8 Correct 172 ms 7772 KB Output is correct
9 Correct 158 ms 7768 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3196 KB Output is correct
2 Correct 24 ms 3576 KB Output is correct
3 Correct 145 ms 6820 KB Output is correct
4 Correct 202 ms 8000 KB Output is correct
5 Correct 208 ms 7852 KB Output is correct
6 Correct 200 ms 7908 KB Output is correct
7 Correct 222 ms 7916 KB Output is correct
8 Correct 201 ms 7860 KB Output is correct
9 Correct 208 ms 8028 KB Output is correct
10 Correct 213 ms 8056 KB Output is correct
11 Correct 215 ms 7788 KB Output is correct
12 Correct 227 ms 7776 KB Output is correct
13 Correct 229 ms 7816 KB Output is correct
14 Correct 212 ms 7804 KB Output is correct
15 Correct 199 ms 7860 KB Output is correct
16 Correct 189 ms 7932 KB Output is correct
17 Correct 217 ms 7792 KB Output is correct
18 Correct 221 ms 7780 KB Output is correct
19 Correct 200 ms 7936 KB Output is correct
20 Correct 208 ms 7752 KB Output is correct
21 Correct 197 ms 9140 KB Output is correct
22 Correct 199 ms 9160 KB Output is correct
23 Correct 208 ms 8976 KB Output is correct
24 Correct 231 ms 8868 KB Output is correct
25 Correct 257 ms 7968 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3772 KB Output is correct
2 Correct 30 ms 3704 KB Output is correct
3 Correct 205 ms 8276 KB Output is correct
4 Correct 250 ms 8640 KB Output is correct
5 Correct 310 ms 9104 KB Output is correct
6 Correct 285 ms 9088 KB Output is correct
7 Correct 283 ms 8984 KB Output is correct
8 Correct 279 ms 8992 KB Output is correct
9 Runtime error 248 ms 14768 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 3624 KB Output is correct
2 Correct 30 ms 3624 KB Output is correct
3 Correct 242 ms 8244 KB Output is correct
4 Correct 250 ms 8356 KB Output is correct
5 Correct 263 ms 8592 KB Output is correct
6 Correct 296 ms 9048 KB Output is correct
7 Correct 234 ms 8424 KB Output is correct
8 Correct 238 ms 8348 KB Output is correct
9 Correct 259 ms 8416 KB Output is correct
10 Correct 281 ms 8980 KB Output is correct
11 Correct 294 ms 9056 KB Output is correct
12 Correct 286 ms 9008 KB Output is correct
13 Runtime error 219 ms 15412 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -