Submission #436911

#	Time	Username	Problem	Language	Result	Execution time	Memory
436911		PiejanVDC	열쇠 (IOI21_keys)	C++17	20 / 100	2572 ms	19400 KiB

keys

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

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    int n = r.size(), m = u.size();
    vector<pair<int,int>>adj[n];
    for(int i = 0 ; i < m ; i++) {
        adj[u[i]].push_back({v[i],i});
        adj[v[i]].push_back({u[i],i});
    }
    int mn=INT_MAX;
    vector<int>mini;
    for(int i = 0 ; i < n ; i++) {
     vector<bool>keys(n,false), vis(n,false);
     queue<int>q;
     int curr=0;
     q.push(i);
     bool change=true;
     while(change) {
        change=false;
        int sz=q.size();
        vector<int>restore;
        while(sz--) {
            int node = q.front();
            q.pop();
            if(!vis[node]) curr++;
            vis[node]=true;
            keys[r[node]]=true;
            restore.push_back(node);
            for(auto z : adj[node]) {
                if(keys[c[z.second]] && !vis[z.first]) {
                    change=true;
                    q.push(z.first);
                }
            }
         }
         for(auto z : restore) q.push(z);
     }
     if(curr < mn) {
        mini.clear();
        mini.push_back(i);
        mn=curr;
     } else if(curr == mn) mini.push_back(i);
    }
    vector<int>ans(n,0);
    for(auto z : mini) ans[z]=1;
    return ans;
}

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