Submission #441372

#	Time	Username	Problem	Language	Result	Execution time	Memory
441372		fcmalkcin	Keys (IOI21_keys)	C++17	100 / 100	1765 ms	114528 KiB

keys

#include "keys.h"
#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"
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];
void dsu(ll x,ll y)
{
    x=find_par(x);
    y=find_par(y);
    if (x==y) return ;
    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;
    }
}
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();
         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)
{
    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)
        {
            dosth(i);
        }
    }
    for (int i=1;i<=n;i++)
    {
        cnt_all[find_par(i)]++;
    }
    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=1e9;
    for (int i=1;i<=n;i++)
    {
        if (i==find_par(i)&&!chk[i])
        {
             ans=min(ans,cnt_all[i]);
        }
    }
    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;
}

Compilation message (stderr)

keys.cpp:12:15: warning: overflow in conversion from 'double' to 'int' changes value from '3.0e+18' to '2147483647' [-Woverflow]
   12 | const ll base=3e18;
      |               ^~~~

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