Submission #757959

#	Time	Username	Problem	Language	Result	Execution time	Memory
757959		benjaminkleyn	Keys (IOI21_keys)	C++17	37 / 100	3057 ms	52076 KiB

keys

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

int n, m;
vector<pair<int, int>> g[300000];
set<int> R[300000];

int e[300000];
int find(int u)
{
    return e[u] < 0 ? u : e[u] = find(e[u]);
}
bool unite(int u, int v)
{
    u = find(u), v = find(v);
    if (u == v) return false;
    if (e[u] > e[v]) swap(u, v);

    for (int r : R[v])
        R[u].insert(r);
    R[v] = set<int>();

    for (auto [x, k] : g[v])
        g[u].push_back({x, k});
    g[v] = vector<pair<int, int>>();

    e[u] += e[v], e[v] = u;
    return true;
}

stack<int> stck;
bool vis[300000];
void dfs1(int u)
{
    vis[u] = true;
    for (auto [v, c] : g[u])
        if (!vis[find(v)] && R[u].find(c) != R[u].end())
            dfs1(find(v));
    stck.push(u);
}
int cmp[300000];
void dfs2(int u, int rep)
{
    cmp[u] = rep, vis[u] = true;
    for (auto [v, c] : g[u])
        if (!vis[find(v)] && R[find(v)].find(c) != R[find(v)].end())
            dfs2(find(v), rep);
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) 
{
    n = r.size(), m = u.size();
    for (int i = 0; i < n; i++)
        R[i] = {r[i]};
    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]});
    }

    for (int i = 0; i < n; i++)
        e[i] = -1;

    while (true)
    {
        memset(vis, false, sizeof(vis));
        for (int i = 0; i < n; i++)
            if (i == find(i) && !vis[i])
                dfs1(i);

        memset(vis, false, sizeof(vis));
        while (!stck.empty())
        {
            if (!vis[stck.top()])
                dfs2(stck.top(), stck.top());
            stck.pop();
        }

        bool found = false;
        for (int i = 0; i < n; i++)
            if (unite(i, cmp[i]))
                found = true;

        if (!found)
            break;
    }
    vector<int> out(n, 0), ans(n, 0);
    int mn = INT_MAX;
    for (int i = 0; i < n; i++)
        if (find(i) == i)
        {
            for (auto [j, k] : g[i])
                if (find(i) != find(j) && R[i].find(k) != R[i].end())
                    out[i]++;
            if (out[i] == 0)
                mn = min(mn, -e[i]);
        }

    for (int i = 0; i < n; i++)
        if (out[find(i)] == 0 && -e[find(i)] == mn)
            ans[i] = 1;

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

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