oj.uz

Submission #296251

# Submission time Handle Problem Language Result Execution time Memory
296251 2020-09-10T12:39:56 Z PeppaPig Highway Tolls (IOI18_highway) C++14
51 / 100
 222 ms 15068 KB 
#include "highway.h"
#include <bits/stdc++.h>

#define long long long
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 2e5 + 5;

int n, m, A, B;
int chk[N], par[N];
vector<int> u, v;
vector<pii> g[N];

void find_pair(int _n, vector<int> _u, vector<int> _v, int _A, int _B) {
	n = _n, m = (int)_u.size(), u = _u, v = _v, A = _A, B = _B;

	for(int i = 0; i < m; i++) {
		g[u[i]].emplace_back(v[i], i);
		g[v[i]].emplace_back(u[i], i);
	}

	int rot = 0;
	long mn_dist = ask(vector<int>(m));
	vector<int> ans;
	
	for(int _ = 0; _ < 2; _++) {
		queue<int> Q;
		vector<int> vec;

		memset(chk, 0, sizeof chk);

		Q.emplace(rot), chk[rot] = 1, par[rot] = rot;
		while(!Q.empty()) {
			int u = Q.front(); Q.pop();
			for(pii v : g[u]) if(!chk[v.x]) {
				chk[v.x] = 1, par[v.x] = u;
				vec.emplace_back(v.y);
				Q.emplace(v.x);
			}
		}

		reverse(vec.begin(), vec.end());

		//printf("rot = %d\n", rot);
		//for(int i : vec) printf("%d ", i);
		//printf("\n");

		int l = 0, r = (int)vec.size() - 1;
		while(l < r) {
			int mid = (l + r) >> 1;

			vector<int> now(m);
			for(int i = 0; i <= mid; i++) now[vec[i]] = 1;
			if(ask(now) > mn_dist) r = mid;
			else l = mid + 1;
		}

		int a = u[vec[r]], b = v[vec[r]];
		if(par[b] == a) swap(a, b);
		ans.emplace_back(rot = a);
	}
	//printf("answer = %d %d\n", ans[0], ans[1]);

	answer(ans[0], ans[1]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5760 KB Output is correct
2 Correct 4 ms 5760 KB Output is correct
3 Correct 4 ms 5760 KB Output is correct
4 Correct 4 ms 5760 KB Output is correct
5 Correct 4 ms 5760 KB Output is correct
6 Correct 4 ms 5760 KB Output is correct
7 Correct 4 ms 5760 KB Output is correct
8 Correct 4 ms 5760 KB Output is correct
9 Correct 4 ms 5760 KB Output is correct
10 Correct 4 ms 5760 KB Output is correct
11 Correct 4 ms 5760 KB Output is correct
12 Correct 4 ms 5760 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5888 KB Output is correct
2 Correct 19 ms 6656 KB Output is correct
3 Correct 165 ms 12572 KB Output is correct
4 Correct 202 ms 12576 KB Output is correct
5 Correct 216 ms 12568 KB Output is correct
6 Correct 194 ms 12612 KB Output is correct
7 Correct 172 ms 12608 KB Output is correct
8 Correct 165 ms 12584 KB Output is correct
9 Correct 203 ms 12576 KB Output is correct
10 Correct 161 ms 12580 KB Output is correct
11 Correct 219 ms 12232 KB Output is correct
12 Correct 178 ms 12020 KB Output is correct
13 Correct 180 ms 12024 KB Output is correct
14 Correct 169 ms 12028 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6580 KB Output is correct
2 Correct 31 ms 7288 KB Output is correct
3 Correct 42 ms 8040 KB Output is correct
4 Correct 121 ms 12020 KB Output is correct
5 Correct 124 ms 12020 KB Output is correct
6 Correct 121 ms 12028 KB Output is correct
7 Correct 116 ms 12032 KB Output is correct
8 Correct 134 ms 12056 KB Output is correct
9 Correct 123 ms 12064 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5908 KB Output is correct
2 Correct 21 ms 6656 KB Output is correct
3 Correct 134 ms 11240 KB Output is correct
4 Correct 201 ms 12588 KB Output is correct
5 Correct 171 ms 12564 KB Output is correct
6 Correct 162 ms 12576 KB Output is correct
7 Correct 185 ms 12604 KB Output is correct
8 Correct 172 ms 12724 KB Output is correct
9 Correct 178 ms 12580 KB Output is correct
10 Correct 169 ms 12684 KB Output is correct
11 Correct 197 ms 12032 KB Output is correct
12 Correct 164 ms 12260 KB Output is correct
13 Correct 176 ms 12120 KB Output is correct
14 Correct 168 ms 12024 KB Output is correct
15 Correct 162 ms 12836 KB Output is correct
16 Correct 161 ms 12708 KB Output is correct
17 Correct 169 ms 12028 KB Output is correct
18 Correct 172 ms 12024 KB Output is correct
19 Correct 164 ms 12696 KB Output is correct
20 Correct 159 ms 12056 KB Output is correct
21 Correct 139 ms 13244 KB Output is correct
22 Correct 124 ms 13172 KB Output is correct
23 Correct 137 ms 12860 KB Output is correct
24 Correct 132 ms 12816 KB Output is correct
25 Correct 162 ms 12184 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6656 KB Output is correct
2 Correct 22 ms 6656 KB Output is correct
3 Correct 179 ms 13060 KB Output is correct
4 Correct 199 ms 13944 KB Output is correct
5 Incorrect 222 ms 15068 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 6648 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -