oj.uz

Submission #75517

# Submission time Handle Problem Language Result Execution time Memory
75517 2018-09-10T06:39:19 Z Namnamseo Highway Tolls (IOI18_highway) C++17
51 / 100
 341 ms 9472 KB 
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define pb push_back

#define rep(i,n) for(int i=0; i<(n); ++i)
#define rrep(i,n) for(int i=1; i<=(n); ++i)

ll ask(const vector<int>&);
void answer(int, int);

vector<int> asking;

int n, m;

vector<int> e[90010];
int es[130010];

ll base;

int find_cut(int l, int r){
	if(l == r) return l;
	int mid = (l+r)/2;
	for(int p=l; p<=mid; ++p) for(int ei:e[p]) asking[ei]=1;
	bool res = (ask(asking) > base);
	for(int p=l; p<=mid; ++p) for(int ei:e[p]) asking[ei]=0;
	if(res) return find_cut(l, mid);
	else return find_cut(mid+1, r);
}

int cut;

int dst[90010];
int q[90010], hd, tl;
bool vis[90010];

int find_deep(int l, int r){
	if(l == r){
		return q[l];
	}
	int mid=(l+r)/2;
	for(int i=mid+1; i<=r; ++i) for(int ei:e[q[i]]) asking[ei]=1;
	bool res = (ask(asking) > base);
	for(int i=mid+1; i<=r; ++i) for(int ei:e[q[i]]) asking[ei]=0;
	if(res) return find_deep(mid+1, r);
	else return find_deep(l, mid);
}

bool dead[90010];
void muko(int z){
	queue<int> q;
	q.push(z);
	dead[z]=1;
	for(;q.size();){
		int x = q.front(); q.pop();
		for(int ei:e[x]){
			int y=es[ei]-x;
			if(dst[y]==dst[x]-1 && !dead[y]){
				dead[y]=1;
				q.push(y);
			}
		}
	}
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	// find cut vertex
	n = N;
	m = U.size();
	asking.resize(m);

	base = ask(asking);

	for(int i=0; i<m; ++i){
		int a = U[i], b = V[i];
		e[a].pb(i); e[b].pb(i);
		es[i]=a+b;
	}

	cut = find_cut(0, n-1);

	q[hd++] = cut;
	vis[cut]=1;
	while(hd>tl){
		int x=q[tl++];
		for(int ei:e[x]){
			int y=es[ei]-x;
			if(!vis[y]){
				vis[y]=1;
				dst[y]=dst[x]+1;
				q[hd++]=y;
			}
		}
	}

	int deep = find_deep(0, n-1);
	muko(deep);

	hd=tl=0;
	q[hd++] = cut;
	fill(vis, vis+n, 0);
	vis[cut]=1;
	while(hd>tl){
		int x=q[tl++];
		for(int ei:e[x]){
			int y=es[ei]-x;
			if(dead[y]) continue;
			if(!vis[y]){
				vis[y]=1;
				q[hd++]=y;
			}
		}
	}

	int d2 = find_deep(0, hd-1);
	answer(deep, d2);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2452 KB Output is correct
2 Correct 19 ms 3028 KB Output is correct
3 Correct 221 ms 8376 KB Output is correct
4 Correct 204 ms 8328 KB Output is correct
5 Correct 231 ms 8324 KB Output is correct
6 Correct 229 ms 8276 KB Output is correct
7 Correct 227 ms 8276 KB Output is correct
8 Correct 238 ms 8316 KB Output is correct
9 Correct 228 ms 8284 KB Output is correct
10 Correct 223 ms 8284 KB Output is correct
11 Correct 263 ms 8268 KB Output is correct
12 Correct 236 ms 8172 KB Output is correct
13 Correct 227 ms 8188 KB Output is correct
14 Correct 230 ms 8268 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3048 KB Output is correct
2 Correct 41 ms 3760 KB Output is correct
3 Correct 50 ms 4364 KB Output is correct
4 Correct 156 ms 8196 KB Output is correct
5 Correct 159 ms 8180 KB Output is correct
6 Correct 161 ms 8304 KB Output is correct
7 Correct 162 ms 8284 KB Output is correct
8 Correct 168 ms 8300 KB Output is correct
9 Correct 192 ms 8300 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2452 KB Output is correct
2 Correct 38 ms 3016 KB Output is correct
3 Correct 155 ms 6996 KB Output is correct
4 Correct 260 ms 8312 KB Output is correct
5 Correct 249 ms 8300 KB Output is correct
6 Correct 246 ms 8292 KB Output is correct
7 Correct 217 ms 8280 KB Output is correct
8 Correct 208 ms 8296 KB Output is correct
9 Correct 228 ms 8360 KB Output is correct
10 Correct 236 ms 8292 KB Output is correct
11 Correct 260 ms 8256 KB Output is correct
12 Correct 222 ms 8264 KB Output is correct
13 Correct 265 ms 8260 KB Output is correct
14 Correct 269 ms 8308 KB Output is correct
15 Correct 220 ms 8280 KB Output is correct
16 Correct 210 ms 8340 KB Output is correct
17 Correct 266 ms 8268 KB Output is correct
18 Correct 259 ms 8264 KB Output is correct
19 Correct 215 ms 8288 KB Output is correct
20 Correct 236 ms 8264 KB Output is correct
21 Correct 208 ms 8660 KB Output is correct
22 Correct 203 ms 8540 KB Output is correct
23 Correct 226 ms 8704 KB Output is correct
24 Correct 180 ms 8584 KB Output is correct
25 Correct 272 ms 8316 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3124 KB Output is correct
2 Correct 30 ms 3156 KB Output is correct
3 Correct 234 ms 8608 KB Output is correct
4 Correct 337 ms 8896 KB Output is correct
5 Incorrect 341 ms 9436 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3192 KB Output is correct
2 Correct 33 ms 3092 KB Output is correct
3 Partially correct 290 ms 8632 KB Output is partially correct
4 Correct 302 ms 8720 KB Output is correct
5 Correct 273 ms 8932 KB Output is correct
6 Incorrect 298 ms 9472 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -