Submission #680338

#	Time	Username	Problem	Language	Result	Execution time	Memory
680338		DennisTran	Keys (IOI21_keys)	C++17	0 / 100	9 ms	14420 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 n;
int explore(int x, int bound) {
    REP(i, n) {
        visited[i] = false;
        //has_key[i] = false;
        blocked[i].clear();
    }
    visited[x] = true;
    queue<int> q;
    q.push(x);
    int ans = 0;
    int ok = 1;
    while(!q.empty()) {
        const int next = q.front();
        q.pop();
        ans++;
        if (ans > bound) {
            ok = -1;
            break;
        }
        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;
                    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;
                    if (finished[p.second]) return 1e6;
                    q.push(p.second);
                }
            } else blocked[p.first].push_back(p.second);
        }
    }
    return ans * ok;
}

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 a[n];
    int s = n + 1;
    vector <int> perm(n);
    iota(ALL(perm), 0);
    shuffle(ALL(perm), rd);
    REP(i, n) {
        a[perm[i]] = explore(perm[i], s);
        if (a[perm[i]] < 0) a[perm[i]] = n + 1;
        s = min(s, a[perm[i]]);
        finished[perm[i]] = 1;
        has_key[r[perm[i]]] = 0;
    }

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

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