Submission #443067

#	Time	Username	Problem	Language	Result	Execution time	Memory
443067		benedict0724	Keys (IOI21_keys)	C++17	0 / 100	3 ms	4940 KiB

keys

#include "keys.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> adj[200000];
bool visited[200000];
int ord[200000], link[200000], h[200000], out[200000];
vector<int> E;
int cnt = 0;

int _find(int x)
{
    if(x == link[x]) return x;
    return link[x] = _find(link[x]);
}

void _unite(int x, int y)
{
    x = _find(x); y = _find(y);
    if(x == y) return;
    link[x] = y;
    h[y] += h[x];
}

int dfs(int x, int c)
{
    visited[x] = c;
    ord[x] = ++cnt;
    int now = cnt;
    for(int i : adj[x])
    {
        if(visited[i] != 0 && visited[i] < c)
        {
            E.push_back(x);
            continue;
        }

        if(visited[i] == c)
            now = min(now, ord[i]);
        else
        {
            int k = dfs(i, c);
            if(k > ord[x])
                E.push_back(x);
            else
            {
                _unite(x, i);
                now = min(now, k);
            }
        }
    }
    return now;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {

	int n = r.size();
	int m = u.size();

	for(int i=0;i<m;i++)
    {
        if(r[u[i]] == c[i]) adj[u[i]].push_back(v[i]);
        if(r[v[i]] == c[i]) adj[v[i]].push_back(u[i]);
    }

    for(int i=0;i<n;i++)
    {
        link[i] = i;
        h[i] = 1;
    }

    int color = 0;
    for(int i=0;i<n;i++)
    {
        if(!visited[i]) dfs(i, ++color);
    }

    for(int i : E)
    {
        out[_find(i)]++;
    }

    int S = 500000;
    for(int i=0;i<n;i++)
    {
        int j = _find(i);
        if(out[j] == 0) S = min(S, h[j]);
    }

    vector<int> ans(n);
    //for(int i=0;i<n;i++) ans[i] = adj[i].size();

    for(int i=0;i<n;i++)
    {
        int j = _find(i);
        if(out[j] == 0 && S == h[j]) ans[i] = 1;
    }

	return ans;
}

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