제출 #1191165

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191165		12345678	Keys (IOI21_keys)	C++17	100 / 100	438 ms	57628 KiB

keys

#include <bits/stdc++.h>

using namespace std;

const int nx=3e5+5;

int n, m, dsu[nx], t, vs[nx], have[nx], cnt, p[nx], mn=INT_MAX;
vector<pair<int, int>> d[nx], edg;
vector<int> block[nx], past, past_block, k, res;
queue<int> q;

int find(int x)
{
    if (dsu[x]==x) return x;
    return dsu[x]=find(dsu[x]);
}

int bfs(int u, int mode)
{
    cnt=0;
    //for (int i=0; i<n; i++) if (vs[i]||have[i]||!block[i].empty()) cout<<"clear error\n";
    vs[u]=1;
    past.push_back(u);
    q.push(u);
    while (!q.empty())
    {
        auto cu=q.front();
        //cout<<"bfs "<<u<<' '<<cu<<'\n';
        cnt++;
        q.pop();
        have[k[cu]]=1;
        while (!block[k[cu]].empty()) 
        {
            int v=block[k[cu]].back();
            block[k[cu]].pop_back();
            if (!vs[v])
            {
                if (find(v)!=find(u)) return v;
                vs[v]=1;
                past.push_back(v);
                q.push(v);
            }
        }
        for (auto [v, w]:d[cu])
        {
            if (vs[v]) continue;
            if (have[w])
            {
                if (find(v)!=find(u)) return v;
                vs[v]=1;
                past.push_back(v);
                q.push(v);
            }
            else 
            {
                past_block.push_back(w);
                block[w].push_back(v);
            }
        }
    }
    if (mode)
    {
        mn=min(mn, cnt);
        for (auto u:past) p[u]=cnt;
    }
    return -1;
}

void clear()
{
    while (!q.empty()) q.pop();
    for (auto u:past) vs[u]=0, have[k[u]]=0;
    past.clear();
    for (auto w:past_block) block[w].clear();
    past_block.clear();
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	n=r.size();
	m=u.size();
    k=r;
    for (int i=0; i<n; i++) dsu[i]=i, p[i]=INT_MAX;
    for (int i=0; i<m; i++) d[u[i]].push_back({v[i], c[i]}), d[v[i]].push_back({u[i], c[i]});
    while (1)
    {
        edg.clear();
        for (int i=0; i<n; i++) 
        {
            if (dsu[i]==i)
            {
                t=bfs(i, 0);
                clear();
                if (t!=-1) edg.push_back({i, t});
            }
        }
        if (edg.empty()) break;
        for (auto [u, v]:edg) dsu[find(u)]=find(v);
    }
    //cout<<"debug\n";
    for (int i=0; i<n; i++) if (dsu[i]==i) bfs(i, 1), clear();
    for (int i=0; i<n; i++) res.push_back(p[i]==mn);
	return res;
}

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