#include "highway.h"
#include <bits/stdc++.h>
const int MAXN = 9e4;
using namespace std;
typedef pair<int, int> pii;
vector<int> weight;
int n, m;
vector<pii> edges[MAXN];
int base;
bool vis[MAXN];
int sz[MAXN];
int a, b;
void make_sz(int cur, int p = -1) {
sz[cur] = 1;
for (pii e: edges[cur]) {
int nxt = e.first;
if (nxt == p || vis[nxt]) continue;
make_sz(nxt, cur);
sz[cur] += sz[nxt];
}
}
vector<int> res;
void deactivate(int v) {
for (pii e: edges[v]) weight[e.second] = 1;
}
void activate(int v) {
for (pii e: edges[v]) weight[e.second] = 0;
}
int find(int cur, int dest, int p = -1) {
for (pii e: edges[cur]) {
if (e.first == p) continue;
if (e.first == dest) return cur;
int m = find(e.first, dest, cur);
if (m != -1) return m;
}
return -1;
}
void set_sub(int cur, bool v, int p = -1) {
if (v) deactivate(cur);
else activate(cur);
for (pii e: edges[cur]) {
if (vis[e.first] || e.first == p) continue;
set_sub(e.first, v, cur);
}
}
void solve(int cur, int num = 2, int oth = -1) {
if (num == 0) return;
make_sz(cur);
int tot = sz[cur];
if (tot == 1) {
assert(num < 2);
res.push_back(cur);
vis[cur] = 1;
return;
}
int p = -1;
bool f = 0;
while (!f) {
f = 1;
for (pii e: edges[cur]) {
int nxt = e.first;
if (vis[nxt] || nxt == p) continue;
if (2*sz[nxt] >= tot) {
f = 0;
p = cur;
cur = nxt;
break;
}
}
}
vis[cur] = 1;
deactivate(cur);
int val = ask(weight);
activate(cur);
if (val == base+b-a) {
res.push_back(cur);
val = base;
num--;
oth = cur;
if (num == 0) return;
}
if (val == base) { // figure out which subtree
vector<pii> adj;
for (pii e: edges[cur]) {
if (vis[e.first]) continue;
adj.push_back(e);
}
int l = 0;
int r = adj.size();
assert(adj.size() >= 1);
while (r > l+1) {
int mid = (l+r)/2;
for (int i = l; i < mid; i++) set_sub(adj[i].first, 1);
int v = ask(weight);
for (int i = l; i < mid; i++) set_sub(adj[i].first, 0);
if (v > base) {
r = mid;
}
else {
l = mid;
}
}
solve(adj[l].first, num, oth);
}
else {
while (num > 0) {
int ig_dir = -1;
if (num == 1) ig_dir = find(oth, cur);
vector<pii> adj;
for (pii e: edges[cur]) {
if (vis[e.first] || e.first == ig_dir) continue;
adj.push_back(e);
}
int l = 0;
int r = adj.size();
assert(adj.size() >= num);
while (r > l+1) {
int mid = (l+r)/2;
for (int i = l; i < mid; i++) weight[adj[i].second] = 1;
int v = ask(weight);
for (int i = l; i < mid; i++) weight[adj[i].second] = 0;
if (v > base) {
r = mid;
}
else {
l = mid;
}
}
solve(adj[l].first, 1, cur);
num--;
oth = res[0];
}
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
a = A; b = B;
// assert(U.size() == N-1);
n = N;
m = U.size();
for (int i = 0; i < m; i++) {
edges[U[i]].push_back(pii(V[i], i));
edges[V[i]].push_back(pii(U[i], i));
}
weight = vector<int>(m);
fill(weight.begin(), weight.end(), 0);
base = ask(weight);
solve(0); assert(res.size() == 2);
answer(res[0], res[1]);
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from highway.cpp:3:
highway.cpp: In function 'void solve(int, int, int)':
highway.cpp:127:31: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
127 | assert(adj.size() >= num);
| ~~~~~~~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2424 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2420 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2384 KB |
Output is correct |
| 2 |
Correct |
11 ms |
2996 KB |
Output is correct |
| 3 |
Incorrect |
106 ms |
7904 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
3664 KB |
Output is correct |
| 2 |
Correct |
20 ms |
4936 KB |
Output is correct |
| 3 |
Correct |
36 ms |
6356 KB |
Output is correct |
| 4 |
Correct |
96 ms |
14404 KB |
Output is correct |
| 5 |
Correct |
85 ms |
14364 KB |
Output is correct |
| 6 |
Correct |
69 ms |
14536 KB |
Output is correct |
| 7 |
Correct |
78 ms |
14404 KB |
Output is correct |
| 8 |
Correct |
93 ms |
14424 KB |
Output is correct |
| 9 |
Incorrect |
79 ms |
14384 KB |
Output is incorrect: {s, t} is wrong. |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2384 KB |
Output is correct |
| 2 |
Correct |
12 ms |
3000 KB |
Output is correct |
| 3 |
Correct |
70 ms |
6692 KB |
Output is correct |
| 4 |
Correct |
137 ms |
7900 KB |
Output is correct |
| 5 |
Correct |
70 ms |
7920 KB |
Output is correct |
| 6 |
Correct |
130 ms |
7932 KB |
Output is correct |
| 7 |
Correct |
72 ms |
7920 KB |
Output is correct |
| 8 |
Correct |
101 ms |
7916 KB |
Output is correct |
| 9 |
Incorrect |
132 ms |
7944 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
143 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
137 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
