Submission #1202898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202898		simona1230	Keys (IOI21_keys)	C++20	0 / 100	9 ms	10568 KiB

keys

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

const int maxn=2*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[2001];
int k[2001];

vector<int> e[maxn];
void dfs(int i)
{
    //cout<<i<<endl;
    cnt++;
    in[k[i]]=1;
    used[i]=1;
    for(int j=0;j<e[k[i]].size();j++)
    {
        int nb=e[k[i]][j];
        if(used[nb])continue;
        dfs(nb);
    }

    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 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)
{
	vector<int> h;
	int minn=R.size();

	for(int i=0;i<R.size();i++)
        k[i]=R[i];

	for(int i=0;i<U.size();i++)
        ae(U[i],V[i],C[i]);
    for(int i=0;i<R.size();i++)
    {
        //cout<<i<<"!"<<endl;
        cnt=0;
        dfs(i);
        memset(used,0,sizeof(used));
        memset(in,0,sizeof(in));

        if(cnt<minn)
        {
            minn=cnt;
            h={i};
        }
        else if(cnt==minn)
            h.push_back(i);
    }

    vector<int> ans;
    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;
}

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