oj.uz

Submission #76097

# Submission time Handle Problem Language Result Execution time Memory
76097 2018-09-12T04:33:41 Z Namnamseo Highway Tolls (IOI18_highway) C++17
18 / 100
 373 ms 9440 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;

bool dead[90010];

int find_cut(){
	int l=-1, r=n-1;
	while(l+1<r){
		int mid=(l+r)/2;

		for(int i=l+1; i<=mid; ++i){
			for(int ei:e[i]) asking[ei]=1;
		}

		bool res = (ask(asking) > base);

		if(res){
			for(int i=l+1; i<=mid; ++i){
				for(int ei:e[i]){
					int j=es[ei]-i;
					if(!dead[j]) asking[ei]=0;
				}
			}

			r = mid;
		} else {
			for(int i=l+1; i<=mid; ++i) dead[i]=1;
			l = mid;
		}
	}
	return 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]]){
		int j=es[ei]-q[i];
		if(!dead[j]) asking[ei]=0;
	}
	if(res) return find_deep(mid+1, r);
	else return find_deep(l, mid);
}

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();

	q[hd++] = cut;
	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;
				dst[y]=dst[x]+1;
				q[hd++]=y;
			}
		}
	}

	int deep = find_deep(0, hd-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 4 ms 2424 KB Output is correct
2 Correct 5 ms 2424 KB Output is correct
3 Correct 4 ms 2520 KB Output is correct
4 Correct 4 ms 2448 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 4 ms 2444 KB Output is correct
7 Correct 0 ms 2444 KB Output is correct
8 Correct 4 ms 2424 KB Output is correct
9 Correct 4 ms 2424 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 4 ms 2452 KB Output is correct
12 Correct 4 ms 2440 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2464 KB Output is correct
2 Correct 27 ms 3108 KB Output is correct
3 Correct 223 ms 8332 KB Output is correct
4 Correct 225 ms 8324 KB Output is correct
5 Correct 220 ms 8340 KB Output is correct
6 Correct 236 ms 8280 KB Output is correct
7 Correct 234 ms 8388 KB Output is correct
8 Correct 223 ms 8312 KB Output is correct
9 Correct 206 ms 8368 KB Output is correct
10 Correct 218 ms 8372 KB Output is correct
11 Correct 266 ms 8264 KB Output is correct
12 Correct 268 ms 8180 KB Output is correct
13 Correct 258 ms 8256 KB Output is correct
14 Correct 267 ms 8272 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3020 KB Output is correct
2 Correct 41 ms 3696 KB Output is correct
3 Correct 51 ms 4164 KB Output is correct
4 Correct 151 ms 7920 KB Output is correct
5 Correct 156 ms 7988 KB Output is correct
6 Correct 164 ms 8052 KB Output is correct
7 Correct 157 ms 7564 KB Output is correct
8 Correct 164 ms 7996 KB Output is correct
9 Correct 147 ms 7664 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2500 KB Output is correct
2 Correct 17 ms 3100 KB Output is correct
3 Correct 170 ms 6900 KB Output is correct
4 Correct 225 ms 8184 KB Output is correct
5 Correct 240 ms 8192 KB Output is correct
6 Correct 204 ms 7904 KB Output is correct
7 Correct 195 ms 8136 KB Output is correct
8 Incorrect 215 ms 8036 KB Output is incorrect: {s, t} is wrong.
9 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3140 KB Output is correct
2 Correct 30 ms 3116 KB Output is correct
3 Correct 287 ms 8580 KB Output is correct
4 Correct 321 ms 8788 KB Output is correct
5 Correct 358 ms 9404 KB Output is correct
6 Correct 360 ms 9340 KB Output is correct
7 Correct 372 ms 9388 KB Output is correct
8 Correct 360 ms 9396 KB Output is correct
9 Correct 267 ms 7456 KB Output is correct
10 Correct 266 ms 7712 KB Output is correct
11 Correct 249 ms 7608 KB Output is correct
12 Correct 325 ms 8884 KB Output is correct
13 Correct 295 ms 9180 KB Output is correct
14 Correct 368 ms 9244 KB Output is correct
15 Correct 363 ms 9240 KB Output is correct
16 Correct 304 ms 8224 KB Output is correct
17 Correct 214 ms 8712 KB Output is correct
18 Correct 224 ms 8656 KB Output is correct
19 Correct 214 ms 8744 KB Output is correct
20 Incorrect 221 ms 8612 KB Output is incorrect: {s, t} is wrong.
21 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 3144 KB Output is correct
2 Correct 30 ms 3144 KB Output is correct
3 Correct 292 ms 8508 KB Output is correct
4 Partially correct 340 ms 8696 KB Output is partially correct
5 Correct 330 ms 8728 KB Output is correct
6 Partially correct 344 ms 9416 KB Output is partially correct
7 Correct 300 ms 8716 KB Output is correct
8 Correct 251 ms 8668 KB Output is correct
9 Correct 283 ms 8864 KB Output is correct
10 Correct 344 ms 9440 KB Output is correct
11 Correct 365 ms 9404 KB Output is correct
12 Incorrect 373 ms 9440 KB Output is incorrect: {s, t} is wrong.
13 Halted 0 ms 0 KB -