oj.uz

Submission #259938

# Submission time Handle Problem Language Result Execution time Memory
259938 2020-08-08T20:32:38 Z medk Highway Tolls (IOI18_highway) C++14
51 / 100
 253 ms 262148 KB 
#include <bits/stdc++.h>
#include "highway.h"
 
#define ll long long
#define pb push_back
#define x first
#define y second
#define sz(u) (int)(u.size())
#define all(u) u.begin(),u.end()
 
using namespace std;
 
vector<vector<pair<int,int>>> g;
vector<bool> blocked;
vector<int> sz, toask, edges;
vector<pair<int,int>> cand;
int n,m;
ll initdist,a,b,dist;
int fst,scd;
 
void calc_sz(int u, int par=-1){
	sz[u]=1;
	for(auto p:g[u]){
		if(p.x==par || blocked[p.x]) continue;
		calc_sz(p.x,u);
		sz[u]+=sz[p.x];
	}
}
 
int find_centroid(int u, int par, int comp){
	for(auto p:g[u]){
		if(p.x==par || blocked[p.x]) continue;
		if(sz[p.x]>=comp/2) return find_centroid(p.x,u,comp);
	}
	return u;
}
 
void color(int u, int par){
	for(auto p:g[u]){
		if(p.x==par || blocked[p.x]) continue;
		toask[p.y]=1;
		edges.pb(p.y);
		color(p.x,u);
	}
}
 
void uncolor(){
	for(int e:edges) toask[e]=0;
	edges.clear();
}
 
void atdist(int u, int par, int goald, int d=0){
	for(auto p:g[u]){
		if(p.x==par || blocked[p.x]) continue;
		if(d==goald-1){
			cand.pb(p);
		}
		else atdist(p.x,u,goald,d+1);
	}
}
 
void find_first(int u){
	calc_sz(u);
	int centroid=find_centroid(u,u,sz[u]);
	vector<pair<int,int>> adj;
	for(auto p:g[centroid]){
		if(blocked[p.x]) continue;
		adj.pb(p);
		edges.pb(p.y);
		toask[p.y]=1;
	}
	int l=0, r=sz(adj)-1;
	if(ask(toask)==initdist){
		uncolor();
		while(l<r){
			int md=(l+r)/2;
			for(int i=l;i<=md;i++){
				color(adj[i].x,centroid);
			}
			if(ask(toask)==initdist) l=md+1;
			else r=md;
			uncolor();
		}
		blocked[centroid]=1;
		find_first(adj[l].x);
		return;
	}
	uncolor();
	while(l<r){
		int md=(l+r)/2;
		for(int i=l;i<=md;i++){
			toask[adj[i].y]=1;
			edges.pb(adj[i].y);
		}
		if(ask(toask)==initdist) l=md+1;
		else r=md;
		uncolor();
	}
	color(adj[l].x,centroid);
	ll get=ask(toask);
	uncolor();
	ll dst=(get-initdist)/(b-a)+1LL;
	atdist(centroid,-1,dst);
	l=0, r=sz(cand);
	while(l<r){
		int md=(l+r)/2;
		for(int i=l;i<=md;i++){
			toask[cand[i].y]=1;
			edges.pb(cand[i].y);
		}
		if(ask(toask)==initdist) l=md+1;
		else r=md;
		uncolor();
	}
	fst=cand[l].x;
}
 
void find_second(){
	for(int i=0;i<n;i++) blocked[i]=0;
	cand.clear();
	atdist(fst,-1,dist);
	int l=0, r=sz(cand);
	while(l<r){
		int md=(l+r)/2;
		for(int i=l;i<=md;i++){
			toask[cand[i].y]=1;
			edges.pb(cand[i].y);
		}
		if(ask(toask)==initdist) l=md+1;
		else r=md;
		uncolor();
	}
	scd=cand[l].x;
}
 
void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
	n=N, m=sz(U), a=A, b=B;
	g.resize(n), blocked.resize(n), sz.resize(n), toask.resize(m);
	for(int i=0;i<m;i++){
		g[U[i]].pb({V[i],i});
		g[V[i]].pb({U[i],i});
		toask[i]=0;
	}
	initdist=ask(toask);
	dist=initdist/a;
	find_first(0);
	find_second();
	answer(fst,scd);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 1 ms 384 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 14 ms 1272 KB Output is correct
3 Correct 161 ms 8528 KB Output is correct
4 Correct 136 ms 8260 KB Output is correct
5 Correct 146 ms 8384 KB Output is correct
6 Correct 138 ms 8184 KB Output is correct
7 Correct 147 ms 8288 KB Output is correct
8 Correct 135 ms 8376 KB Output is correct
9 Correct 140 ms 8312 KB Output is correct
10 Correct 158 ms 8568 KB Output is correct
11 Correct 145 ms 9776 KB Output is correct
12 Correct 147 ms 10236 KB Output is correct
13 Correct 136 ms 9592 KB Output is correct
14 Correct 144 ms 8884 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1920 KB Output is correct
2 Correct 22 ms 3576 KB Output is correct
3 Correct 35 ms 5240 KB Output is correct
4 Correct 108 ms 14840 KB Output is correct
5 Correct 144 ms 14840 KB Output is correct
6 Correct 108 ms 14840 KB Output is correct
7 Correct 110 ms 14840 KB Output is correct
8 Correct 108 ms 14840 KB Output is correct
9 Correct 109 ms 14840 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 11 ms 1280 KB Output is correct
3 Correct 100 ms 6520 KB Output is correct
4 Correct 140 ms 8292 KB Output is correct
5 Correct 149 ms 8440 KB Output is correct
6 Correct 154 ms 8372 KB Output is correct
7 Correct 149 ms 8388 KB Output is correct
8 Correct 155 ms 8344 KB Output is correct
9 Correct 141 ms 8296 KB Output is correct
10 Correct 141 ms 8248 KB Output is correct
11 Correct 146 ms 8824 KB Output is correct
12 Correct 249 ms 10232 KB Output is correct
13 Correct 144 ms 9848 KB Output is correct
14 Correct 160 ms 10232 KB Output is correct
15 Correct 153 ms 8360 KB Output is correct
16 Correct 151 ms 8380 KB Output is correct
17 Correct 143 ms 9976 KB Output is correct
18 Correct 162 ms 9716 KB Output is correct
19 Correct 146 ms 8312 KB Output is correct
20 Correct 171 ms 10936 KB Output is correct
21 Correct 123 ms 11080 KB Output is correct
22 Correct 126 ms 11136 KB Output is correct
23 Correct 126 ms 9708 KB Output is correct
24 Correct 133 ms 10460 KB Output is correct
25 Correct 172 ms 15428 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 253 ms 262148 KB Execution killed with signal 9 (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 245 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -