Submission #437478

#	Time	Username	Problem	Language	Result	Execution time	Memory
437478		WnRS	Keys (IOI21_keys)	C++17	20 / 100	2569 ms	1048580 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;
    vector<vector<bool>>vis(n,vector<bool>(n,false));
    for(int i = 0 ; i < n ; i++) {
        vector<bool>keys(n,false);
        queue<int>q;
        q.push(i);
        bool change=true;
        while(change) {
        vector<int>restore;
            change=false;
            int sz = q.size();
            while(sz--) {
                int node = q.front();
                q.pop();
                keys[r[node]]=true;
                restore.push_back(node);
                if(!vis[i][node]) {
                    for(int j = 0 ; j < n ; j++) {
                        if(vis[node][j]) {
                            if(!vis[i][j]) q.push(j);
                            vis[i][j]=true;
                            keys[r[j]]=true;
                        }
                    }
                    vis[i][node]=true;
                }
                for(auto z : adj[node]) {
                    if(keys[c[z.second]] && !vis[i][z.first]) {
                        change=true;
                        q.push(z.first);
                    }
                }
            }
         for(auto z : restore) q.push(z);
        }
    int curr=0;
    for(auto z : vis[i]) curr+=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