Submission #441370

#	Time	Username	Problem	Language	Result	Execution time	Memory
441370		fcmalkcin	Keys (IOI21_keys)	C++17	100 / 100	1868 ms	122656 KiB

keys

#include <bits/stdc++.h>
using namespace std;
#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
//#define endl "\n"
const ll maxn=4e5+10;
const ll mod =998244353 ;
const ll base=3e18;
set<pll> adj[maxn];
set<ll> key[maxn];
set<ll> adv[maxn];
ll par[maxn];
ll find_par(ll u)
{
    if (par[u]==u) return u;
    return par[u]=find_par(par[u]);
}
ll dd[maxn];
/*1
1 6
1 4
1 10
2
2 9
3 5
3 7
3 8
2 3
1 1
2 2
3 2
4 1
5 2
6 1
7 2
8 2
9 2
10 1*/

void dsu(ll x,ll y)
{
    x=find_par(x);
    y=find_par(y);
    if (x==y) return ;
   // par[x]+=par[y];
    par[y]=x;
    if (key[y].size()+adj[y].size()+adv[y].size()>key[x].size()+adj[x].size()+adv[x].size())
    {
        swap(key[x],key[y]);
        swap(adj[x],adj[y]);
        swap(adv[x],adv[y]);
    }
    for (auto to:adv[y]) adv[x].insert(to);
    for (auto to:key[y])
    {
        auto it=adj[x].lower_bound(make_pair(to,(ll)0));
        while (it!=adj[x].end()&&((*it).ff)==to)
        {
            adv[x].insert((*it).ss);
            it=adj[x].erase(it);
        }
        key[x].insert(to);
    }
    for (auto p:adj[y])
    {
          if (key[x].count(p.ff))
          {
              adv[x].insert(p.ss);
          }
          else
          {
              adj[x].insert(make_pair(p.ff,p.ss));
          }
    }
    key[y].clear();
    adj[y].clear();
    adv[y].clear();
}
void popfront(ll x)
{
    while (!adv[x].empty())
    {
        auto h=*adv[x].begin();
        if (find_par(h)!=x&&find_par(h)!=h)
        {
            adv[x].insert(find_par(h));
            adv[x].erase(h);
        }
        else if (find_par(h)==x)
        {
            adv[x].erase(h);
        }
        else break;
    }
}
/*1
6 1 adv of u
1 6 adv of u
4 1 adv of u
1 4 adv of u
10 1 adv of u
1 10 adv of u
2
9 2 adv of u
2 9 adv of u
3 2 adv of u
5 3 adv of u
3 5 adv of u
7 3 adv of u
3 7 adv of u
8 3 adv of u
3 8 adv of u
2 3 adv of u*/
void dosth(ll x)
{
    stack<ll> st;
    dd[x]=1;
    st.push(x);
    while (!st.empty())
    {
         auto u=st.top();
         popfront(u);
         if (adv[u].empty())
         {
             dd[u]=2;
             st.pop();
             continue;
         }
         ll v=*adv[u].begin();
      //   cout <<v<<" "<<u<<endl;
         adv[u].erase(v);
         if (dd[v]==2) continue;
         if (dd[v]==1)
         {
             while(st.top()!=v)
             {
                 dsu(v,st.top());
                 dd[st.top()]=0;
                 st.pop();
             }
         }
         else if(dd[v]==0)
         {
              dd[v]=1;
              st.push(v);
         }
    }
}
ll cnt_all[maxn];
bool chk[maxn];
vector<int> find_reachable(vector<int> r, vector<int>  u, vector<int> v, vector<int> c)
{
   // memset(par,-1,sizeof(par));
    ll n=r.size();
    ll m=u.size();
    vector<int> res;
    for (int i=1;i<=n;i++)
    {
        par[i]=i;
        dd[i]=0;
        key[i].clear();
        adv[i].clear();
        adj[i].clear();
        cnt_all[i]=0;
        chk[i]=0;
        key[i].insert(r[i-1]);
    }
    for (int i=1; i<=m; i++)
    {
        u[i-1]++;
        v[i-1]++;
        if (key[u[i-1]].count(c[i-1]))
        {
             adv[u[i-1]].insert(v[i-1]);
        }
        else
        {
             adj[u[i-1]].insert(make_pair(c[i-1],v[i-1]));
        }
        if (key[v[i-1]].count(c[i-1]))
        {
             adv[v[i-1]].insert(u[i-1]);
        }
        else
        {
             adj[v[i-1]].insert(make_pair(c[i-1],u[i-1]));
        }
    }
    for (int i=1;i<=n;i++)
    {
        if (!dd[i]&&find_par(i)==i)
        {
             //cout <<i<<endl;
            dosth(i);

        }
    }
    /*1 1
2 2
3 2
4 1
5 2
6 1
7 2
8 2
9 2
10 1*/
/*1
0
6 10

2
0
9

3
0
5 7 8 9

4
0
6

5
0
3 9

6
0
1 4 10

7
0
3

8
0
3

9
0
2 3 5

10
0
1 6
*/
    for (int i=1;i<=n;i++)
    {
        cnt_all[find_par(i)]++;
        //cout <<i<<" "<<find_par(i)<<endl;
    }
    for (int i=1;i<=m;i++)
    {
        ll x=find_par(u[i-1]);
        ll y=find_par(v[i-1]);
        if (x==y) continue;
        if (key[x].count(c[i-1])) chk[x]=1;
        if (key[y].count(c[i-1])) chk[y]=1;
    }
    ll ans=base;
    for (int i=1;i<=n;i++)
    {
        if (i==find_par(i)&&!chk[i])
        {
             ans=min(ans,cnt_all[i]);
            // cout <<"NANI"<<endl;
        }
    }
    for (int i=1;i<=n;i++)
    {
          if (!chk[find_par(i)]&&cnt_all[find_par(i)]==ans)
          {
              res.pb(1);
          }
          else
          {
              res.pb(0);
          }
    }
    return res;
}
/*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;
    cin>> n>> m;
    vector<int> r;
    for (int i=1; i<=n; i++)
    {
        int x;
        cin>> x;
        r.pb(x);
    }
    vector<int> u,v,c;
    for (int i=1; i<=m; i++)
    {
        int x, y, w;
        cin>> x>> y>> w;
        u.pb(x);
        v.pb(y);
        c.pb(w);
    }

    vector<int> ans=find_reachable(r,u,v,c);
    for (auto to:ans) cout <<to<<" ";

}*/
/*
10 14
0 0 0 0 0 0 0 0 0 0
2 7 0
6 2 0
2 8 0
4 8 0
9 5 0
5 0 0
4 2 0
2 6 0
7 2 0
9 0 0
8 1 0
9 0 0
8 1 0
5 3 0
*/
/*
4 5
0 1 1 2
0 1 0
0 2 0
1 2 1
1 3 0
3 1 2*/
/*
7 10
0 1 1 2 2 1 2
0 1 0
0 2 0
1 2 1
1 3 0
2 3 0
3 4 1
3 5 2
4 5 0
4 6 2
5 6 1
*/

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 30 / 30
• Subtask 5: 33 / 33