oj.uz

Submission #158281

# Submission time Handle Problem Language Result Execution time Memory
158281 2019-10-16T02:18:48 Z kig9981 Highway Tolls (IOI18_highway) C++17
6 / 100
 232 ms 8244 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]==e) C1.push_back(i);
		if(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 3064 KB Output is correct
2 Incorrect 4 ms 3112 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3192 KB Output is correct
2 Correct 24 ms 3576 KB Output is correct
3 Correct 214 ms 8036 KB Output is correct
4 Correct 216 ms 8068 KB Output is correct
5 Correct 210 ms 8032 KB Output is correct
6 Correct 190 ms 7956 KB Output is correct
7 Correct 196 ms 8048 KB Output is correct
8 Correct 202 ms 7972 KB Output is correct
9 Correct 197 ms 7976 KB Output is correct
10 Correct 232 ms 8044 KB Output is correct
11 Incorrect 195 ms 7736 KB Output is incorrect: {s, t} is wrong.
12 Halted 0 ms 0 KB -

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 4092 KB Output is correct
3 Correct 70 ms 4652 KB Output is correct
4 Correct 175 ms 7800 KB Output is correct
5 Correct 162 ms 7796 KB Output is correct
6 Correct 155 ms 7732 KB Output is correct
7 Correct 166 ms 7820 KB Output is correct
8 Correct 174 ms 7720 KB Output is correct
9 Correct 166 ms 7816 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3112 KB Output is correct
2 Incorrect 24 ms 3776 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 3664 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3624 KB Output is correct
2 Correct 20 ms 3644 KB Output is correct
3 Incorrect 197 ms 8244 KB Output is incorrect: {s, t} is wrong.
4 Halted 0 ms 0 KB -