Submission #582367

#	Time	Username	Problem	Language	Result	Execution time	Memory
582367		georgievskiy	Keys (IOI21_keys)	C++17	100 / 100	1301 ms	61300 KiB

keys

#include <bits/stdc++.h>
#include <vector>
using namespace std;

using vi = vector<int>;
typedef vector<vector<pair<int, int>>> graph;

const int N = 3.1e5;
//const int N = 100;
vector<int> blocked[N];
int used[N], keys[N], travelled[N], a[N];
int n, m;
int timer = 0;


void travel(int start, vi& r, graph& g) {
    int cnt = 0;
    int cur = ++timer;
    queue<int> q;
    q.push(start);
    vector<int> to_clear, used_list;
    while (q.size()) {
        int v = q.front(); q.pop();
        if (travelled[v]) {
            for (int x : to_clear)
                blocked[x].clear();
            return;
        }
        if (used[v] == cur)
            continue;
        cnt++;
        used[v] = cur;
        used_list.push_back(v);
        int t = r[v];
        if (keys[t] < cur) {
            for (int x : blocked[t])
                q.push(x);
            keys[t] = cur;
        }
        for (auto u : g[v]) {
            if (used[u.first] == cur)
                continue;

            if (keys[u.second] == cur) {
                q.push(u.first);
            } else {
                to_clear.push_back(u.second);
                blocked[u.second].push_back(u.first);
            }
        }
    }
    for (int x : to_clear)
        blocked[x].clear();
    for (int x : used_list)
        a[x] = min(a[x], cnt);
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	random_device rd;
	mt19937 rng(rd());

	n = r.size(), m = u.size();
	graph g(n);
	for (int i = 0; i < m; i++) {
        g[u[i]].push_back({v[i], c[i]});
        g[v[i]].push_back({u[i], c[i]});
	}

	vector<int> t;
	for (int i = 0; i < m; i++)
        t.push_back(u[i]), t.push_back(v[i]);
    for (int i = 0; i < n; i++)
        if (g[i].empty())
            t.push_back(i);
    shuffle(t.begin(), t.end(), rng);

    fill(a, a + n, 1e9);
    for (int v : t) {
        if (travelled[v])
            continue;
        travel(v, r, g);
        travelled[v] = 1;
    }

    int mn = *min_element(a, a + n);
    vector<int> ans(n);
    for (int i = 0; i < n; i++)
        ans[i] = a[i] == mn;
	return ans;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:87:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   87 |     for (int i = 0; i < n; i++)
      |     ^~~
keys.cpp:89:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   89 |  return ans;
      |  ^~~~~~

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