Submission #758843

#	Time	Username	Problem	Language	Result	Execution time	Memory
758843		fanwen	Keys (IOI21_keys)	C++17	37 / 100	3098 ms	25128 KiB

keys

/**
 *      author : pham van sam 
 *      created : 15 June 2023 (Thursday)
 **/
#define ONLINE_JUDGE
#include <bits/stdc++.h>

using namespace std;
using namespace chrono;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)

template <typename U, typename V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; }
template <typename U, typename V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; }

vector <int> find_reachable (vector <int> type_keys, vector <int> u, vector <int> v, vector <int> c) {
    int N = (int) type_keys.size();   
    int M = (int) u.size();
    vector <int> dd(N), keys(N), p(N, 1), ans(N);
    vector <vector <pair <int, int>>> adj(N);
    REP(i, M) {
        adj[u[i]].push_back(make_pair(v[i], c[i]));
        adj[v[i]].push_back(make_pair(u[i], c[i]));
    }
    int run = 0;
    function <void(int)> dfs = [&] (int u) {
        if(dd[u]) return ;
        dd[u] = 1;
        keys[type_keys[u]] = 1;
        run++;
        // cout << u << " ";
        for (auto [v, k] : adj[u]) if(keys[k]) dfs(v);
    };
    REP(u, N) {
        fill(ALL(dd), 0);
        fill(ALL(keys), 0);
        run = 0;
        dfs(u);
        p[u] = run;
    }
    int cur = *min_element(ALL(p));
    REP(i, N) ans[i] = (cur == p[i]);// cout << p[i] << " \n"[i == N - 1];
    return ans;
}

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