Submission #1239416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239416		Faggi	Keys (IOI21_keys)	C++20	67 / 100	3097 ms	325272 KiB

keys

#include <bits/stdc++.h>
#define ll int
#define sz(x) int(x.size())
#define forn(i,n) for(i=0; i<n; i++)
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;

const int MAXN=3e5+1;
vector<pair<ll,ll>>grafo[MAXN];
ll ke[MAXN], cant[MAXN], vis[MAXN], tim=1, comp, id[MAXN];
unordered_set<ll>comps[MAXN];
unordered_map<ll,vector<ll>>esp;
unordered_set<ll>keys;

bool dfs(ll nod)
{
    comps[comp].insert(nod);
    if(cant[nod]!=0)
    {
        auto it=comps[id[nod]].find(comp);
        if(it!=comps[id[nod]].end())
            id[comp]=id[nod];
        return 1;
    }
    vis[nod]=tim;
    cant[comp]++;
    keys.insert(ke[nod]);
    for(auto k:esp[ke[nod]])
    {
        if(vis[k]!=tim)
        {
           if(dfs(k))
                return 1;
        }
    }
    esp[ke[nod]].resize(0);
    for(auto k:grafo[nod])
    {
        auto it=keys.find(k.se);
        if(vis[k.fr]!=tim&&it!=keys.end())
        {
            if(dfs(k.fr))
                return 1;
        }
        else if(it==keys.end())
        {
            esp[k.se].pb(k.fr);
        }
    }
    return 0;
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c)
{
    ll i, mi=INT_MAX;
    for(i=0; i<sz(u); i++)
    {
        grafo[u[i]].pb({v[i],c[i]});
        grafo[v[i]].pb({u[i],c[i]});
    }
    for(i=0; i<sz(r); i++)
    {
        ke[i]=r[i];
        id[i]=i;
    }

    for(i=0; i<sz(r); i++)
    {
        comp=i;
        tim++;
        keys.clear();
        esp.clear();
        if(dfs(i))
        {
            if(id[i]==i)
                cant[i]=MAXN;
            else
                cant[i]=cant[id[i]];
        }
    }
    for(i=0; i<sz(r); i++)
    {
        mi=min(mi,cant[i]);
    }
    vector<int>ans(sz(r),0);
    for(i=0; i<sz(r); i++)
    {
        if(cant[i]==mi)
            ans[i]=1;
    }
    return ans;
}

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