oj.uz

Submission #298899

# Submission time Handle Problem Language Result Execution time Memory
298899 2020-09-14T09:47:15 Z amiratou Highway Tolls (IOI18_highway) C++14
51 / 100
 193 ms 13416 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MX = 90005;
#define sz(x) (ll)(x.size())
#define fi first
#define se second
typedef pair<ll,ll> ii;

vector<ii> vec[MX];
bitset<MX> vis,dead;
vector<ll> order,h;
ll d[MX],W[MX],p[MX];

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	for (ll i = 0; i < N-1; ++i)
	{
		vec[U[i]].push_back({V[i],i});
		vec[V[i]].push_back({U[i],i});
	}
	queue<ll> q;
	q.push(0);
	vis[0]=1;
	while(!q.empty()){
		ll f=q.front();
		q.pop();
		for(auto it:vec[f]){
			if(!vis[it.fi]){
				d[it.fi]=d[f]+1;
				//cerr<<it.fi<<","<<d[it.fi]<<"\n";
				vis[it.fi]=1,q.push(it.fi);
				order.push_back(it.se);
			}
		}
	}
	//cerr<<"zero "<<d[0]<<"\n";
	for (ll i = 0; i < N-1; ++i)
		if(d[U[i]]>d[V[i]])swap(U[i],V[i]);
	vector<int> query(N-1,0);
	ll l=0,r=N-2,K=ask(query),ans=-1;
	while(l<=r){
		fill(query.begin(),query.end(),0);
		ll med=(l+r)>>1;
		for (ll i = 0; i < med; ++i)
			query[order[i]]=1;
		if(ask(query)==K)ans=med,l=med+1;
		else r=med-1;
	}
	ll lca=U[order[ans]];
	//cerr<<lca<<"\n";
	q.push(lca);
	order.clear();
	d[lca]=0;
	while(!q.empty()){
		ll f=q.front();
		q.pop();
		for(auto it:vec[f]){
			if(d[it.fi]<d[f])continue;
			q.push(it.fi);
			p[it.fi]=f;
			d[it.fi]=d[f]+1;
			W[it.fi]=it.se;
			order.push_back(it.se);
		}
	}
	/*cerr<<"LCA : "<<lca<<"\n";
	for(auto it:order){
		cerr<<U[it]<<"-"<<V[it]<<"\n";
	}*/
	l=0,r=sz(order)-1,ans=-1;
	while(l<=r){
		fill(query.begin(),query.end(),1);
		ll med=(l+r)>>1;
		for (ll i = 0; i <= med; ++i)
			query[order[i]]=0;
		if(ask(query)==K)ans=med,r=med-1;
		else l=med+1;
	}
	ll T=V[order[ans]];
	//cerr<<T<<"\n";
	if(d[T]==(K/A)){answer(lca,T);return ;}
	ll node=T;
	while(node!=lca){
		//cerr<<node<<"\n";
		dead[node]=1;
		h.push_back(W[node]);
		node=p[node];
	}
	q.push(lca);
	order.clear();
	while(!q.empty()){
		ll f=q.front();
		q.pop();
		for(auto it:vec[f]){
			if(d[it.fi]<d[f] ||dead[it.fi])continue;
			q.push(it.fi);
			order.push_back(it.se);
		}
	}
	l=0,r=sz(order)-1,ans=-1;
	/*for(auto it:h){
		cerr<<U[it]<<"->"<<V[it]<<"\n";
	}*/
	while(l<=r){
		fill(query.begin(),query.end(),1);
		for(auto it:h)
			query[it]=0;
		ll med=(l+r)>>1;
		for (ll i = 0; i <= med; ++i)
			query[order[i]]=0;
		if(ask(query)==K)ans=med,r=med-1;
		else l=med+1;
	}
	answer(T,V[order[ans]]);

}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2592 KB Output is correct
2 Correct 15 ms 3584 KB Output is correct
3 Correct 170 ms 11932 KB Output is correct
4 Correct 161 ms 11860 KB Output is correct
5 Correct 167 ms 11848 KB Output is correct
6 Correct 158 ms 11816 KB Output is correct
7 Correct 162 ms 11824 KB Output is correct
8 Correct 163 ms 11832 KB Output is correct
9 Correct 156 ms 11824 KB Output is correct
10 Correct 166 ms 12024 KB Output is correct
11 Correct 176 ms 11924 KB Output is correct
12 Correct 173 ms 12000 KB Output is correct
13 Correct 171 ms 11852 KB Output is correct
14 Correct 168 ms 11972 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3584 KB Output is correct
2 Correct 29 ms 4476 KB Output is correct
3 Correct 39 ms 5220 KB Output is correct
4 Correct 117 ms 11060 KB Output is correct
5 Correct 117 ms 11080 KB Output is correct
6 Correct 120 ms 11180 KB Output is correct
7 Correct 121 ms 10696 KB Output is correct
8 Correct 119 ms 11228 KB Output is correct
9 Correct 118 ms 10816 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 16 ms 3584 KB Output is correct
3 Correct 129 ms 9784 KB Output is correct
4 Correct 173 ms 11848 KB Output is correct
5 Correct 163 ms 11812 KB Output is correct
6 Correct 189 ms 12112 KB Output is correct
7 Correct 157 ms 11816 KB Output is correct
8 Correct 170 ms 11804 KB Output is correct
9 Correct 180 ms 11828 KB Output is correct
10 Correct 185 ms 12064 KB Output is correct
11 Correct 193 ms 11944 KB Output is correct
12 Correct 186 ms 12264 KB Output is correct
13 Correct 181 ms 11948 KB Output is correct
14 Correct 173 ms 11816 KB Output is correct
15 Correct 186 ms 12044 KB Output is correct
16 Correct 144 ms 11816 KB Output is correct
17 Correct 183 ms 12012 KB Output is correct
18 Correct 160 ms 12036 KB Output is correct
19 Correct 173 ms 11840 KB Output is correct
20 Correct 168 ms 12004 KB Output is correct
21 Correct 140 ms 12184 KB Output is correct
22 Correct 146 ms 12208 KB Output is correct
23 Correct 160 ms 12024 KB Output is correct
24 Correct 156 ms 12036 KB Output is correct
25 Correct 180 ms 13416 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 3456 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 3456 KB Incorrect
2 Halted 0 ms 0 KB -