oj.uz

Submission #74971

# Submission time Handle Problem Language Result Execution time Memory
74971 2018-09-07T18:55:10 Z khsoo01 Highway Tolls (IOI18_highway) C++11
51 / 100
 450 ms 21520 KB 
#include "highway.h"
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int N = 90005, M = 1300005;
const ll inf = 1e18;

int n, m, a, b, p;
ll def, dis[N];
bool ban[N], v1[N], v2[N];

vector<int> adj[N], dij[N], drv[N], ord;
vector<pii> edg;

queue<int> q;

ll query () {
	vector<int> V;
	for(int i=0;i<m;i++) {
		V.push_back(ban[edg[i].X] || ban[edg[i].Y]);
	}
	return ask(V);
}

int getpiv () {
	int S = 0, E = (int)ord.size() - 1;
	while(S<E) {
		int Z = (S+E)/2;
		for(int i=0;i<=Z;i++) {
			ban[ord[i]] = true;
		}
		query() != def ? E = Z : S = Z+1;
		for(int i=0;i<=Z;i++) {
			ban[ord[i]] = false;
		}
	}
	return ord[S];
}

void dfs1 (int C) {
	if(C == p || v1[C]) return;
	v1[C] = true;
	for(auto &T : drv[C]) {
		dfs1(T);
	}
}

void dfs2 (int C) {
	if(v2[C]) return;
	v2[C] = true;
	for(auto &T : dij[C]) {
		dfs2(T);
	}
}

void find_pair(int _N, vector<int> _U, vector<int> _V, int _A, int _B) {
	n = _N;
	m = (int)_U.size();
	a = _A;
	b = _B;
	for(int i=0;i<m;i++) {
		edg.push_back({_U[i]+1, _V[i]+1});
		adj[_U[i]+1].push_back(_V[i]+1);
		adj[_V[i]+1].push_back(_U[i]+1);
	}
	for(int i=0;i<10;i++) query();
	def = query();
	for(int i=1;i<=n;i++) {
		ord.push_back(i);
	}
	p = getpiv();
	ord.clear();
	for(int i=1;i<p;i++) {
		ban[i] = true;
	}
	for(int i=1;i<=n;i++) {
		dis[i] = inf;
	}
	dis[p] = 0;
	q.push(p);
	while(!q.empty()) {
		int C = q.front();
		q.pop();
		ord.push_back(C);
		for(auto &T : adj[C]) {
			if(T < p) continue;
			if(dis[T] == inf) {
				dis[T] = dis[C] + 1;
				q.push(T);
			}
			if(dis[T] == dis[C] - 1) {
				dij[T].push_back(C);
				drv[C].push_back(T);
			}
		}
	}
	reverse(ord.begin(), ord.end());
	int PA = getpiv();
	ord.clear();
	dfs1(PA);
	for(int i=p;i<=n;i++) {
		if(v1[i]) dfs2(i);
	}
	for(int i=p;i<=n;i++) {
		if(!v2[i] && dis[i] + dis[PA] == def / a) ord.push_back(i);
	}
	int PB = getpiv();
	ord.clear();
	answer(PA-1, PB-1);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6692 KB Output is correct
2 Correct 8 ms 6776 KB Output is correct
3 Correct 9 ms 6696 KB Output is correct
4 Correct 8 ms 6676 KB Output is correct
5 Correct 8 ms 6672 KB Output is correct
6 Correct 9 ms 6676 KB Output is correct
7 Correct 9 ms 6688 KB Output is correct
8 Correct 9 ms 6676 KB Output is correct
9 Correct 8 ms 6700 KB Output is correct
10 Correct 8 ms 6692 KB Output is correct
11 Correct 8 ms 6676 KB Output is correct
12 Correct 8 ms 6672 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6776 KB Output is correct
2 Correct 26 ms 7968 KB Output is correct
3 Correct 281 ms 17984 KB Output is correct
4 Correct 271 ms 18060 KB Output is correct
5 Correct 276 ms 17968 KB Output is correct
6 Correct 314 ms 17956 KB Output is correct
7 Correct 266 ms 18004 KB Output is correct
8 Correct 403 ms 17968 KB Output is correct
9 Correct 258 ms 18036 KB Output is correct
10 Correct 267 ms 17972 KB Output is correct
11 Correct 291 ms 19312 KB Output is correct
12 Correct 279 ms 19532 KB Output is correct
13 Correct 292 ms 19304 KB Output is correct
14 Correct 260 ms 19192 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 8304 KB Output is correct
2 Correct 47 ms 9716 KB Output is correct
3 Correct 100 ms 9116 KB Output is correct
4 Correct 183 ms 18176 KB Output is correct
5 Correct 179 ms 18224 KB Output is correct
6 Correct 317 ms 19716 KB Output is correct
7 Correct 152 ms 14060 KB Output is correct
8 Correct 180 ms 18908 KB Output is correct
9 Correct 154 ms 15096 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6736 KB Output is correct
2 Correct 29 ms 7948 KB Output is correct
3 Correct 191 ms 14276 KB Output is correct
4 Correct 225 ms 15036 KB Output is correct
5 Correct 244 ms 16724 KB Output is correct
6 Correct 194 ms 14108 KB Output is correct
7 Correct 215 ms 15544 KB Output is correct
8 Correct 224 ms 15056 KB Output is correct
9 Correct 294 ms 17280 KB Output is correct
10 Correct 359 ms 17884 KB Output is correct
11 Correct 221 ms 15188 KB Output is correct
12 Correct 257 ms 18320 KB Output is correct
13 Correct 383 ms 18260 KB Output is correct
14 Correct 375 ms 17596 KB Output is correct
15 Correct 256 ms 16844 KB Output is correct
16 Correct 216 ms 14840 KB Output is correct
17 Correct 263 ms 17968 KB Output is correct
18 Correct 188 ms 14820 KB Output is correct
19 Correct 204 ms 13996 KB Output is correct
20 Correct 174 ms 14240 KB Output is correct
21 Correct 394 ms 16324 KB Output is correct
22 Correct 237 ms 15460 KB Output is correct
23 Correct 260 ms 17484 KB Output is correct
24 Correct 303 ms 17900 KB Output is correct
25 Correct 295 ms 21520 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 7988 KB Output is correct
2 Correct 33 ms 7992 KB Output is correct
3 Correct 423 ms 18272 KB Output is correct
4 Correct 365 ms 18108 KB Output is correct
5 Correct 418 ms 19208 KB Output is correct
6 Correct 390 ms 18876 KB Output is correct
7 Correct 376 ms 19184 KB Output is correct
8 Correct 369 ms 19376 KB Output is correct
9 Correct 267 ms 13816 KB Output is correct
10 Correct 420 ms 13804 KB Output is correct
11 Correct 260 ms 13572 KB Output is correct
12 Correct 308 ms 17292 KB Output is correct
13 Correct 416 ms 18604 KB Output is correct
14 Correct 411 ms 19432 KB Output is correct
15 Correct 349 ms 19448 KB Output is correct
16 Correct 296 ms 15680 KB Output is correct
17 Incorrect 233 ms 16940 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 8012 KB Output is correct
2 Correct 35 ms 7988 KB Output is correct
3 Correct 285 ms 17688 KB Output is correct
4 Partially correct 450 ms 18304 KB Output is partially correct
5 Correct 289 ms 17864 KB Output is correct
6 Incorrect 349 ms 19504 KB Output isn't correct
7 Halted 0 ms 0 KB -