Submission #827876

#	Time	Username	Problem	Language	Result	Execution time	Memory
827876		Liudas	Keys (IOI21_keys)	C++17	37 / 100	3057 ms	38208 KiB

keys

#include <bits/stdc++.h>
using namespace std;
const int n_max = 301000;
const int k_max = 301000;

vector<pair<int,int>> adj[n_max];
bool visited[n_max];
int original_key[n_max];
int has_key[k_max];
vector<int> blocked[k_max];

int n;
int explore(int x) {
    for(int i=0; i<n; i++) {
        visited[i] = false;
        has_key[i] = false;
        blocked[i].clear();
    }
    visited[x] = true;
    queue<int> q;
    q.push(x);
    int ans = 0;
    while(!q.empty()) {
        const int next = q.front();
        q.pop();
        ans++;

        int new_key = original_key[next];
        if(!has_key[new_key]) {
            has_key[new_key] = true;
            for(int i: blocked[new_key]) {
                if(!visited[i]) {
                    visited[i] = true;
                    q.push(i);
                }
            }
        }
        for(pair<int,int> p: adj[next]) {
            if(has_key[p.first]) { // i have the key
                if(!visited[p.second]) { // put in the queue
                    visited[p.second] = true;
                    q.push(p.second);
                }
            } else { // it may be unblocked later
                //assert(p.first < k_max);
                blocked[p.first].push_back(p.second);
            }
        }
    }
    return ans;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    int m = c.size();
    n = r.size();
    for(int i=0; i<n; i++) {
        original_key[i] = r[i];
    }
    for(int i=0; i<m; i++) {
        adj[u[i]].emplace_back(c[i], v[i]);
        adj[v[i]].emplace_back(c[i], u[i]);
    }
    int a[n];
    int s = n+1;
    for(int i=0; i<n; i++) {
        a[i] = explore(i);
        s = min(s, a[i]);
    }
    vector<int> ans(n);

    for(int i=0; i<n; i++) {
        if(a[i]==s) {
            ans[i] = 1;
        }
    }
    return ans;
}

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