| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 562981 | fcmalkcin | Chameleon's Love (JOI20_chameleon) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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[x][i]==y)
{
continue;
}
vector<ll> vt1;
vt1.pb(x);
vt1.pb(adj[x][i]);
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
{
bool chk1=false;
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)
{
chk1=true;
if (chk(adj[i][t],i))
{
dd[i]=1;
dd[adj[i][t]]=1;
Answer(adj[i][t],i);
}
else
{
dd[i]=1;
dd[adj[i][t1]]=1;
Answer(adj[i][t1],i);
}
break;
}
}
if (chk1) break;
}
}
}
}
/*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
*/