Submission #1203835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203835		simona1230	Keys (IOI21_keys)	C++20	0 / 100	7 ms	14408 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 bfs(int i)
{
    queue<int> q;
    q.push(i);
    used[i]=1;
    while(q.size())
    {
        cnt++;
        int f=q.front();
        q.pop();

        u.push_back(f);
        act[k[f]]=1;
        for(int i=0;i<e[k[f]].size();i++)
        {
            int nb=e[k[f]][i];
            if(!used[nb])
            {
                used[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;
                q.push(nb.first);
            }
            else
            {
                u.push_back(nb.second);
                e[nb.second].push_back(nb.first);
            }
        }
    }

    for(int i=0;i<u.size();i++)
    {
        int j=u[i];
        used[j]=act[j]=0;
        e[j].clear();
    }
    if(cnt<minn)
    {
        minn=cnt;
        ans={i};
    }
    else if(cnt==minn)ans.push_back(i);
    u.clear();
    cnt=0;
}

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];
    }

    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 i=0;i<R.size();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