oj.uz

Submission #1010481

# Submission time Handle Problem Language Result Execution time Memory
1010481 2024-06-29T06:54:37 Z 정민찬(#10827) Highway Tolls (IOI18_highway) C++17
51 / 100
 379 ms 13524 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

long long ask(const std::vector<int> &w);
void answer(int s, int t);

vector<vector<pair<int,int>>> adj;
vector<int> poss;
vector<int> sz;

int getSize(int x, int p) {
	sz[x] = poss[x];
	for (auto &[y, z] : adj[x]) {
		if (y == p) continue;
		sz[x] += getSize(y, x);
	}
	return sz[x];
}

vector<int> cur;
int cnt;
vector<int> qry;

void getCand(int x, int p, int e) {
	if (poss[x] && cnt >= sz[x]) {
		cur[x] = 1;
		qry[e] = 1;
		cnt --;
	}
	for (auto &[y, z] : adj[x]) {
		if (y == p) continue;
		getCand(y, x, z);
	}
}

bool check(int x, int p, int tar) {
	if (x == tar) return true;
	for (auto &[y, z] : adj[x]) {
		if (y == p) continue;
		if (check(y, x, tar))
			return true;
	}
	return false;
}

void del(int x, int p) {
	poss[x] = 0;
	for (auto &[y, z] : adj[x]) {
		if (y == p) continue;
		del(y, x);
	}
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	adj.resize(N);
	for (int i=0; i<N-1; i++) {
		adj[U[i]].push_back({V[i], i});
		adj[V[i]].push_back({U[i], i});
	}
	int mndist = ask(vector<int>(N-1, 0));
	int s = 0, e = N-1;
	while (s < e) {
		int mid = s + e >> 1;
		vector<int> w(N-1, 0);
		for (int i=s; i<=mid; i++) {
			for (auto &[j, k] : adj[i]) {
				w[k] = 1;
			}
		}
		int ret = ask(w);
		if (ret == mndist) s = mid + 1;
		else e = mid;
	}
	int rt = s;
	poss.assign(N, 1);
	sz.assign(N, 0);
	cur.assign(N, 0);
	qry.assign(N-1, 0);
	while (true) {
		getSize(rt, -1);
		if (sz[rt] == 1) break;
		cnt = sz[rt] / 2;
		fill(cur.begin(), cur.end(), 0);
		fill(qry.begin(), qry.end(), 0);
		getCand(rt, -1, -1);
		assert(cnt == 0);
		int ret = ask(qry);
		if (ret == mndist) {
			for (int i=0; i<N; i++) {
				if (cur[i]) {
					poss[i] = 0;
				}
			}
		}
		else {
			for (int i=0; i<N; i++) {
				if (!cur[i]) {
					poss[i] = 0;
				}
			}
		}
	}
	int u, v;
	for (int i=0; i<N; i++) {
		if (poss[i]) {
			u = i;
			break;
		}
	}
	fill(poss.begin(), poss.end(), 1);
	for (auto &[x, _] : adj[rt]) {
		if (check(x, rt, u)) {
			del(x, rt);
		}
	}
	while (true) {
		getSize(rt, -1);
		if (sz[rt] == 1) break;
		cnt = sz[rt] / 2;
		fill(cur.begin(), cur.end(), 0);
		fill(qry.begin(), qry.end(), 0);
		getCand(rt, -1, -1);
		assert(cnt == 0);
		int ret = ask(qry);
		if (ret == mndist) {
			for (int i=0; i<N; i++) {
				if (cur[i]) {
					poss[i] = 0;
				}
			}
		}
		else {
			for (int i=0; i<N; i++) {
				if (!cur[i]) {
					poss[i] = 0;
				}
			}
		}
	}
	for (int i=0; i<N; i++) {
		if (poss[i]) {
			v = i;
			break;
		}
	}
	answer(u, v);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:65:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   int mid = s + e >> 1;
      |             ~~^~~
highway.cpp:148:8: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
  148 |  answer(u, v);
      |  ~~~~~~^~~~~~
highway.cpp:114:12: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
  114 |   if (check(x, rt, u)) {
      |       ~~~~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 13 ms 1376 KB Output is correct
3 Correct 166 ms 8724 KB Output is correct
4 Correct 165 ms 8848 KB Output is correct
5 Correct 146 ms 8692 KB Output is correct
6 Correct 161 ms 8728 KB Output is correct
7 Correct 153 ms 8736 KB Output is correct
8 Correct 168 ms 8600 KB Output is correct
9 Correct 165 ms 8600 KB Output is correct
10 Correct 162 ms 8728 KB Output is correct
11 Correct 319 ms 9768 KB Output is correct
12 Correct 250 ms 10120 KB Output is correct
13 Correct 296 ms 9664 KB Output is correct
14 Correct 350 ms 9536 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1624 KB Output is correct
2 Correct 20 ms 3012 KB Output is correct
3 Correct 32 ms 4496 KB Output is correct
4 Correct 111 ms 11516 KB Output is correct
5 Correct 103 ms 11500 KB Output is correct
6 Correct 111 ms 12516 KB Output is correct
7 Correct 118 ms 13524 KB Output is correct
8 Correct 113 ms 12256 KB Output is correct
9 Correct 113 ms 12284 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 19 ms 1276 KB Output is correct
3 Correct 186 ms 6892 KB Output is correct
4 Correct 240 ms 8724 KB Output is correct
5 Correct 263 ms 9124 KB Output is correct
6 Correct 201 ms 8732 KB Output is correct
7 Correct 153 ms 8728 KB Output is correct
8 Correct 234 ms 8720 KB Output is correct
9 Correct 205 ms 8732 KB Output is correct
10 Correct 153 ms 8588 KB Output is correct
11 Correct 379 ms 9160 KB Output is correct
12 Correct 353 ms 9732 KB Output is correct
13 Correct 375 ms 9384 KB Output is correct
14 Correct 364 ms 10084 KB Output is correct
15 Correct 158 ms 8600 KB Output is correct
16 Correct 238 ms 8860 KB Output is correct
17 Correct 373 ms 9140 KB Output is correct
18 Correct 303 ms 9976 KB Output is correct
19 Correct 178 ms 8768 KB Output is correct
20 Correct 338 ms 10332 KB Output is correct
21 Correct 107 ms 8956 KB Output is correct
22 Correct 80 ms 8828 KB Output is correct
23 Correct 104 ms 8868 KB Output is correct
24 Correct 136 ms 9328 KB Output is correct
25 Correct 316 ms 12968 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1112 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1112 KB Incorrect
2 Halted 0 ms 0 KB -