//#pragma optimize("Ofast")
//#pragma optimize("unroll-loops")
//#pragma traget("avx,avx2")
#include "highway.h"
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define el '\n'
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define point pair <ll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
#include <random>
mt19937 rnd(time(0));
const int maxn = 9e4;
vector <pair <int, int>> gr[maxn];
int from[maxn], dist[maxn];
void find_pair(int n, vector <int> u, vector <int> v, int a, int b) {
int m = u.size();
vector <int> q(m);
ll len = ask(q);
int l = -1, r = m;
while (l + 1 < r) {
int mid = (l + r) >> 1;
for (int i = 0; i <= mid; i++)
q[i] = 1;
for (int i = mid + 1; i < m; i++)
q[i] = 0;
if (ask(q) == len) l = mid;
else r = mid;
}
for (int i = 0; i < m; i++)
q[i] = 1;
q[r] = 0;
for (int i = 0; i < m; i++) {
if (i == r)
continue;
gr[u[i]].pb({v[i], i});
gr[v[i]].pb({u[i], i});
}
vector <int> left, right;
for (int i = 0; i < n; i++)
from[i] = -1;
from[u[r]] = u[r];
from[v[r]] = v[r];
queue <int> qu;
qu.push(u[r]);
qu.push(v[r]);
while (!qu.empty()) {
int ver = qu.front();
qu.pop();
for (auto &[to, id] : gr[ver]) {
if (from[to] != -1)
continue;
from[to] = from[ver];
dist[to] = dist[ver] + 1;
if (from[to] == u[r]) left.pb(id);
else right.pb(id);
q[id] = 0;
qu.push(to);
}
}
vector <int> now;
int s = u[r], t = v[r];
now = q;
for (int i : left)
now[i] = 1;
ll len_left = ask(now);
l = -2, r = left.size();
while (l + 1 < r) {
int mid = (l + r) / 2;
now = q;
for (int i = 0; i <= mid; i++)
now[left[i]] = 1;
if (ask(now) == len_left) r = mid;
else l = mid;
}
if (r != -1) {
if (dist[u[left[r]]] > dist[v[left[r]]]) s = u[left[r]];
else s = v[left[r]];
}
now = q;
for (int i : right)
now[i] = 1;
ll len_right = ask(now);
l = -2, r = right.size();
while (l + 1 < r) {
int mid = (l + r) / 2;
now = q;
for (int i = 0; i <= mid; i++)
now[right[i]] = 1;
if (ask(now) == len_right) r = mid;
else l = mid;
}
if (r != -1) {
if (dist[u[right[r]]] > dist[v[right[r]]]) t = u[right[r]];
else t = v[right[r]];
}
answer(s, t);
return;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2904 KB |
Output is correct |
2 |
Correct |
1 ms |
2904 KB |
Output is correct |
3 |
Correct |
1 ms |
2904 KB |
Output is correct |
4 |
Correct |
1 ms |
2904 KB |
Output is correct |
5 |
Correct |
1 ms |
2904 KB |
Output is correct |
6 |
Correct |
1 ms |
2904 KB |
Output is correct |
7 |
Correct |
1 ms |
2904 KB |
Output is correct |
8 |
Correct |
1 ms |
2904 KB |
Output is correct |
9 |
Correct |
2 ms |
3104 KB |
Output is correct |
10 |
Correct |
1 ms |
2904 KB |
Output is correct |
11 |
Correct |
1 ms |
2904 KB |
Output is correct |
12 |
Correct |
1 ms |
2904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3160 KB |
Output is correct |
2 |
Correct |
8 ms |
3672 KB |
Output is correct |
3 |
Correct |
85 ms |
9256 KB |
Output is correct |
4 |
Correct |
86 ms |
9564 KB |
Output is correct |
5 |
Correct |
88 ms |
9268 KB |
Output is correct |
6 |
Correct |
75 ms |
9256 KB |
Output is correct |
7 |
Correct |
82 ms |
9360 KB |
Output is correct |
8 |
Correct |
72 ms |
9268 KB |
Output is correct |
9 |
Correct |
72 ms |
9264 KB |
Output is correct |
10 |
Correct |
78 ms |
9456 KB |
Output is correct |
11 |
Correct |
72 ms |
8692 KB |
Output is correct |
12 |
Correct |
79 ms |
8716 KB |
Output is correct |
13 |
Correct |
80 ms |
8716 KB |
Output is correct |
14 |
Correct |
99 ms |
8732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
3672 KB |
Output is correct |
2 |
Correct |
15 ms |
4184 KB |
Output is correct |
3 |
Correct |
21 ms |
4896 KB |
Output is correct |
4 |
Correct |
63 ms |
8760 KB |
Output is correct |
5 |
Correct |
80 ms |
8652 KB |
Output is correct |
6 |
Correct |
69 ms |
8676 KB |
Output is correct |
7 |
Correct |
67 ms |
8664 KB |
Output is correct |
8 |
Correct |
62 ms |
8624 KB |
Output is correct |
9 |
Correct |
67 ms |
8664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3160 KB |
Output is correct |
2 |
Correct |
8 ms |
3828 KB |
Output is correct |
3 |
Correct |
55 ms |
7880 KB |
Output is correct |
4 |
Correct |
73 ms |
9256 KB |
Output is correct |
5 |
Correct |
70 ms |
9260 KB |
Output is correct |
6 |
Correct |
70 ms |
9460 KB |
Output is correct |
7 |
Correct |
73 ms |
9284 KB |
Output is correct |
8 |
Correct |
59 ms |
9384 KB |
Output is correct |
9 |
Correct |
88 ms |
9704 KB |
Output is correct |
10 |
Correct |
80 ms |
9516 KB |
Output is correct |
11 |
Correct |
84 ms |
8680 KB |
Output is correct |
12 |
Correct |
82 ms |
8696 KB |
Output is correct |
13 |
Correct |
82 ms |
8680 KB |
Output is correct |
14 |
Correct |
82 ms |
9164 KB |
Output is correct |
15 |
Correct |
68 ms |
9268 KB |
Output is correct |
16 |
Correct |
78 ms |
9216 KB |
Output is correct |
17 |
Correct |
86 ms |
8984 KB |
Output is correct |
18 |
Correct |
87 ms |
8700 KB |
Output is correct |
19 |
Correct |
70 ms |
9156 KB |
Output is correct |
20 |
Correct |
72 ms |
8648 KB |
Output is correct |
21 |
Correct |
68 ms |
9788 KB |
Output is correct |
22 |
Correct |
65 ms |
9792 KB |
Output is correct |
23 |
Correct |
75 ms |
9644 KB |
Output is correct |
24 |
Correct |
73 ms |
9800 KB |
Output is correct |
25 |
Correct |
82 ms |
8856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
11 ms |
3672 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
3672 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |