oj.uz

Submission #76093

# Submission time Handle Problem Language Result Execution time Memory
76093 2018-09-12T04:23:00 Z Namnamseo Highway Tolls (IOI18_highway) C++17
18 / 100
 389 ms 9424 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, 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 4 ms 2444 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 2524 KB Output is correct
5 Correct 4 ms 2436 KB Output is correct
6 Correct 4 ms 2424 KB Output is correct
7 Correct 4 ms 2328 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 2424 KB Output is correct
12 Correct 4 ms 2448 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2424 KB Output is correct
2 Correct 25 ms 2984 KB Output is correct
3 Correct 211 ms 8288 KB Output is correct
4 Correct 237 ms 8404 KB Output is correct
5 Correct 204 ms 8372 KB Output is correct
6 Correct 229 ms 8288 KB Output is correct
7 Correct 217 ms 8300 KB Output is correct
8 Correct 242 ms 8312 KB Output is correct
9 Correct 221 ms 8276 KB Output is correct
10 Correct 206 ms 8268 KB Output is correct
11 Correct 263 ms 8300 KB Output is correct
12 Correct 249 ms 8268 KB Output is correct
13 Correct 259 ms 8264 KB Output is correct
14 Correct 263 ms 8256 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3068 KB Output is correct
2 Correct 40 ms 3576 KB Output is correct
3 Correct 56 ms 4168 KB Output is correct
4 Correct 170 ms 7920 KB Output is correct
5 Correct 112 ms 7916 KB Output is correct
6 Correct 166 ms 8064 KB Output is correct
7 Correct 174 ms 7600 KB Output is correct
8 Correct 156 ms 7980 KB Output is correct
9 Correct 169 ms 7744 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2424 KB Output is correct
2 Correct 25 ms 3112 KB Output is correct
3 Correct 153 ms 6896 KB Output is correct
4 Correct 226 ms 8120 KB Output is correct
5 Correct 257 ms 8188 KB Output is correct
6 Correct 192 ms 7908 KB Output is correct
7 Correct 180 ms 8212 KB Output is correct
8 Incorrect 219 ms 8088 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 32 ms 3136 KB Output is correct
2 Correct 21 ms 3168 KB Output is correct
3 Correct 231 ms 8560 KB Output is correct
4 Correct 382 ms 8812 KB Output is correct
5 Correct 386 ms 9388 KB Output is correct
6 Correct 379 ms 9424 KB Output is correct
7 Correct 389 ms 9400 KB Output is correct
8 Correct 383 ms 9412 KB Output is correct
9 Correct 246 ms 7396 KB Output is correct
10 Correct 258 ms 7736 KB Output is correct
11 Correct 242 ms 7552 KB Output is correct
12 Correct 355 ms 8888 KB Output is correct
13 Correct 305 ms 9136 KB Output is correct
14 Correct 365 ms 9240 KB Output is correct
15 Correct 347 ms 9268 KB Output is correct
16 Correct 309 ms 8212 KB Output is correct
17 Correct 169 ms 8636 KB Output is correct
18 Correct 229 ms 8648 KB Output is correct
19 Correct 232 ms 8692 KB Output is correct
20 Incorrect 219 ms 8620 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 30 ms 3128 KB Output is correct
2 Correct 27 ms 3264 KB Output is correct
3 Partially correct 301 ms 8572 KB Output is partially correct
4 Partially correct 301 ms 8684 KB Output is partially correct
5 Correct 319 ms 8820 KB Output is correct
6 Partially correct 377 ms 9412 KB Output is partially correct
7 Correct 310 ms 8644 KB Output is correct
8 Correct 258 ms 8680 KB Output is correct
9 Correct 278 ms 8824 KB Output is correct
10 Partially correct 338 ms 9420 KB Output is partially correct
11 Correct 364 ms 9364 KB Output is correct
12 Incorrect 370 ms 9420 KB Output is incorrect: {s, t} is wrong.
13 Halted 0 ms 0 KB -