Submission #757938

#	Time	Username	Problem	Language	Result	Execution time	Memory
757938		benjaminkleyn	Keys (IOI21_keys)	C++17	0 / 100	12 ms	21716 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);
    for (auto [x, k] : g[v])
        g[u].push_back({x, k});
    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]});

    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 (!vis[find(i)])
                dfs1(find(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> ans(n, 1);

    int mn = INT_MAX;
    for (int i = 0; i < n; i++)
        if (i == find(i))
            mn = min(mn, -e[i]);
    for (int i = 0; i < n; i++)
        if (-e[find(i)] == mn)
            ans[i] = 0;

	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:85:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   85 |     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: 0 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33