Submission #441236

#	Time	Username	Problem	Language	Result	Execution time	Memory
441236		fcmalkcin	Keys (IOI21_keys)	C++17	0 / 100	34 ms	59812 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]<0) 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[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[y],key[x]);
        swap(adj[y],adj[x]);
        swap(adv[y],adv[x]);
    }
    for (auto to:adv[y]) adv[x].insert(to);
    for (auto to:key[y])
    {
        auto it=adj[x].lower_bound(make_pair(to,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(p);
          }
    }
}
void popfront(ll x)
{
    while (!adv[x].size())
    {
        auto h=*adv[x].begin();
        if (find_par(h)!=x&&par[h]>=0)
        {
            adv[x].erase(h);
            adv[x].insert(find_par(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
         {
              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++)
    {
        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])
        {
            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=base;
    for (int i=1;i<=n;i++)
    {
        if (!chk[find_par(i)])
        {
             ll t=find_par(i);
             ans=min(ans,cnt_all[t]);
        }
    }
    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<<" ";

}*/
/*
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: 0 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33