Submission #960337

#	Time	Username	Problem	Language	Result	Execution time	Memory
960337		Tuanlinh123	Meetings (JOI19_meetings)	C++17	100 / 100	656 ms	1300 KiB

meetings

#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 (stderr)

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);
      |                              ^~~

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 71 / 71