Submission #1052998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052998		noyancanturk	Keys (IOI21_keys)	C++17	37 / 100	3016 ms	42184 KiB

keys

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

#define pb push_back
using pii=pair<int,int>;

const int lim=3e5+100;
int n,m;

vector<pii>v[lim];
bool havekey[lim];
vector<int>willvis[lim],r;
bool vis[lim];

void dfs(int node){
    if(vis[node])return;
    vis[node]=1;
    if(!havekey[r[node]]){
        havekey[r[node]]=1;
        for(int j:willvis[r[node]]){
            dfs(j);
        }
    }
    for(auto[j,c]:v[node]){
        if(havekey[c]){
            dfs(j);
        }else{
            willvis[c].pb(j);
        }
    }
}

vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> c) {
	n=R.size(),m=U.size();
    r=R;
    for(int i=0;i<m;i++){
        v[U[i]].pb({V[i],c[i]});
        v[V[i]].pb({U[i],c[i]});
    }
	int res=INT_MAX;
	vector<int>ans;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            vis[j]=0;
            havekey[j]=0;
            willvis[j].clear();
        }
        dfs(i);
        int cnt=0;
        for(int j=0;j<n;j++){
            if(vis[j])cnt++;
        }
        if(cnt<res){
            res=cnt;
            ans.clear();
        }
        if(res==cnt){
            ans.pb(i);
        }
    }
	vector<int>finalans(n,0);
	for(int i:ans){
		finalans[i]=1;
	}
	return finalans;
}

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