Submission #582259

#	Time	Username	Problem	Language	Result	Execution time	Memory
582259		georgievskiy	Keys (IOI21_keys)	C++17	37 / 100	147 ms	44168 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 = 2022;
vector<int> opens[N];
int n, m;

int solve(int start, vi& r, graph& g) {
    for (int i = 0; i < n; i++)
        opens[i].clear();
    vector<int> used(n, 0);
    vector<int> keys(n, 0);
    queue<int> q;
    q.push(start);
    while (q.size()) {
        int v = q.front(); q.pop();
        if (used[v])
            continue;
        used[v] = 1;
        int t = r[v];
        if (!keys[t]) {
            for (int x : opens[t])
                q.push(x);
            keys[t] = 1;
        }
        for (auto u : g[v]) {
            if (!used[u.first]) {
                if (keys[u.second]) {
                    q.push(u.first);
                } else {
                    opens[u.second].push_back(u.first);
                }
            }
        }
    }
    int ans = accumulate(used.begin(), used.end(), 0);
    return ans;
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	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> a(n);
	for (int i = 0; i < n; i++)
        a[i] = solve(i, r, g);

    int mn = *min_element(a.begin(), a.end());
    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:59:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   59 |     for (int i = 0; i < n; i++)
      |     ^~~
keys.cpp:61:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   61 |  return ans;
      |  ^~~~~~

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