Submission #599192

#	Time	Username	Problem	Language	Result	Execution time	Memory
599192		lcj	Keys (IOI21_keys)	C++17	37 / 100	3054 ms	28564 KiB

keys

#include <bits/stdc++.h>
#include "keys.h"
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n = r.size();int m = u.size();
    vector<vector<pii>> adj(n);
    for (int i = 0; i < m; i++)
    {
        adj[u[i]].push_back({v[i], c[i]});
        adj[v[i]].push_back({u[i], c[i]});
    }
    vector<int> reach(n, 0);
    for (int i = 0; i < n; i++)
    {
        vector<bool> mkeys(n, 0);
        vector<bool> vis(n, 0);
        int vcount = 0;
        vector<vector<int>> unlockables(n);
        queue<int> q;
        q.push(i);
        while (!q.empty())
        {
            int cn = q.front();q.pop();
            if (vis[cn]) continue;
            vis[cn] = 1;
            vcount++;
            mkeys[r[cn]] = 1;
            for (int j : unlockables[r[cn]]) {
                q.push(j);
            }
            unlockables[r[cn]].clear();
            for (auto nn : adj[cn]) {
                if (mkeys[nn.second]) {
                    q.push(nn.first);
                }
                else {
                    unlockables[nn.second].push_back(nn.first);
                }
            }
        }
        reach[i] = vcount;
    }
    int mr = *min_element(all(reach));    
    vector<int> ans(n);
    for (int i = 0; i < n; i++)
    {
        ans[i] = reach[i] == mr;
    }
	return ans;
}

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