Submission #436890

#	Time	Username	Problem	Language	Result	Execution time	Memory
436890		PiejanVDC	열쇠 (IOI21_keys)	C++17	0 / 100	1 ms	256 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];
    map<pair<int,int>,bool>mp;
    for(int i = 0 ; i < m ; i++) {
        if(mp[{u[i],v[i]}] || mp[{v[i],u[i]}]) continue;
        adj[u[i]].push_back({v[i],i});
        adj[v[i]].push_back({u[i],i});
        mp[{u[i],v[i]}]=true;
        mp[{v[i],u[i]}]=true;
    }
    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=false;
     while(change) {
        int sz = q.size();
        while(sz--) {
            int node = q.front();
            q.pop();
            vis[node]=true;
            curr++;
            keys[r[node]]=true;
            for(auto z : adj[node]) {
                if(keys[c[z.second]] && !vis[z.first]) {
                    change=true;
                    q.push(z.first);
                }
            }
        }
     }
     if(curr < mn) {
        mini.clear();
        mini.push_back(i);
     } else if(curr == mn) mini.push_back(i);
    }
    vector<int>ans(n,0);
    for(auto z : mini) ans[z]=1;
    return ans;
}

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