Submission #758286

#	Time	Username	Problem	Language	Result	Execution time	Memory
758286		benjaminkleyn	Keys (IOI21_keys)	C++17	37 / 100	346 ms	80388 KiB

keys

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

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

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

bool compress()
{
    bool found = false;
    for (int i = 0; i < n; i++)
    {
        if (cmp[i] != cmp[cmp[i]]) found = true;
        cmp[i] = cmp[cmp[cmp[cmp[i]]]];
    }

    for (int u = 0; u < n; u++)
    {
        temp[u] = g[u];
        g[u] = vector<pair<int, int>>();
    }

    for (int u = 0; u < n; u++)
        for (auto [v, k] : temp[u])
            if (cmp[u] != cmp[v])
                g[cmp[u]].push_back({cmp[v], k});

    for (int i = 0; i < n; i++)
        if (cmp[i] != i)
        {
            for (int r : R[i])
                R[cmp[i]].insert(r);
            R[i] = set<int>();
        }
    return found;
}

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++)
        cmp[i] = i;

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

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

        if (!compress())
            break;
    }

    vector<int> sz(n, 0);
    for (int i = 0; i < n; i++)
        sz[cmp[i]]++;

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

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

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