Submission #788388

#	Time	Username	Problem	Language	Result	Execution time	Memory
788388		alexander707070	Keys (IOI21_keys)	C++17	20 / 100	3070 ms	12776 KiB

keys

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

int n,m,cnt;
bool used[MAXN],reach[MAXN],dali;
int ans[MAXN],mins;
vector<int> sol;

vector<int> find_reachable(vector<int> r,vector<int> u,vector<int> v,vector<int> c){
    n=int(r.size()); m=int(u.size());
    mins=n;

    for(int i=0;i<n;i++){
        for(int f=0;f<n;f++){
            used[f]=false; reach[f]=false;
        }

        used[r[i]]=true; reach[i]=true;
        dali=true; cnt=1;

        while(dali){
            dali=false;
            for(int k=0;k<m;k++){
                if(reach[u[k]] and !reach[v[k]] and used[c[k]]){
                    reach[v[k]]=true; used[r[v[k]]]=true;
                    dali=true; cnt++;
                }
                if(!reach[u[k]] and reach[v[k]] and used[c[k]]){
                    reach[u[k]]=true; used[r[u[k]]]=true;
                    dali=true; cnt++;
                }
            }
        }

        ans[i]=cnt;
        mins=min(mins,cnt);
    }

    for(int i=0;i<n;i++){
        if(ans[i]==mins){
            sol.push_back(1);
        }else sol.push_back(0);
    }

    return sol;
}

/*
int main(){
    find_reachable({0, 1, 1, 2},{0, 0, 1, 1, 3}, {1, 2, 2, 3, 1}, {0, 0, 1, 0, 2});
}
*/

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