Submission #979407

#	Time	Username	Problem	Language	Result	Execution time	Memory
979407		alontanay	Keys (IOI21_keys)	C++17	37 / 100	3068 ms	36424 KiB

keys

#include "keys.h"
#include <bits/stdc++.h>
#define f first
#define s second

using namespace std;
using pi = pair<int,int>;

const int MAX_N = 3e5;
vector<pi> nei[MAX_N];
vector<pi> need_key[MAX_N];
int state[MAX_N];
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
    int n = r.size(), m = u.size();
    for(int i = 0;i < m; i ++) {
        int a = u[i], b = v[i], t = c[i];
        nei[a].push_back({b,t});
        nei[b].push_back({a,t});
    }
    vector<int> res;
    int opt_score = n;
    for(int i = 0; i < n; i ++) {
        vector<bool> vis(n);
        vis[i] = true;
        stack<int> dfs;
        vector<vector<int>> waiting(n);
        vector<int> keys(n);
        dfs.push(i);
        int cnt = 0;
        while(!dfs.empty()) {
            int cur = dfs.top();
            cnt++;
            dfs.pop();
            keys[r[cur]] = true;
            for(int w : waiting[r[cur]]) {
                if(!vis[w]) {
                    vis[w] = true;
                    dfs.push(w);
                }
            }
            waiting[r[cur]].clear();
            for(pi edge : nei[cur]) {
                if(keys[edge.s]) {
                    if(!vis[edge.f]) {
                        vis[edge.f] = true;
                        dfs.push(edge.f);
                    }
                } else {
                    waiting[edge.s].push_back(edge.f);
                }
            }
        }
        if(cnt < opt_score) {
            res.clear();
            opt_score = cnt;
        }
        if(cnt == opt_score) {
            res.push_back(i);
        }
    }
    vector<int> ans(n);
    for(int r : res) {
        ans[r] = 1;
    }
    return ans;
}

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