#include <bits/stdc++.h>
#include "highway.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 9e4+5;
ll base;
int n, m;
vector< ii > adj[maxn];
int dist[maxn];
void bfs(int s)
{
for(int i = 0; i< n; i++) dist[i] = 1e9;
dist[s] = 0;
queue<int> q; q.push(s);
while(!q.empty())
{
int u = q.front(); q.pop();
for(auto kk : adj[u])
{
int v = kk.X;
if(dist[v]> dist[u]+1)
{
dist[v] = dist[u]+1;
q.push(v);
}
}
}
}
bool cmp(int a, int b)
{
return dist[a]< dist[b];
}
int F(vector<int> &vec)
{
int lo = 0, hi = n-1;
while(lo< hi)
{
int mid = (lo+hi)/2;
vector<bool> mark(n, false);
vector<int> send(m, 1);
for(int i = 0; i<= mid; i++) mark[vec[i]] = true;
for(int i = 0; i<= mid; i++)
{
int u = vec[i];
for(auto kk : adj[u])
{
int v = kk.X, id = kk.Y;
if(mark[u] && mark[v])
{
send[id] = 0;
}
}
}
ll exp = ask(send);
if(exp == base) hi = mid;
else lo = mid+1;
}
return lo;
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
n = N;
m = U.size();
for(int i = 0; i< m; i++)
{
adj[U[i]].pb({V[i], i});
adj[V[i]].pb({U[i], i});
}
base = ask(vector<int>(m, 0));
vector<int> foo;
for(int i = 0; i< n; i++) foo.pb(i);
int v = foo[F(foo)];
bfs(v); sort(foo.begin(), foo.end(), cmp);
int ad = F(foo);
int T = foo[ad];
foo.erase(foo.begin()+ad+1, foo.end());
bfs(T); sort(foo.begin(), foo.end(), cmp);
int S = foo[F(foo)];
answer(S, T);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2524 KB |
Output is correct |
2 |
Correct |
4 ms |
2424 KB |
Output is correct |
3 |
Correct |
4 ms |
2424 KB |
Output is correct |
4 |
Correct |
4 ms |
2424 KB |
Output is correct |
5 |
Correct |
4 ms |
2424 KB |
Output is correct |
6 |
Correct |
4 ms |
2424 KB |
Output is correct |
7 |
Correct |
4 ms |
2520 KB |
Output is correct |
8 |
Correct |
4 ms |
2436 KB |
Output is correct |
9 |
Correct |
4 ms |
2436 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 |
2572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2424 KB |
Output is correct |
2 |
Correct |
22 ms |
3120 KB |
Output is correct |
3 |
Correct |
557 ms |
8464 KB |
Output is correct |
4 |
Correct |
680 ms |
8548 KB |
Output is correct |
5 |
Correct |
619 ms |
8568 KB |
Output is correct |
6 |
Correct |
717 ms |
8520 KB |
Output is correct |
7 |
Correct |
362 ms |
8468 KB |
Output is correct |
8 |
Correct |
414 ms |
8448 KB |
Output is correct |
9 |
Correct |
331 ms |
8536 KB |
Output is correct |
10 |
Correct |
672 ms |
8464 KB |
Output is correct |
11 |
Correct |
367 ms |
7992 KB |
Output is correct |
12 |
Correct |
500 ms |
8016 KB |
Output is correct |
13 |
Correct |
478 ms |
7960 KB |
Output is correct |
14 |
Correct |
620 ms |
8008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
3120 KB |
Output is correct |
2 |
Correct |
41 ms |
3676 KB |
Output is correct |
3 |
Correct |
62 ms |
4268 KB |
Output is correct |
4 |
Correct |
209 ms |
7892 KB |
Output is correct |
5 |
Correct |
200 ms |
8016 KB |
Output is correct |
6 |
Correct |
232 ms |
7972 KB |
Output is correct |
7 |
Correct |
182 ms |
7900 KB |
Output is correct |
8 |
Correct |
253 ms |
7916 KB |
Output is correct |
9 |
Correct |
234 ms |
7912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2424 KB |
Output is correct |
2 |
Correct |
24 ms |
3120 KB |
Output is correct |
3 |
Correct |
247 ms |
7124 KB |
Output is correct |
4 |
Correct |
374 ms |
8452 KB |
Output is correct |
5 |
Correct |
351 ms |
8556 KB |
Output is correct |
6 |
Correct |
311 ms |
8448 KB |
Output is correct |
7 |
Correct |
314 ms |
8456 KB |
Output is correct |
8 |
Correct |
322 ms |
8548 KB |
Output is correct |
9 |
Correct |
590 ms |
8536 KB |
Output is correct |
10 |
Correct |
497 ms |
8548 KB |
Output is correct |
11 |
Correct |
572 ms |
7900 KB |
Output is correct |
12 |
Correct |
755 ms |
8020 KB |
Output is correct |
13 |
Correct |
544 ms |
8020 KB |
Output is correct |
14 |
Correct |
515 ms |
8016 KB |
Output is correct |
15 |
Correct |
336 ms |
8468 KB |
Output is correct |
16 |
Correct |
332 ms |
8540 KB |
Output is correct |
17 |
Correct |
617 ms |
7952 KB |
Output is correct |
18 |
Correct |
519 ms |
7940 KB |
Output is correct |
19 |
Correct |
313 ms |
8532 KB |
Output is correct |
20 |
Correct |
336 ms |
7992 KB |
Output is correct |
21 |
Correct |
486 ms |
8804 KB |
Output is correct |
22 |
Correct |
358 ms |
8744 KB |
Output is correct |
23 |
Correct |
633 ms |
8704 KB |
Output is correct |
24 |
Correct |
577 ms |
8644 KB |
Output is correct |
25 |
Correct |
778 ms |
7988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
3116 KB |
Output is correct |
2 |
Correct |
29 ms |
3160 KB |
Output is correct |
3 |
Correct |
474 ms |
8796 KB |
Output is correct |
4 |
Correct |
545 ms |
9184 KB |
Output is correct |
5 |
Correct |
626 ms |
10140 KB |
Output is correct |
6 |
Correct |
815 ms |
10156 KB |
Output is correct |
7 |
Correct |
629 ms |
10132 KB |
Output is correct |
8 |
Correct |
774 ms |
10040 KB |
Output is correct |
9 |
Correct |
383 ms |
8240 KB |
Output is correct |
10 |
Correct |
313 ms |
8812 KB |
Output is correct |
11 |
Correct |
410 ms |
9008 KB |
Output is correct |
12 |
Correct |
427 ms |
9772 KB |
Output is correct |
13 |
Correct |
667 ms |
9852 KB |
Output is correct |
14 |
Correct |
837 ms |
10056 KB |
Output is correct |
15 |
Correct |
745 ms |
10088 KB |
Output is correct |
16 |
Correct |
469 ms |
9348 KB |
Output is correct |
17 |
Correct |
497 ms |
8780 KB |
Output is correct |
18 |
Correct |
424 ms |
8976 KB |
Output is correct |
19 |
Correct |
396 ms |
8824 KB |
Output is correct |
20 |
Correct |
391 ms |
8824 KB |
Output is correct |
21 |
Correct |
465 ms |
10128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
3200 KB |
Output is correct |
2 |
Correct |
68 ms |
3168 KB |
Output is correct |
3 |
Partially correct |
328 ms |
8808 KB |
Output is partially correct |
4 |
Partially correct |
632 ms |
9056 KB |
Output is partially correct |
5 |
Partially correct |
688 ms |
9264 KB |
Output is partially correct |
6 |
Correct |
827 ms |
10056 KB |
Output is correct |
7 |
Correct |
382 ms |
8800 KB |
Output is correct |
8 |
Partially correct |
414 ms |
9004 KB |
Output is partially correct |
9 |
Correct |
398 ms |
9264 KB |
Output is correct |
10 |
Partially correct |
474 ms |
10100 KB |
Output is partially correct |
11 |
Correct |
478 ms |
10064 KB |
Output is correct |
12 |
Correct |
422 ms |
10080 KB |
Output is correct |
13 |
Correct |
449 ms |
9020 KB |
Output is correct |
14 |
Correct |
348 ms |
8752 KB |
Output is correct |
15 |
Correct |
386 ms |
9200 KB |
Output is correct |
16 |
Correct |
342 ms |
8732 KB |
Output is correct |
17 |
Correct |
396 ms |
9108 KB |
Output is correct |
18 |
Correct |
355 ms |
8816 KB |
Output is correct |
19 |
Correct |
699 ms |
9736 KB |
Output is correct |
20 |
Correct |
406 ms |
9892 KB |
Output is correct |
21 |
Partially correct |
685 ms |
10096 KB |
Output is partially correct |
22 |
Correct |
674 ms |
10132 KB |
Output is correct |
23 |
Correct |
870 ms |
10036 KB |
Output is correct |
24 |
Partially correct |
459 ms |
10040 KB |
Output is partially correct |
25 |
Correct |
491 ms |
10092 KB |
Output is correct |
26 |
Partially correct |
476 ms |
10056 KB |
Output is partially correct |
27 |
Correct |
496 ms |
8800 KB |
Output is correct |
28 |
Correct |
573 ms |
8908 KB |
Output is correct |
29 |
Correct |
512 ms |
9080 KB |
Output is correct |
30 |
Correct |
710 ms |
8840 KB |
Output is correct |
31 |
Correct |
582 ms |
8884 KB |
Output is correct |
32 |
Partially correct |
403 ms |
8716 KB |
Output is partially correct |
33 |
Partially correct |
551 ms |
9000 KB |
Output is partially correct |
34 |
Correct |
589 ms |
8884 KB |
Output is correct |
35 |
Partially correct |
641 ms |
8872 KB |
Output is partially correct |
36 |
Partially correct |
439 ms |
8744 KB |
Output is partially correct |
37 |
Partially correct |
440 ms |
9076 KB |
Output is partially correct |
38 |
Partially correct |
507 ms |
8908 KB |
Output is partially correct |
39 |
Correct |
566 ms |
10208 KB |
Output is correct |
40 |
Partially correct |
554 ms |
10240 KB |
Output is partially correct |
41 |
Partially correct |
954 ms |
10156 KB |
Output is partially correct |
42 |
Correct |
537 ms |
10212 KB |
Output is correct |