Submission #1020798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020798		Blistering_Barnacles	Keys (IOI21_keys)	C++17	37 / 100	3027 ms	27712 KiB

keys

#include <bits/stdc++.h>
#include "keys.h"
using namespace std;
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c){
    int n = (int)r.size(), m = (int)u.size();
    vector<vector<pair<int, int>>> adj(n);
    for(int i = 0; i < m; i++){
        adj[u[i]].push_back({v[i], c[i]});
        adj[v[i]].push_back({u[i], c[i]});
    }
    vector<int> p(n);
    for(int i = 0; i < n; i++){
        vector<vector<int>> tmp(n);
        vector<bool> vis(n), ok(n);
        vector<int> se = {i};
        vis[i] = 1;
        while(!se.empty()){
            int v = se.back();
            se.pop_back();
            ok[r[v]] = 1;
            p[i]++;
            for(int j: tmp[r[v]]){
                if(vis[j])continue;
                se.push_back(j);
                vis[j] = 1;
            }
            tmp[r[v]].clear();
            for(auto [u, w]: adj[v]){
                if(vis[u])continue;
                if(ok[w]){
                    se.push_back(u);
                    vis[u] = 1;
                }
                else{
                    tmp[w].push_back(u);
                }
            }
        }
    }
    int mn = *min_element(p.begin(), p.end());
    vector<int> ret(n);
    for(int i = 0; i < n; i++){
        ret[i] = mn == p[i];
    }
    return ret;
}

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