oj.uz

Submission #104711

# Submission time Handle Problem Language Result Execution time Memory
104711 2019-04-09T01:51:07 Z turbat Highway Tolls (IOI18_highway) C++14
51 / 100
 260 ms 15152 KB 
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
using pii = pair <int, int>;
using vi = vector <int>;
#define N 200005
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define ll long long
int deep[N], cnt, flat[N], len,  curdeep;
vector <pii> edg[N];
pii parent[N];
bool vis[N];
void dfs(int u){
	vis[u] = 1;
	flat[cnt++] = u;
	for (pii v : edg[u])
		if (!vis[v.F]){
			dfs(v.F);
			parent[v.F] = mp(u, v.S);			
		}
}
void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
  	int M = U.size();
 	vi v(M);
 	ll maxdist, dist;
 	for (int i = 0;i < M;i++) v[i] = 1;
 	maxdist = ask(v);
 	for (int i = 0;i < M;i++) v[i] = 0;
 	for (int i = 0;i < M;i++){
 		edg[U[i]].pb(mp(V[i], i));
 		edg[V[i]].pb(mp(U[i], i));
 	}
 	dfs(0);
 	int l = 1, r = n - 1, mid;
 	while (l != r){
 		mid = (l + r) / 2;
 		for (int i = l;i <= mid;i++)
 			v[parent[flat[i]].S] = 1;
 		dist = ask(v);
 		if (dist < maxdist) l = mid + 1;
 		else {
 			r = mid;
	 		for (int i = l;i <= mid;i++)
	 			v[parent[flat[i]].S] = 0;
 		}
 	}
 	for (int i = 0;i < M;i++) v[i] = 0;
 	int s = flat[l];
 	cnt = 0;
 	memset(vis, 0, sizeof vis);
 	dfs(s);
 	l = 1, r = n - 1;
 	while (l != r){
 		mid = (l + r) / 2;
 		for (int i = l;i <= mid;i++)
 			v[parent[flat[i]].S] = 1;
 		dist = ask(v);
 		if (dist < maxdist) l = mid + 1;
 		else {
 			r = mid;
	 		for (int i = l;i <= mid;i++)
	 			v[parent[flat[i]].S] = 0;
 		}
 	}
 	int t = flat[l];
 	answer(s, t);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5244 KB Output is correct
2 Correct 7 ms 5224 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5156 KB Output is correct
5 Correct 6 ms 5156 KB Output is correct
6 Correct 6 ms 5164 KB Output is correct
7 Correct 6 ms 5160 KB Output is correct
8 Correct 6 ms 5240 KB Output is correct
9 Correct 6 ms 5160 KB Output is correct
10 Correct 7 ms 5168 KB Output is correct
11 Correct 6 ms 5112 KB Output is correct
12 Correct 6 ms 5112 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5240 KB Output is correct
2 Correct 26 ms 5800 KB Output is correct
3 Correct 205 ms 11432 KB Output is correct
4 Correct 260 ms 11432 KB Output is correct
5 Correct 219 ms 11436 KB Output is correct
6 Correct 237 ms 11448 KB Output is correct
7 Correct 230 ms 11496 KB Output is correct
8 Correct 208 ms 11532 KB Output is correct
9 Correct 225 ms 11432 KB Output is correct
10 Correct 181 ms 11432 KB Output is correct
11 Correct 211 ms 11904 KB Output is correct
12 Correct 230 ms 12488 KB Output is correct
13 Correct 218 ms 12004 KB Output is correct
14 Correct 224 ms 12088 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6264 KB Output is correct
2 Correct 31 ms 7372 KB Output is correct
3 Correct 58 ms 8496 KB Output is correct
4 Correct 160 ms 15100 KB Output is correct
5 Correct 160 ms 15104 KB Output is correct
6 Correct 168 ms 15104 KB Output is correct
7 Correct 174 ms 15104 KB Output is correct
8 Correct 156 ms 15152 KB Output is correct
9 Correct 180 ms 15108 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5184 KB Output is correct
2 Correct 31 ms 5868 KB Output is correct
3 Correct 163 ms 10160 KB Output is correct
4 Correct 207 ms 11548 KB Output is correct
5 Correct 211 ms 11436 KB Output is correct
6 Correct 184 ms 11452 KB Output is correct
7 Correct 209 ms 11432 KB Output is correct
8 Correct 216 ms 11416 KB Output is correct
9 Correct 222 ms 11432 KB Output is correct
10 Correct 211 ms 11436 KB Output is correct
11 Correct 211 ms 11636 KB Output is correct
12 Correct 219 ms 12424 KB Output is correct
13 Correct 229 ms 12108 KB Output is correct
14 Correct 242 ms 12388 KB Output is correct
15 Correct 214 ms 11424 KB Output is correct
16 Correct 171 ms 11448 KB Output is correct
17 Correct 215 ms 12176 KB Output is correct
18 Correct 209 ms 12248 KB Output is correct
19 Correct 202 ms 11432 KB Output is correct
20 Correct 216 ms 12732 KB Output is correct
21 Correct 147 ms 11588 KB Output is correct
22 Correct 170 ms 11700 KB Output is correct
23 Correct 150 ms 11640 KB Output is correct
24 Correct 182 ms 11980 KB Output is correct
25 Correct 204 ms 14724 KB Output is correct

Subtask #5
0 / 18.0

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