Submission #1064384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064384		c2zi6	Keys (IOI21_keys)	C++17	37 / 100	3005 ms	30432 KiB

keys

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

VI find_reachable(VI r, VI U_ARG, VI V_ARG, VI c) {
    int n = r.size();
    int m = U_ARG.size();
    VVPI edges(n);
    /*
     * edges[x] = vor koxer@ kbacvin
     * x balninq@ stanaluc heto? 
     */
    rep(i, m) {
        edges[c[i]].pb({U_ARG[i], V_ARG[i]});
        edges[c[i]].pb({V_ARG[i], U_ARG[i]});
    }

    VI ans(n);
    rep(s, n) {
        VI vis(n);
        VI key(n);
        VVI gp(n);
        queue<int> q;

        /*cout << "SOLVING FOR " << s << endl;*/
        
        auto addkey = [&](int k) {
            if (key[k]) return;
            /*cout << "    ADDED NEW KEY " << k << endl;*/
            key[k] = true;
            for (auto[u, v] : edges[k]) {
                if (vis[u] && !vis[v]) {
                    /*cout << "        pushed " << v << " to the queue" << endl;*/
                    q.push(v);
                    vis[v] = true;
                }
                gp[u].pb(v);
            }
        };

        q.push(s);
        vis[s] = true;
        addkey(r[s]);
        while (q.size()) {
            int u = q.front();
            q.pop();
            /*cout << "CURRENTLY AT VERTEX " << u << endl;*/
            addkey(r[u]);
            for (int v : gp[u]) if (!vis[v]) {
                /*cout << "    ADDED VERTEX " << v << endl;*/
                q.push(v);
                vis[v] = true;
            }
        }

        int cnt = 0;
        rep(i, n) cnt += vis[i];
        ans[s] = cnt;
        /*break;*/
    }

    int mn = 2e9;
    for (int x : ans) setmin(mn, x);
    for (int& x : ans) x = (x == mn);
	return ans;
}

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