oj.uz

Submission #818089

# Submission time Handle Problem Language Result Execution time Memory
818089 2023-08-10T01:57:49 Z pavement Highway Tolls (IOI18_highway) C++17
18 / 100
 174 ms 4696 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define eb emplace_back
#define mt make_tuple

using ll = long long;
using ii = pair<int, int>;

int M;
vector<int> U, V;

vector<int> gen_edges(vector<int> &in_grp) {
	vector<int> ret(M, 0);
	for (int i = 0; i < M; i++) {
		ret[i] = (in_grp[U[i]] == in_grp[V[i]]);
	}
	return ret;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	M = (int)U.size();
	::U = U;
	::V = V;
	int s_xor_t = 0;
	vector<int> init_grp;
	for (int bit = 0; (1 << bit) < N; bit++) {
		vector<int> in_grp(N, 0);
		for (int i = 0; i < N; i++) {
			in_grp[i] = !!(i & (1 << bit));
		}
		auto edges = gen_edges(in_grp);
		if (ask(edges) % 2) {
			// S and T are in different sets
			init_grp = in_grp;
			s_xor_t ^= (1 << bit);
		}
	}
	assert(!init_grp.empty());
	while (count(init_grp.begin(), init_grp.end(), 1) > 1) {
		int cnt = count(init_grp.begin(), init_grp.end(), 1) / 2;
		vector<int> new_init_grp(N, 0);
		for (int i = 0; i < N; i++) {
			if (init_grp[i] && cnt) {
				cnt--;
				new_init_grp[i] = 1;
			} else {
				new_init_grp[i] = 0;
			}
		}
		auto edges = gen_edges(new_init_grp);
		if (ask(edges) % 2 == 0) {
			for (int i = 0; i < N; i++) {
				new_init_grp[i] ^= init_grp[i];
			}
		}
		init_grp = new_init_grp;
	}
	int S = find(init_grp.begin(), init_grp.end(), 1) - init_grp.begin(), T = S ^ s_xor_t;
	answer(S, T);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Runtime error 1 ms 432 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 464 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 976 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Runtime error 9 ms 1004 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 672 KB Output is correct
2 Correct 8 ms 592 KB Output is correct
3 Correct 96 ms 3824 KB Output is correct
4 Correct 110 ms 4092 KB Output is correct
5 Correct 124 ms 4580 KB Output is correct
6 Correct 97 ms 4604 KB Output is correct
7 Correct 96 ms 4592 KB Output is correct
8 Correct 123 ms 4596 KB Output is correct
9 Correct 120 ms 4116 KB Output is correct
10 Correct 124 ms 4072 KB Output is correct
11 Correct 100 ms 4228 KB Output is correct
12 Correct 95 ms 4412 KB Output is correct
13 Correct 119 ms 4508 KB Output is correct
14 Correct 102 ms 4608 KB Output is correct
15 Correct 174 ms 4696 KB Output is correct
16 Correct 109 ms 4184 KB Output is correct
17 Correct 63 ms 3476 KB Output is correct
18 Correct 67 ms 3520 KB Output is correct
19 Correct 73 ms 3560 KB Output is correct
20 Correct 69 ms 3536 KB Output is correct
21 Correct 137 ms 4588 KB Output is correct

Subtask #6
0 / 31.0

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