oj.uz

Submission #75511

# Submission time Handle Problem Language Result Execution time Memory
75511 2018-09-10T05:40:22 Z Namnamseo Highway Tolls (IOI18_highway) C++17
51 / 100
 313 ms 10300 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 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 x){
	dead[x]=1;
	for(int ei:e[x]){
		int y=es[ei]-x;
		if(y==cut) continue;
		if(!dead[y]){
			muko(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;
				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 2348 KB Output is correct
2 Correct 4 ms 2424 KB Output is correct
3 Correct 4 ms 2440 KB Output is correct
4 Correct 4 ms 2444 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 4 ms 2428 KB Output is correct
7 Correct 4 ms 2440 KB Output is correct
8 Correct 4 ms 2440 KB Output is correct
9 Correct 5 ms 2424 KB Output is correct
10 Correct 4 ms 2524 KB Output is correct
11 Correct 4 ms 2524 KB Output is correct
12 Correct 5 ms 2440 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2552 KB Output is correct
2 Correct 26 ms 2984 KB Output is correct
3 Correct 224 ms 7960 KB Output is correct
4 Correct 249 ms 7932 KB Output is correct
5 Correct 242 ms 8040 KB Output is correct
6 Correct 223 ms 7928 KB Output is correct
7 Correct 242 ms 8032 KB Output is correct
8 Correct 239 ms 8036 KB Output is correct
9 Correct 232 ms 7936 KB Output is correct
10 Correct 249 ms 7924 KB Output is correct
11 Correct 307 ms 8468 KB Output is correct
12 Correct 279 ms 8992 KB Output is correct
13 Correct 248 ms 8604 KB Output is correct
14 Correct 270 ms 8528 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3320 KB Output is correct
2 Correct 41 ms 4060 KB Output is correct
3 Correct 56 ms 4320 KB Output is correct
4 Correct 197 ms 9024 KB Output is correct
5 Correct 176 ms 9712 KB Output is correct
6 Correct 182 ms 9696 KB Output is correct
7 Correct 174 ms 8072 KB Output is correct
8 Correct 155 ms 8852 KB Output is correct
9 Correct 170 ms 8468 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2588 KB Output is correct
2 Correct 28 ms 3068 KB Output is correct
3 Correct 168 ms 6812 KB Output is correct
4 Correct 286 ms 8024 KB Output is correct
5 Correct 281 ms 8008 KB Output is correct
6 Correct 313 ms 8028 KB Output is correct
7 Correct 203 ms 7936 KB Output is correct
8 Correct 235 ms 7964 KB Output is correct
9 Correct 235 ms 8012 KB Output is correct
10 Correct 234 ms 7940 KB Output is correct
11 Correct 280 ms 8472 KB Output is correct
12 Correct 232 ms 8336 KB Output is correct
13 Correct 249 ms 8188 KB Output is correct
14 Correct 251 ms 8536 KB Output is correct
15 Correct 218 ms 7920 KB Output is correct
16 Correct 233 ms 7932 KB Output is correct
17 Correct 280 ms 8320 KB Output is correct
18 Correct 247 ms 8840 KB Output is correct
19 Correct 210 ms 7932 KB Output is correct
20 Correct 256 ms 8948 KB Output is correct
21 Correct 204 ms 8200 KB Output is correct
22 Correct 189 ms 8220 KB Output is correct
23 Correct 204 ms 8180 KB Output is correct
24 Correct 219 ms 8432 KB Output is correct
25 Correct 263 ms 10300 KB Output is correct

Subtask #5
0 / 18.0

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