Submission #562978

#	Time	Username	Problem	Language	Result	Execution time	Memory
562978		fcmalkcin	Chameleon's Love (JOI20_chameleon)	C++17	0 / 100	42 ms	19536 KiB

chameleon

#include <bits/stdc++.h>
using namespace std;

#define ll  int
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=2e5+10;
const ll mod=1e9+7  ;
const ll base=2e9;


/// i believe myself
/// goal 2/7

#include "chameleon.h"

ll par[maxn];
vector<ll> gr[maxn];

ll find_par(ll u)
{
    if (u==par[u]) return u;
    return par[u]=find_par(par[u]);
}
void dsu(ll x,ll y)
{
    x=find_par(x);
    y=find_par(y);
    if (x==y) return ;
    if (gr[x].size()>gr[y].size()) swap(x,y);
    for (auto to:gr[x]) gr[y].pb(to);
    gr[x].clear();
    par[x]=y;
}
ll nxt[maxn];
bool dd[maxn];
vector<ll> adj[maxn];
void mer(ll x,ll y)
{
    adj[x].pb(y);
    adj[y].pb(x);
    dsu(x,nxt[x]);
    dsu(y,nxt[y]);
}
void dosth(vector<ll> vt,ll x)
{
    vector<ll> vt1=vt;
    vt1.pb(x);
    if (Query(vt1)!=(ll)vt1.size())
    {
        ll l=0, h=vt.size()-1;
        while (l<=h)
        {
            ll mid=(l+h)/2;
            vector<ll> vt1;
            for (int i=0;i<=mid;i++) vt1.pb(vt[i]);
            vt1.pb(x);
            if (Query(vt1)==(ll)vt1.size()) l=mid+1;
            else h=mid-1;
        }
        ll pos=l;
        mer(vt[pos],x);
        vector<ll> vt1;
        for (int i=pos+1;i<vt.size();i++) vt1.pb(vt[i]);
        dosth(vt1,x);
    }
}
bool chk(ll x,ll y)
{
    for (int i=0;i<3;i++)
    {
        if (adj[i][x]==y)
        {
            continue;
        }
        vector<ll> vt1;
        vt1.pb(x);
        vt1.pb(adj[i][x]);
        vt1.pb(y);
        if (Query(vt1)==1) return true;
    }
    return false;
}
void Solve(ll n)
{
   n*=2;
   for (int i=1;i<=2*n;i++)
   {
       par[i]=i;
       if (i<=n)
       {
           nxt[i]=i+n;
           gr[i].pb(i);
       }
       else
       {
           nxt[i]=i-n;
       }
   }
   for (int i=2;i<=n;i++)
   {
       vector<ll> lf;
       vector<ll> rt;
       for (int j=1;j<=i-1;j++)
       {
           ll h=find_par(j);
           ll h1=find_par(nxt[j]);
           if (dd[h]||dd[h1]) continue;
           dd[h]=1;
           dd[h1]=1;
           for (auto to:gr[h]) lf.pb(to);
           for (auto to:gr[h1]) rt.pb(to);
       }
       for (int j=1;j<=i-1;j++) dd[find_par(j)]=false,dd[find_par(nxt[j])]=false;
       dosth(lf,i);
       dosth(rt,i);
   }
   for (int i=1;i<=n;i++)
   {
       if (dd[i]) continue;
       ll h=adj[i].size();
       assert((h==1||h==3));
       if (h==1)
       {
           ll x=adj[i][0];
           dd[i]=1;
           dd[x]=1;
           Answer(i,x);
       }
       else
       {
           for (int t=0;t<3;t++)
           {
               for (int t1=t+1;t1<3;t1++)
               {
                   vector<ll> vt;
                   vt.pb(i);
                   vt.pb(adj[i][t]);
                   vt.pb(adj[i][t1]);
                   if (Query(vt)==1)
                   {
                       if (chk(adj[i][t],i))
                       {
                           Answer(adj[i][t],i);
                       }
                       else
                       {
                           Answer(adj[i][t1],i);
                       }
                   }
               }
           }
       }
   }
}


/*int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp","r"))
    {
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }
    ll n, m, p, q;
    ll g[10];
    ll r[10][2];
    cin>> n>> m>> p;
    for (int i=0;i<m;i++) cin>> r[i][0]>>r[i][1];
    cin>> q;
    for (int t=0;t<q;t++) cin>> g[t];
    count_routes(n,m,p,r,q,g);
}*/
/*
5 5 2
1 0
1 2
3 2
1 3
4 2
2
3 1
*/
/*
6 6 0
1 2
0 1
0 3
3 4
4 5
1 5
1
3
*/

Compilation message (stderr)

chameleon.cpp: In function 'void dosth(std::vector<int>, int)':
chameleon.cpp:69:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for (int i=pos+1;i<vt.size();i++) vt1.pb(vt[i]);
      |                          ~^~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36