oj.uz

Submission #349395

# Submission time Handle Problem Language Result Execution time Memory
349395 2021-01-17T14:10:18 Z amunduzbaev Highway Tolls (IOI18_highway) C++14
51 / 100
 294 ms 21544 KB 
#include "highway.h"
#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif
using namespace std;
 
#define pb push_back
#define sz(x) (int)x.size()
#define ff first
#define ss second
#define vv vector 
typedef pair<int, int> pii; 
#define ll long long
 
const int NN = 130005;
vv<pii> edges[NN];
vv<pii> gg[NN];
vv<int> tr;
vv<int> tt;
int un[NN], used[NN], wh[NN], rr, dd[NN], on[NN], l, r;
ll dis; 
 
void dfs(int u, int p, int d = 0){
	if(d == dis) tt.pb(u);
	
	dd[u] = d;
	for(auto x : edges[u]){
		if(x.ff == p) continue;
		on[x.ff] = x.ss;
		dfs(x.ff, u, d+1);
	}
}
 
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	for(int i=0;i<sz(V);i++){
		gg[V[i]].pb({U[i], i});
		gg[U[i]].pb({V[i], i});
	}
	
	int mm = sz(V);
	tr.resize(mm, 0);
	dis = ask(tr)/A;
	
	l = 0, r = mm-1;
	while(l < r){
		int m = (l + r-1)>>1;
		for(int i=l;i<=m;i++) tr[l] = 1;
		
		ll res = ask(tr);
		tr.assign(mm, 0);
		if(res > dis*A) r = m;
		else l = m+1;
	}
	
	rr = V[l];
	queue<int> q;
	q.push(rr);
	used[rr] = 1;
	vector<int> tmp(mm, 1); 
	
	while(!q.empty()){
		int cur = q.front(); q.pop();
		for(auto x : gg[cur]){
			if(used[x.ff]) continue;
			edges[cur].pb(x);
			edges[x.ff].pb({cur, x.ss});
			tmp[x.ss] = 0;
			used[x.ff] = 1;
			q.push(x.ff);
		}
	}
	queue<int> qq;
	qq.push(0);
	memset(used, 0, sizeof used);
	un[0] = 1, used[0] = 1;
	int last = 1;
	wh[last] = 0;
	
	while(!qq.empty()){
		int cur = qq.front(); qq.pop();
		for(auto x : edges[cur]){
			if(used[x.ff]) continue;
			un[x.ff] = ++last;
			used[x.ff] = 1;
			wh[last] = x.ff;
			qq.push(x.ff);
		}
	}
	
	l = 1, r = last;
	ll br = dis * B;
	while(l < r){
		int m = (l + r -1)>>1;
		tr = tmp;
		
		for(int i=1;i<=m;i++){
			for(auto x:edges[wh[i]]){
				if(un[x.ff] > m) continue;
				tr[x.ss] = 1;
			}
		}
		
		ll res = ask(tr);
		
		if(res < br) l = m+1;
		else r = m;
	}
	
	rr = wh[l];
	dfs(rr, -1, 0);
	
	l = 0, r = sz(tt)-1;
	
	while(l < r){
		int m = (l + r)>>1;
		tr = tmp;
		for(int i=0;i<=m;i++) tr[on[tt[i]]] = 1;
		ll res = ask(tr);
		
		if(res > dis*A) r = m;
		else l = m+1;
	}
	
	answer(rr, tt[l]);
}
 
/*
 
7 6 1 2 0 4
0 1 
0 2 
0 3 
3 4 
2 6 
3 5 
 
*/

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7020 KB Output is correct
2 Correct 20 ms 8044 KB Output is correct
3 Correct 234 ms 17540 KB Output is correct
4 Correct 243 ms 17380 KB Output is correct
5 Correct 245 ms 17432 KB Output is correct
6 Correct 250 ms 17488 KB Output is correct
7 Correct 200 ms 17424 KB Output is correct
8 Correct 204 ms 17280 KB Output is correct
9 Correct 172 ms 17436 KB Output is correct
10 Correct 294 ms 17396 KB Output is correct
11 Correct 218 ms 17272 KB Output is correct
12 Correct 204 ms 18352 KB Output is correct
13 Correct 182 ms 17580 KB Output is correct
14 Correct 245 ms 17752 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8556 KB Output is correct
2 Correct 33 ms 9708 KB Output is correct
3 Correct 48 ms 11700 KB Output is correct
4 Correct 163 ms 19500 KB Output is correct
5 Correct 125 ms 19572 KB Output is correct
6 Correct 143 ms 20868 KB Output is correct
7 Correct 165 ms 21544 KB Output is correct
8 Correct 148 ms 19756 KB Output is correct
9 Correct 142 ms 20360 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7020 KB Output is correct
2 Correct 24 ms 8172 KB Output is correct
3 Correct 137 ms 15096 KB Output is correct
4 Correct 233 ms 17556 KB Output is correct
5 Correct 274 ms 17228 KB Output is correct
6 Correct 269 ms 17380 KB Output is correct
7 Correct 274 ms 17384 KB Output is correct
8 Correct 268 ms 17320 KB Output is correct
9 Correct 275 ms 17508 KB Output is correct
10 Correct 273 ms 17444 KB Output is correct
11 Correct 267 ms 17384 KB Output is correct
12 Correct 278 ms 17540 KB Output is correct
13 Correct 276 ms 17712 KB Output is correct
14 Correct 249 ms 17944 KB Output is correct
15 Correct 187 ms 17272 KB Output is correct
16 Correct 239 ms 17316 KB Output is correct
17 Correct 233 ms 17656 KB Output is correct
18 Correct 225 ms 17948 KB Output is correct
19 Correct 190 ms 17376 KB Output is correct
20 Correct 211 ms 18280 KB Output is correct
21 Correct 191 ms 18844 KB Output is correct
22 Correct 250 ms 18852 KB Output is correct
23 Correct 213 ms 18384 KB Output is correct
24 Correct 203 ms 18916 KB Output is correct
25 Correct 237 ms 21512 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 8172 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 Incorrect 27 ms 8172 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -