Submission #1203461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203461		simona1230	Keys (IOI21_keys)	C++20	37 / 100	3095 ms	45756 KiB

keys

#include <bits/stdc++.h>
#include "keys.h"
using namespace std;

const int maxn=3*1e5+5;
vector<pair<int,int> > v[maxn];

void ae(int i,int j,int z)
{
    v[i].push_back({j,z});
    v[j].push_back({i,z});
}

int cnt,used[maxn];
int in[maxn];
int k[maxn];

int bg;
bool f;
vector<int> e[maxn], u;
int l[maxn],done[maxn];

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

void dfs(int i)
{
    if(f)return;
    int x=fl(i);
    if(x!=bg)
    {
        //cout<<i<<" ! "<<bg<<endl;
        f=1;
        done[x]=1;
        l[bg]=x;
        return;
    }
    //cout<<i<<endl;
    cnt++;
    in[k[i]]=1;
    used[i]=1;
    u.push_back(i);
    for(int j=0; j<e[k[i]].size(); j++)
    {
        int nb=e[k[i]][j];
        if(used[nb])continue;
        dfs(nb);
    }
    e[k[i]].clear();

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

        if(in[nb.second])dfs(nb.first);
        else
        {
            u.push_back(nb.second);
            e[nb.second].push_back(nb.first);
        }
    }
}

vector<int> p;
void dfs1(int i)
{
    if(fl(i)==bg)p.push_back(i);
    //cout<<"- "<<bg<<" "<<i<<" "<<cnt<<endl;
    cnt++;
    in[k[i]]=1;
    used[i]=1;
    u.push_back(i);
    for(int j=0; j<e[k[i]].size(); j++)
    {
        int nb=e[k[i]][j];
        if(used[nb])continue;
        dfs1(nb);
    }
    e[k[i]].clear();

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

        if(in[nb.second])dfs1(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)
{
    for(int i=0; i<R.size(); i++)
        k[i]=R[i],l[i]=i;

    for(int i=0; i<U.size(); i++)
        ae(U[i],V[i],C[i]);

    for(int j=0; j<=18; j++)
    {
        memset(done,0,sizeof(done));
        for(int i=0; i<R.size(); i++)
        {
            if(done[i]||fl(i)!=i)continue;
            //cout<<i<<"!"<<endl;
            bg=i;
            dfs(i);

            for(int x=0;x<u.size();x++)
            {
                in[k[u[x]]]=used[u[x]]=0;
                e[u[x]].clear();
            }
            u.clear();
            f=0;
        }
    }

    vector<int> ans;
    int minn=R.size();

    for(int i=0;i<R.size();i++)
    {
        if(fl(i)==i)
        {
            bg=i;
            cnt=0;
            dfs1(i);

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

            for(int x=0;x<u.size();x++)
            {
                in[k[u[x]]]=used[u[x]]=0;
                e[u[x]].clear();
            }
            u.clear();

            /*cout<<bg<<" "<<cnt<<endl;
            for(int x=0;x<p.size();x++)
                cout<<p[x]<<" ";
            cout<<endl;*/
            p.clear();
        }
    }

    vector<int> h=ans;
    ans.clear();
    for(int i=0;i<R.size();i++)
        ans.push_back(0);
    for(int i=0;i<h.size();i++)
        ans[h[i]]=1;
    return ans;
}
/*
6 8
1 0 1 1 1 0
0 1 0
0 2 1
0 3 1
0 5 0
1 2 1
2 4 0
3 4 1
4 5 0
*/

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