#include "meetings.h"
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;
void Solve(int n)
{
vector <pll> edge;
vector <ll> seen(n, 0);
seen[0]=seen[1]=seen[2]=1;
ll x=Query(0, 1, 2);
if (!seen[x]) seen[x]=1, edge.pb({x, 0}), edge.pb({x, 1}), edge.pb({x, 2});
else for (ll i=0; i<=2; i++) if (i!=x) edge.pb({x, i});
for (ll i=0; i<n; i++)
{
if (seen[i]) continue;
vector <ll> used(n, 0);
vector <vector <ll>> A(n);
for (auto [u, v]:edge)
A[u].pb(v), A[v].pb(u);
auto furthest=[&](ll r)
{
vector <ll> dis(n, -1);
queue <ll> q; q.push(r), dis[r]=0;
pll Max={0, r};
while (sz(q))
{
ll u=q.front(); q.pop();
Max=max(Max, {dis[u], u});
for (ll v:A[u])
if (!used[v] && dis[v]==-1)
dis[v]=dis[u]+1, q.push(v);
}
return Max.se;
};
auto getline=[&](ll root)
{
ll a=furthest(root), b=furthest(a);
if (b==a) return vector <ll>{a};
vector <ll> res, pa(n, -1);
queue <ll> q; q.push(a), pa[a]=a;
while (sz(q))
{
ll u=q.front(); q.pop();
for (ll v:A[u])
if (!used[v] && pa[v]==-1)
pa[v]=u, q.push(v);
}
for (ll crr=b; pa[crr]!=crr; crr=pa[crr])
res.pb(crr); res.pb(a);
return res;
};
for (ll root=0, found=0; !found;)
{
vector <ll> line=getline(root);
if (sz(line)==1) {edge.pb({i, root}), seen[i]=1; break;}
ll x=Query(i, line[0], line.back());
if (seen[x])
{
for (ll j:line) if (j!=x) used[j]=1;
root=x; continue;
}
ll lo=0, hi=sz(line); found=seen[x]=seen[i]=1;
while (hi-lo>1)
{
ll m1=lo+(hi-lo+1)/3, m2=hi-(hi-lo+1)/3, m=Query(x, line[m1-1], line[m2]);
if (m==x) lo=m1, hi=m2;
else if (m==line[m2]) lo=m2+1;
else hi=m1-1;
}
if (hi-lo==1)
{
if (lo==0 && Query(x, line[lo], line[lo+1])==x) lo++;
if (lo && Query(x, line[lo-1], line[lo])!=x) lo++;
}
if (lo==0) edge.pb({x, line[0]});
else if (lo==sz(line)) edge.pb({x, line.back()});
else
{
for (ll i=0; i<sz(edge); i++)
{
auto [u, v]=edge[i];
if ((u==line[lo-1] && v==line[lo])||(u==line[lo] && v==line[lo-1]))
{swap(edge[i], edge.back()), edge.pop_back(); break;}
}
edge.pb({line[lo-1], x}), edge.pb({x, line[lo]});
}
if (x!=i) edge.pb({x, i});
}
}
for (pll &i:edge) if (i.fi>i.se) swap(i.fi, i.se);
for (pll i:edge) Bridge(i.fi, i.se);
}
Compilation message
meetings.cpp: In lambda function:
meetings.cpp:56:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
56 | for (ll crr=b; pa[crr]!=crr; crr=pa[crr])
| ^~~
meetings.cpp:57:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
57 | res.pb(crr); res.pb(a);
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
500 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
596 KB |
Output is correct |
13 |
Correct |
1 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
500 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
596 KB |
Output is correct |
13 |
Correct |
1 ms |
376 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
16 |
Correct |
1 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
1 ms |
344 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
21 |
Correct |
1 ms |
596 KB |
Output is correct |
22 |
Correct |
1 ms |
344 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
1 ms |
344 KB |
Output is correct |
25 |
Correct |
1 ms |
344 KB |
Output is correct |
26 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
500 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
596 KB |
Output is correct |
13 |
Correct |
1 ms |
376 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
16 |
Correct |
1 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
1 ms |
344 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
21 |
Correct |
1 ms |
596 KB |
Output is correct |
22 |
Correct |
1 ms |
344 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
1 ms |
344 KB |
Output is correct |
25 |
Correct |
1 ms |
344 KB |
Output is correct |
26 |
Correct |
1 ms |
344 KB |
Output is correct |
27 |
Correct |
11 ms |
344 KB |
Output is correct |
28 |
Correct |
10 ms |
516 KB |
Output is correct |
29 |
Correct |
11 ms |
344 KB |
Output is correct |
30 |
Correct |
8 ms |
344 KB |
Output is correct |
31 |
Correct |
6 ms |
344 KB |
Output is correct |
32 |
Correct |
9 ms |
536 KB |
Output is correct |
33 |
Correct |
11 ms |
532 KB |
Output is correct |
34 |
Correct |
15 ms |
596 KB |
Output is correct |
35 |
Correct |
15 ms |
600 KB |
Output is correct |
36 |
Correct |
8 ms |
344 KB |
Output is correct |
37 |
Correct |
11 ms |
344 KB |
Output is correct |
38 |
Correct |
14 ms |
536 KB |
Output is correct |
39 |
Correct |
8 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
416 ms |
760 KB |
Output is correct |
2 |
Correct |
431 ms |
812 KB |
Output is correct |
3 |
Correct |
451 ms |
1008 KB |
Output is correct |
4 |
Correct |
467 ms |
760 KB |
Output is correct |
5 |
Correct |
340 ms |
760 KB |
Output is correct |
6 |
Correct |
327 ms |
716 KB |
Output is correct |
7 |
Correct |
482 ms |
1044 KB |
Output is correct |
8 |
Correct |
548 ms |
988 KB |
Output is correct |
9 |
Correct |
545 ms |
988 KB |
Output is correct |
10 |
Correct |
540 ms |
756 KB |
Output is correct |
11 |
Correct |
623 ms |
840 KB |
Output is correct |
12 |
Correct |
347 ms |
780 KB |
Output is correct |
13 |
Correct |
323 ms |
1052 KB |
Output is correct |
14 |
Correct |
369 ms |
744 KB |
Output is correct |
15 |
Correct |
353 ms |
1300 KB |
Output is correct |
16 |
Correct |
384 ms |
1028 KB |
Output is correct |
17 |
Correct |
298 ms |
748 KB |
Output is correct |
18 |
Correct |
286 ms |
756 KB |
Output is correct |
19 |
Correct |
305 ms |
820 KB |
Output is correct |
20 |
Correct |
384 ms |
788 KB |
Output is correct |
21 |
Correct |
375 ms |
740 KB |
Output is correct |
22 |
Correct |
379 ms |
756 KB |
Output is correct |
23 |
Correct |
371 ms |
600 KB |
Output is correct |
24 |
Correct |
397 ms |
820 KB |
Output is correct |
25 |
Correct |
342 ms |
984 KB |
Output is correct |
26 |
Correct |
335 ms |
988 KB |
Output is correct |
27 |
Correct |
326 ms |
600 KB |
Output is correct |
28 |
Correct |
575 ms |
1248 KB |
Output is correct |
29 |
Correct |
472 ms |
788 KB |
Output is correct |
30 |
Correct |
523 ms |
988 KB |
Output is correct |
31 |
Correct |
555 ms |
980 KB |
Output is correct |
32 |
Correct |
656 ms |
1104 KB |
Output is correct |
33 |
Correct |
260 ms |
848 KB |
Output is correct |
34 |
Correct |
8 ms |
344 KB |
Output is correct |
35 |
Correct |
8 ms |
344 KB |
Output is correct |
36 |
Correct |
8 ms |
344 KB |
Output is correct |
37 |
Correct |
8 ms |
344 KB |
Output is correct |
38 |
Correct |
7 ms |
600 KB |
Output is correct |
39 |
Correct |
8 ms |
344 KB |
Output is correct |
40 |
Correct |
11 ms |
524 KB |
Output is correct |
41 |
Correct |
13 ms |
532 KB |
Output is correct |
42 |
Correct |
13 ms |
600 KB |
Output is correct |
43 |
Correct |
8 ms |
344 KB |
Output is correct |
44 |
Correct |
11 ms |
592 KB |
Output is correct |
45 |
Correct |
11 ms |
344 KB |
Output is correct |
46 |
Correct |
6 ms |
544 KB |
Output is correct |
47 |
Correct |
1 ms |
344 KB |
Output is correct |
48 |
Correct |
1 ms |
344 KB |
Output is correct |
49 |
Correct |
1 ms |
344 KB |
Output is correct |
50 |
Correct |
1 ms |
344 KB |
Output is correct |
51 |
Correct |
1 ms |
344 KB |
Output is correct |
52 |
Correct |
1 ms |
344 KB |
Output is correct |
53 |
Correct |
1 ms |
344 KB |
Output is correct |
54 |
Correct |
1 ms |
344 KB |
Output is correct |
55 |
Correct |
1 ms |
344 KB |
Output is correct |
56 |
Correct |
1 ms |
344 KB |
Output is correct |
57 |
Correct |
1 ms |
344 KB |
Output is correct |
58 |
Correct |
1 ms |
344 KB |
Output is correct |
59 |
Correct |
1 ms |
344 KB |
Output is correct |
60 |
Correct |
0 ms |
344 KB |
Output is correct |
61 |
Correct |
0 ms |
344 KB |
Output is correct |
62 |
Correct |
0 ms |
344 KB |
Output is correct |
63 |
Correct |
0 ms |
344 KB |
Output is correct |
64 |
Correct |
1 ms |
344 KB |
Output is correct |
65 |
Correct |
1 ms |
344 KB |
Output is correct |
66 |
Correct |
0 ms |
344 KB |
Output is correct |
67 |
Correct |
0 ms |
344 KB |
Output is correct |
68 |
Correct |
0 ms |
344 KB |
Output is correct |
69 |
Correct |
1 ms |
344 KB |
Output is correct |
70 |
Correct |
0 ms |
352 KB |
Output is correct |
71 |
Correct |
1 ms |
596 KB |
Output is correct |
72 |
Correct |
0 ms |
344 KB |
Output is correct |