제출 #1281252

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281252		Faggi	열쇠 (IOI21_keys)	C++20	0 / 100	4 ms	576 KiB

keys

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;

const int MAXN = 3e5 + 1;

vector<ll> R, res, comp[MAXN], block, bkey[MAXN], key, alc;
ll last[MAXN], id[MAXN], ans, keys[MAXN];
vector<pair<ll, ll>> grafo[MAXN];
bool vis[MAXN], dead[MAXN];

void unionfind(ll x, ll y)
{
    y = id[y];
    for (auto k : comp[x])
    {
        id[k] = y;
        comp[y].pb(k);
    }
}

void cln()
{
    for (auto k : block)
        bkey[k].clear();
    for (auto k : key)
        keys[k] = 0;
    alc.clear();
    key.clear();
    block.clear();
}

void bfs(ll nod, ll it)
{
    last[nod] = it;
    keys[R[nod]] = 1;
    key.pb(R[nod]);
    queue<ll> q;
    q.push(nod);

    while (q.size())
    {
        ll x = q.front();
        q.pop();
        if (id[x] != id[nod])
        {
            unionfind(nod, x);
            last[id[x]] = it;
            cln();
            return;
        }

        if (vis[x])
            continue;
        vis[x] = 1;
        alc.pb(x);

        if (keys[R[x]] == 0)
        {
            keys[R[x]] = 1;
            key.pb(R[x]);
            while (bkey[R[x]].size())
            {
                q.push(bkey[R[x]].back());
                bkey[R[x]].pop_back();
            }
        }

        for (auto k : grafo[x])
        {
            if (vis[k.fr])
                continue;
            if (keys[k.se])
                q.push(k.fr);
            else
            {
                bkey[k.se].pb(k.fr);
                block.pb(k.se);
            }
        }
    }

    dead[nod] = 1;
    if(sz(alc)<ans)
    {
        res.clear();
        ans=sz(alc);
    }
    if(ans==sz(alc))
    {
        for(auto k:alc)
            res.pb(k);
    }
    cln();
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c)
{
    ll n = sz(r), m = sz(c), i, it = 0;
    ans = n + 1;
    for (i = 0; i < n; i++)
    {
        R.pb(r[i]);
        id[i] = i;
        comp[i] = {i};
    }

    for (i = 0; i < m; i++)
    {
        grafo[u[i]].pb({v[i], c[i]});
        grafo[v[i]].pb({u[i], c[i]});
    }

    bool band = 1;

    while (band)
    {
        it++;
        memset(vis, 0, sizeof(vis));
        band = 0;
        for (i = 0; i < n; i++)
        {
            if (id[i] == i && !dead[i] && last[i] != it)
            {
                bfs(i, it);
                band = 1;
            }
        }
    }

    vector<int>ret(n,0);

    for(auto k:res)
        ret[k]=1;
    return ret;
}

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