#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
#define all(x) (x).begin(), (x).end()
const int MAXN = 1e6 + 10;
bool bad[MAXN];
int askcnt = 0;
int from[MAXN], to[MAXN], n, m, par[MAXN], mn;
vector<int> adj[MAXN], dfs_order, fuck;
inline int f(int ind, int v) {
return from[ind] ^ to[ind] ^ v;
}
void dfs(int v, int p) {
dfs_order.push_back(v);
for (int ind : adj[v]) {
int u = f(ind, v);
if (u == p) continue;
if (bad[u]) continue;
par[u] = ind;
dfs(u, v);
}
}
inline vector<int> seg(int l, int r) {
vector<int> ans;
for (int i = l; i <= r; i++)
ans.push_back(par[dfs_order[i]]);
return ans;
}
inline int get(vector<int> vec) {
askcnt++;
assert(askcnt <= 90);
vector<int> W(m);
for (int i = 0; i < m; i++) W[i] = 1;
for (int e : fuck)
W[e] = 0;
for (int e : vec)
W[e] = 1;
return ask(W);
}
inline int getp(vector<int> vec) {
askcnt++;
assert(askcnt <= 90);
vector<int> W(m);
for (int i = 0; i < m; i++)
W[i] = 1;
for (int e : vec)
W[e] = 0;
return ask(W);
}
inline int get(int l, int r) {
return get(seg(l, r));
}
inline int getp(int l, int r) {
return getp(seg(l, r));
}
inline int find(int root) {
par[root] = -1;
dfs_order.clear();
dfs(root, root);
int l = 1, r = int(dfs_order.size()) - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (getp(1, mid) == mn) r = mid;
else l = mid + 1;
}
return dfs_order[l];
}
int dist[MAXN];
const double Z = 0.4;
inline vector<int> random_spt() {
vector<int> ans;
queue<int> q;
int l = 0, r = n - 1;
while (l < r) {
int len = r - l;
int mid = l + Z * len;
mid = max(mid, l);
mid = min(mid, r - 1);
vector<int> W(m);
for (int i = 0; i < m; i++)
if (from[i] <= mid || to[i] <= mid)
W[i] = 1;
if (ask(W) == mn) {
for (int i = l; i <= mid; i++) bad[i] = true;
l = mid + 1;
} else r = mid;
}
int v = l;
memset(dist, 63, sizeof dist);
q.push(v);
dist[v] = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
for (int ind : adj[v]) {
int u = f(ind, v);
if (dist[u] > dist[v] + 1) {
dist[u] = dist[v] + 1;
q.push(u);
ans.push_back(ind);
}
}
}
return ans;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
m = U.size();
n = N;
for (int i = 0; i < m; i++) {
from[i] = U[i];
to[i] = V[i];
adj[from[i]].push_back(i);
adj[to[i]].push_back(i);
}
for (int i = 0; i < m; i++)
fuck.push_back(i);
mn = get({});
vector<int> tmp = random_spt();
fuck = tmp;
for (int i = 0; i < n; i++) adj[i].clear();
for (int ind : tmp) {
adj[from[ind]].push_back(ind);
adj[to[ind]].push_back(ind);
}
int v = find(0);
int u = find(v);
cerr << u << sep << v << endl;
answer(u, v);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
27672 KB |
Output is correct |
2 |
Correct |
12 ms |
27636 KB |
Output is correct |
3 |
Correct |
14 ms |
27672 KB |
Output is correct |
4 |
Correct |
14 ms |
27680 KB |
Output is correct |
5 |
Correct |
15 ms |
27744 KB |
Output is correct |
6 |
Correct |
15 ms |
27716 KB |
Output is correct |
7 |
Correct |
15 ms |
27728 KB |
Output is correct |
8 |
Correct |
13 ms |
27672 KB |
Output is correct |
9 |
Correct |
15 ms |
27812 KB |
Output is correct |
10 |
Correct |
13 ms |
27688 KB |
Output is correct |
11 |
Correct |
13 ms |
27676 KB |
Output is correct |
12 |
Correct |
13 ms |
27644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
27736 KB |
Output is correct |
2 |
Correct |
25 ms |
28588 KB |
Output is correct |
3 |
Correct |
127 ms |
35064 KB |
Output is correct |
4 |
Correct |
125 ms |
35008 KB |
Output is correct |
5 |
Correct |
147 ms |
35064 KB |
Output is correct |
6 |
Correct |
116 ms |
35088 KB |
Output is correct |
7 |
Correct |
132 ms |
35068 KB |
Output is correct |
8 |
Correct |
121 ms |
34996 KB |
Output is correct |
9 |
Correct |
120 ms |
35072 KB |
Output is correct |
10 |
Correct |
145 ms |
35072 KB |
Output is correct |
11 |
Correct |
130 ms |
36620 KB |
Output is correct |
12 |
Correct |
133 ms |
37576 KB |
Output is correct |
13 |
Correct |
126 ms |
36796 KB |
Output is correct |
14 |
Correct |
129 ms |
36860 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
21 ms |
28384 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
13 ms |
27744 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
28468 KB |
Output is correct |
2 |
Correct |
27 ms |
28640 KB |
Output is correct |
3 |
Incorrect |
117 ms |
35284 KB |
Output is incorrect: {s, t} is wrong. |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
28628 KB |
Output is correct |
2 |
Correct |
27 ms |
28644 KB |
Output is correct |
3 |
Incorrect |
122 ms |
34376 KB |
Output is incorrect: {s, t} is wrong. |
4 |
Halted |
0 ms |
0 KB |
- |