Submission #687553

#	Time	Username	Problem	Language	Result	Execution time	Memory
687553		coding_snorlax	Keys (IOI21_keys)	C++17	37 / 100	254 ms	20880 KiB

keys

#include<bits/stdc++.h>
#include "keys.h"
using namespace std;
vector<pair<int,int>> G[2005];
int Get[2005];
int N;
vector<int> List;
vector<int> Count;
vector<int> final_answer;
int cal(int node){
    //cout<<"\n";
    int vis[2005]={0};
    set<int> List[2005];
    int key[2005]={0};
    vector<int> process;
    process.push_back(node);
    vis[node]=1;
    while((int)process.size()){
        //cout<<"1\n";
        int now = process.back();
        process.pop_back();
        if(!key[Get[now]]){
            key[Get[now]]=1;
            for(int i:List[Get[now]]){
                process.push_back(i);
            }
        }
        for(auto i:G[now]){
            //cout<<"now_i: " << i.first<<" ";
            //cout<<"2\n";
            //cout<<i.first<<" "<<i.second<<" \n";
            if(key[i.second]==1){
                //cout<<"3\n";
                if(!vis[i.first]){
                    vis[i.first] = 1;
                    process.push_back(i.first);
                }
            }
            else{
                //cout<<"4\n";
                List[i.second].insert(i.first);
            }
        }
    }
    //cout<<"OK\n";
    int answer = 0;
    for(int i=0;i<N;i++){
        if(vis[i]) answer++;
    }
    return answer;
}
vector<int> find_reachable(vector<int> r,vector<int> u,vector<int> v,vector<int> c){
    N=(int)r.size();
    for(int i=0;i<(int)r.size();i++) Get[i]=r[i];
    for(int i=0;i<(int)u.size();i++){
        G[u[i]].push_back(make_pair(v[i],c[i]));
        G[v[i]].push_back(make_pair(u[i],c[i]));
    }
    int Min = 3000;
    for(int i=0;i<N;i++){
        Count.push_back(cal(i));
        Min = min(Min,Count[i]);
    }
    for(int i=0;i<N;i++){
        if(Count[i]==Min) final_answer.push_back(1);
        else final_answer.push_back(0);
    }
    return final_answer;
}

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