#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}); 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]=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]}), edge.pb({x, i});
else if (lo==sz(line)) edge.pb({x, line.back()}), edge.pb({x, i});
else
{
for (pll& i:edge)
{
if (i.fi==line[lo-1] && i.se==line[lo]) swap(i, edge.back()), edge.pop_back();
else if (i.fi==line[lo] && i.se==line[lo-1]) swap(i, edge.back()), edge.pop_back();
}
edge.pb({line[lo-1], x}), edge.pb({x, line[lo]}), edge.pb({x, i});
}
}
}
for (pll i:edge) Bridge(min(i.fi, i.se), max(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 |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
344 KB |
Wrong Answer [3] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
344 KB |
Wrong Answer [3] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
344 KB |
Wrong Answer [3] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
600 KB |
Wrong Answer [1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
