Submission #1203956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203956		simona1230	Keys (IOI21_keys)	C++20	0 / 100	6 ms	14604 KiB

keys

#include <bits/stdc++.h>
#include "keys.h"
using namespace std;
const int maxn=3*1e5+5;

int k[maxn];
vector<pair<int,int> > v[maxn];
vector<int> e[maxn],u,ans;
int cnt,minn,used[maxn],act[maxn];

void clean()
{
    for(int i=0; i<u.size(); i++)
    {
        int j=u[i];
        used[j]=0;
        act[k[j]]=0;
        e[j].clear();
    }
    u.clear();
}

vector<int> p;
void bfs(int s)
{
    clean();
    p.clear();
    cnt=0;

    queue<int> q;
    q.push(s);
    used[s]=1;
    act[k[s]]=1;

    while(q.size())
    {
        cnt++;
        int f=q.front();
        q.pop();

        p.push_back(f);
        u.push_back(f);

        for(int i=0; i<e[k[f]].size(); i++)
        {
            int nb=e[k[f]][i];
            if(!used[nb])
            {
                used[nb]=1;
                act[k[nb]]=1;
                q.push(nb);
            }
        }
        e[k[f]].clear();

        for(int i=0; i<v[f].size(); i++)
        {
            pair<int,int> nb=v[f][i];
            if(used[nb.first])continue;

            if(act[nb.second])
            {
                used[nb.first]=1;
                act[k[nb.first]]=1;
                q.push(nb.first);
            }
            else
            {
                u.push_back(nb.second);
                e[nb.second].push_back(nb.first);
            }
        }
    }

    if(cnt<minn)
    {
        minn=cnt;
        ans=p;
    }
    else if(cnt==minn)
    {
        for(int i=0; i<p.size(); i++)
            ans.push_back(p[i]);
    }
}

int curr;
int done[maxn];
int l[maxn];
int par[maxn];
int sz[maxn];

int fl(int x)
{
    if(x==l[x])return x;
    return l[x]=fl(l[x]);
}

void bfs1(int s)
{
    clean();

    queue<int> q;
    q.push(s);
    used[s]=1;
    act[k[s]]=1;
    u.push_back(s);

    while(q.size())
    {
        int f=q.front();
        q.pop();

        for(int i=0; i<e[k[f]].size(); i++)
        {
            int nb=e[k[f]][i];
            if(!used[nb])
            {
                int x=fl(nb);
                if(x!=s)
                {
                    //cout<<s<<" "<<x<<endl;
                    s=fl(s);
                    par[s]=par[x];
                    if(sz[x]>sz[s])swap(x,s);
                    done[par[x]]=curr;
                    l[s]=x;
                    sz[x]+=sz[s];
                    return;
                }

                u.push_back(nb);
                used[nb]=1;
                act[k[nb]]=1;
                q.push(nb);
            }
        }
        e[k[f]].clear();

        for(int i=0; i<v[f].size(); i++)
        {
            pair<int,int> nb=v[f][i];
            if(used[nb.first])continue;

            if(act[nb.second])
            {
                int x=fl(nb.first);
                if(x!=s)
                {
                    //cout<<s<<" "<<x<<endl;
                    s=fl(s);
                    par[s]=par[x];
                    if(sz[x]>sz[s])swap(x,s);
                    done[par[x]]=curr;
                    l[s]=x;
                    sz[x]+=sz[s];
                    return;
                }
                u.push_back(nb.first);
                used[nb.first]=1;
                act[k[nb.first]]=1;
                q.push(nb.first);
            }
            else
            {
                u.push_back(nb.second);
                e[nb.second].push_back(nb.first);
            }
        }
    }
}

std::vector<int> find_reachable(std::vector<int> R, std::vector<int> U, std::vector<int> V, std::vector<int> C)
{
    minn=R.size();

    for(int i=0; i<R.size(); i++)
    {
        k[i]=R[i];
        l[i]=i;
        par[i]=i;
        sz[i]=1;
    }

    for(int i=0; i<U.size(); i++)
    {
        v[U[i]].push_back({V[i],C[i]});
        v[V[i]].push_back({U[i],C[i]});
    }

    for(int c=1; c<=18; c++)
    {
        curr=c;
        for(int i=0; i<R.size(); i++)
        {
            if(l[i]==i&&done[i]!=curr)
            {
                bfs1(i);
            }
        }
    }

    for(int i=0; i<R.size(); i++)
        if(l[i]==i)bfs(i);

    vector<int> h(R.size());
    for(int i=0; i<ans.size(); i++)
        h[ans[i]]=1;

    return h;
}

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