#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define all(a) (a).begin(),(a).end()
#define For(i,a,b) for(auto i=(a);i<(b);i++)
#define FOR(i,b) For(i,0,b)
#define Rev(i,a,b) for(auto i=(a);i>(b);i--)
#define REV(i,a) Rev(i,a,-1)
#define FORE(i,a) for(auto&&i:a)
#define sz(a) (int((a).size()))
#define MIN(a,b) ((a)=min((a),(b)))
#define MAX(a,b) ((a)=max((a),(b)))
using ll=long long;using ld=long double;using uint=unsigned int;using ull=unsigned long long;
using pii=pair<int,int>;using pll=pair<ll,ll>;using pill=pair<int,ll>;using plli=pair<ll,int>;using pdd=pair<double,double>;using pld=pair<ld,ld>;
constexpr const char nl='\n',sp=' ';constexpr const int INT_INF=0x3f3f3f3f;constexpr const ll LL_INF=0x3f3f3f3f3f3f3f3f;
constexpr const double D_INF=numeric_limits<double>::infinity();constexpr const ld LD_INF=numeric_limits<ld>::infinity();constexpr const double EPS=1e-9;
const int MAXN = 90005, MAXM = 130005;
int q[MAXN], to[MAXN];
bool good[MAXM];
vector<int> adj[MAXN];
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
int M = sz(U), front, back, s = 0, lo = 0, hi = M - 1, mid, v;
FOR(i, M) {
adj[U[i]].pb(i);
adj[V[i]].pb(i);
}
vector<int> Q(M, 0);
ll DA = ask(Q);
while (lo < hi) {
mid = lo + (hi - lo) / 2;
FOR(i, M) Q[i] = i <= mid;
if (ask(Q) == DA) lo = mid + 1;
else hi = mid;
}
s = U[lo];
vector<int> ans;
fill(good, good + M, 1);
FOR(_, 2) {
front = 0, back = 0, lo = 1, hi = N - 1;
fill(to, to + N, -1);
to[q[back++] = s] = -INT_INF;
while (front < back) FORE(e, adj[v = q[front++]]) if (good[e] && to[v ^ U[e] ^ V[e]] == -1) good[to[q[back++] = v ^ U[e] ^ V[e]] = e] = 0;
while (lo <= hi) {
mid = lo + (hi - lo) / 2;
fill(all(Q), 0);
For(i, mid, N) Q[to[q[i]]] = 1;
if (ask(Q) == DA) hi = mid - 1;
else lo = mid + 1;
}
FOR(i, M) good[i] ^= 1;
ans.pb(s = q[hi]);
}
answer(ans[0], ans[1]);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2444 KB |
Output is correct |
2 |
Correct |
4 ms |
2424 KB |
Output is correct |
3 |
Correct |
4 ms |
2464 KB |
Output is correct |
4 |
Correct |
4 ms |
2424 KB |
Output is correct |
5 |
Correct |
4 ms |
2444 KB |
Output is correct |
6 |
Correct |
4 ms |
2424 KB |
Output is correct |
7 |
Correct |
4 ms |
2440 KB |
Output is correct |
8 |
Correct |
4 ms |
2452 KB |
Output is correct |
9 |
Correct |
4 ms |
2448 KB |
Output is correct |
10 |
Correct |
4 ms |
2424 KB |
Output is correct |
11 |
Correct |
4 ms |
2424 KB |
Output is correct |
12 |
Correct |
4 ms |
2424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2492 KB |
Output is correct |
2 |
Correct |
26 ms |
3020 KB |
Output is correct |
3 |
Correct |
253 ms |
8024 KB |
Output is correct |
4 |
Correct |
217 ms |
8040 KB |
Output is correct |
5 |
Correct |
261 ms |
8040 KB |
Output is correct |
6 |
Correct |
212 ms |
8032 KB |
Output is correct |
7 |
Correct |
255 ms |
8020 KB |
Output is correct |
8 |
Correct |
266 ms |
8104 KB |
Output is correct |
9 |
Correct |
236 ms |
7980 KB |
Output is correct |
10 |
Correct |
253 ms |
7952 KB |
Output is correct |
11 |
Correct |
281 ms |
7932 KB |
Output is correct |
12 |
Correct |
275 ms |
7920 KB |
Output is correct |
13 |
Correct |
281 ms |
7928 KB |
Output is correct |
14 |
Correct |
246 ms |
7832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
2984 KB |
Output is correct |
2 |
Correct |
42 ms |
3588 KB |
Output is correct |
3 |
Correct |
85 ms |
4324 KB |
Output is correct |
4 |
Correct |
167 ms |
7836 KB |
Output is correct |
5 |
Correct |
203 ms |
7868 KB |
Output is correct |
6 |
Correct |
182 ms |
7880 KB |
Output is correct |
7 |
Correct |
178 ms |
7840 KB |
Output is correct |
8 |
Correct |
163 ms |
7832 KB |
Output is correct |
9 |
Correct |
162 ms |
7832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2484 KB |
Output is correct |
2 |
Correct |
25 ms |
2960 KB |
Output is correct |
3 |
Correct |
192 ms |
6736 KB |
Output is correct |
4 |
Correct |
266 ms |
7944 KB |
Output is correct |
5 |
Correct |
272 ms |
7920 KB |
Output is correct |
6 |
Correct |
275 ms |
8000 KB |
Output is correct |
7 |
Correct |
279 ms |
8044 KB |
Output is correct |
8 |
Correct |
263 ms |
7944 KB |
Output is correct |
9 |
Correct |
259 ms |
7940 KB |
Output is correct |
10 |
Correct |
279 ms |
8032 KB |
Output is correct |
11 |
Correct |
268 ms |
8016 KB |
Output is correct |
12 |
Correct |
250 ms |
7844 KB |
Output is correct |
13 |
Correct |
265 ms |
7884 KB |
Output is correct |
14 |
Correct |
292 ms |
7892 KB |
Output is correct |
15 |
Correct |
301 ms |
7944 KB |
Output is correct |
16 |
Correct |
281 ms |
7944 KB |
Output is correct |
17 |
Correct |
266 ms |
7836 KB |
Output is correct |
18 |
Correct |
269 ms |
7920 KB |
Output is correct |
19 |
Correct |
254 ms |
7948 KB |
Output is correct |
20 |
Correct |
281 ms |
7832 KB |
Output is correct |
21 |
Correct |
197 ms |
8304 KB |
Output is correct |
22 |
Correct |
208 ms |
8188 KB |
Output is correct |
23 |
Correct |
211 ms |
8180 KB |
Output is correct |
24 |
Correct |
230 ms |
8244 KB |
Output is correct |
25 |
Correct |
258 ms |
7896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
2980 KB |
Output is correct |
2 |
Correct |
18 ms |
3012 KB |
Output is correct |
3 |
Correct |
277 ms |
8172 KB |
Output is correct |
4 |
Correct |
302 ms |
8520 KB |
Output is correct |
5 |
Correct |
373 ms |
8940 KB |
Output is correct |
6 |
Correct |
398 ms |
8956 KB |
Output is correct |
7 |
Correct |
386 ms |
8992 KB |
Output is correct |
8 |
Correct |
339 ms |
8932 KB |
Output is correct |
9 |
Incorrect |
263 ms |
7120 KB |
Output is incorrect: {s, t} is wrong. |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
3072 KB |
Output is correct |
2 |
Correct |
32 ms |
3040 KB |
Output is correct |
3 |
Partially correct |
271 ms |
8288 KB |
Output is partially correct |
4 |
Correct |
316 ms |
8288 KB |
Output is correct |
5 |
Partially correct |
312 ms |
8424 KB |
Output is partially correct |
6 |
Correct |
354 ms |
8924 KB |
Output is correct |
7 |
Partially correct |
300 ms |
8292 KB |
Output is partially correct |
8 |
Partially correct |
297 ms |
8304 KB |
Output is partially correct |
9 |
Incorrect |
332 ms |
8480 KB |
Output is incorrect: {s, t} is wrong. |
10 |
Halted |
0 ms |
0 KB |
- |