Submission #680343

#	Time	Username	Problem	Language	Result	Execution time	Memory
680343		DennisTran	Keys (IOI21_keys)	C++17	67 / 100	3076 ms	51072 KiB

keys

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#include <bits/stdc++.h>
using namespace std;
const int n_max = 301000;
const int k_max = 301000;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
#define rand rd

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 finished[n_max];
int a[n_max];
vector <int> visited_list, blocked_list;

int n;
int explore(int x) {
    for (int i : visited_list) {
        visited[i] = false;
        has_key[original_key[i]] = false;
    } visited_list.clear();
    for (int i : blocked_list) blocked[i].clear();
    blocked_list.clear();

    visited[x] = true;
    queue <int> q;
    q.push(x);
    int ans = 0;
    visited_list.emplace_back(x);
    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;
                    visited_list.emplace_back(i);
                    if (finished[i]) return 1e6;
                    q.push(i);
                }
            }
        }
        for(auto p: adj[next]) {
            if(has_key[p.first]) { 
                if(!visited[p.second]) { 
                    visited[p.second] = true;
                    visited_list.emplace_back(p.second);
                    if (finished[p.second]) return 1e6;
                    q.push(p.second);
                }
            } else {
                blocked_list.emplace_back(p.first);
                blocked[p.first].push_back(p.second);
            }
        }
    }

    for (int i : visited_list) a[i] = min(a[i], ans);
    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();
    REP(i, n) original_key[i] = r[i];
    
    REP(i, m) {
        adj[u[i]].emplace_back(c[i], v[i]);
        adj[v[i]].emplace_back(c[i], u[i]);
    }
    int s = n + 1;
    vector <int> perm(n);
    iota(ALL(perm), 0);
    shuffle(ALL(perm), rd);

    REP(i, n) a[i] = n + 1;
    REP(i, n) {
        a[perm[i]] = min(a[perm[i]], explore(perm[i]));
        s = min(s, a[perm[i]]);
        finished[perm[i]] = 1;
    }

    vector<int> ans(n);
    REP(i, n) if(a[i] == s) ans[i] = 1;
    return ans;
}

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