oj.uz

Submission #300732

# Submission time Handle Problem Language Result Execution time Memory
300732 2020-09-17T12:50:57 Z TMJN Highway Tolls (IOI18_highway) C++17
51 / 100
 221 ms 43640 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

struct edge{
	int to,id;
};

vector<edge>V[900000];
int dist[900000];

void dfs(int x,int from){
	for(edge e:V[x]){
		if(e.to==from)continue;
		dist[e.to]=dist[x]+1;
		dfs(e.to,x);
	}
}

void find_pair(int N,vector<int>u,vector<int>v,int A,int B){
	for(int i=0;i<N;i++){
		V[i].clear();
	}
	int M=u.size();
	assert(M==N-1);
	for(int i=0;i<M;i++){
		V[u[i]].push_back({v[i],i});
		V[v[i]].push_back({u[i],i});
	}
	long long Base=ask(vector<int>(M,0));
	int path_len=Base/A;
	int l,r;
	l=-1;
	r=M-1;
	while(l+1!=r){
		int m=(l+r)/2;
		vector<int>K(M,0);
		for(int i=0;i<=m;i++){
			K[i]=1;
		}
		long long t=ask(K);
		if(t>Base){
			r=m;
		}
		else{
			l=m;
		}
	}
	int p=u[r];
	int q=v[r];
	vector<int>K(M,0);
	K[r]=1;
	queue<int>que;
	que.push(q);
	while(!que.empty()){
		int x=que.front();
		que.pop();
		for(edge e:V[x]){
			if(K[e.id])continue;
			K[e.id]=true;
			que.push(e.to);
		}
	}
	K[r]=0;
	long long t=ask(K);
	int len=(t-Base)/(B-A);
	int S,T;
	for(int i=0;i<N;i++){
		dist[i]=-1;
	}
	dist[q]=0;
	dfs(q,p);
	vector<int>W;
	for(int i=0;i<N;i++){
		if(dist[i]==len){
			W.push_back(i);
		}
	}
	l=-1;
	r=W.size()-1;
	while(l+1!=r){
		int m=(l+r)/2;
		vector<int>K(M,0);
		for(int i=0;i<=m;i++){
			for(edge e:V[W[i]]){
				K[e.id]=1;
			}
		}
		if(Base!=ask(K)){
			r=m;
		}
		else{
			l=m;
		}
	}
	S=W[r];
	W.clear();
	for(int i=0;i<N;i++){
		dist[i]=-1;
	}
	dist[p]=0;
	dfs(p,q);
	for(int i=0;i<N;i++){
		if(dist[i]==path_len-1-len){
			W.push_back(i);
		}
	}
	l=-1;
	r=W.size()-1;
	while(l+1!=r){
		int m=(l+r)/2;
		vector<int>K(M,0);
		for(int i=0;i<=m;i++){
			for(edge e:V[W[i]]){
				K[e.id]=1;
			}
		}
		if(Base!=ask(K)){
			r=m;
		}
		else{
			l=m;
		}
	}
	T=W[r];
	answer(S,T);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21504 KB Output is correct
2 Correct 15 ms 21504 KB Output is correct
3 Correct 15 ms 21504 KB Output is correct
4 Correct 15 ms 21452 KB Output is correct
5 Correct 15 ms 21504 KB Output is correct
6 Correct 15 ms 21504 KB Output is correct
7 Correct 15 ms 21504 KB Output is correct
8 Correct 15 ms 21504 KB Output is correct
9 Correct 15 ms 21504 KB Output is correct
10 Correct 15 ms 21520 KB Output is correct
11 Correct 15 ms 21436 KB Output is correct
12 Correct 15 ms 21504 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21504 KB Output is correct
2 Correct 26 ms 22136 KB Output is correct
3 Correct 145 ms 27500 KB Output is correct
4 Correct 154 ms 27476 KB Output is correct
5 Correct 164 ms 27608 KB Output is correct
6 Correct 158 ms 27472 KB Output is correct
7 Correct 157 ms 27488 KB Output is correct
8 Correct 155 ms 27384 KB Output is correct
9 Correct 143 ms 27448 KB Output is correct
10 Correct 167 ms 27496 KB Output is correct
11 Correct 143 ms 27516 KB Output is correct
12 Correct 139 ms 28244 KB Output is correct
13 Correct 157 ms 27764 KB Output is correct
14 Correct 147 ms 27900 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 22400 KB Output is correct
2 Correct 37 ms 23284 KB Output is correct
3 Correct 50 ms 24384 KB Output is correct
4 Correct 123 ms 28944 KB Output is correct
5 Correct 127 ms 29068 KB Output is correct
6 Correct 110 ms 29760 KB Output is correct
7 Correct 125 ms 30440 KB Output is correct
8 Correct 122 ms 29368 KB Output is correct
9 Correct 118 ms 29604 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21504 KB Output is correct
2 Correct 27 ms 22136 KB Output is correct
3 Correct 146 ms 26056 KB Output is correct
4 Correct 166 ms 27544 KB Output is correct
5 Correct 141 ms 27352 KB Output is correct
6 Correct 146 ms 27256 KB Output is correct
7 Correct 143 ms 27404 KB Output is correct
8 Correct 137 ms 27404 KB Output is correct
9 Correct 166 ms 27644 KB Output is correct
10 Correct 194 ms 27508 KB Output is correct
11 Correct 157 ms 27656 KB Output is correct
12 Correct 159 ms 28196 KB Output is correct
13 Correct 155 ms 27904 KB Output is correct
14 Correct 151 ms 27892 KB Output is correct
15 Correct 157 ms 27376 KB Output is correct
16 Correct 158 ms 26972 KB Output is correct
17 Correct 167 ms 27644 KB Output is correct
18 Correct 156 ms 27904 KB Output is correct
19 Correct 150 ms 27348 KB Output is correct
20 Correct 161 ms 28384 KB Output is correct
21 Correct 192 ms 28512 KB Output is correct
22 Correct 192 ms 28052 KB Output is correct
23 Correct 201 ms 28060 KB Output is correct
24 Correct 221 ms 28184 KB Output is correct
25 Correct 164 ms 30620 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 43640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 55 ms 43640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -