제출 #1290866

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

keys

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<tuple>
#include "keys.h"
using namespace std;
const int MAX_N=3e5+5;
vector<pair<int,int>>g[MAX_N];
vector<int>wait[MAX_N];
vector<int>takennodes;
vector<int>waitclear;
bool taken[MAX_N];
bool keys[MAX_N];
queue<int>q;
int N;
vector<int>key;

int parent[MAX_N];
int sz[MAX_N];
int Find(int u)
{
    if(parent[u]==u)return u;
    return Find(parent[u]);
}
void Merge(int u,int v)
{
    int urt=Find(u);
    int vrt=Find(v);
    if(urt==vrt)return;

    sz[vrt]+=sz[urt];
    parent[urt]=vrt;
}

bool calc=0;
vector<pair<int,int>>pairs;
int bfs(int s)
{
    while(q.size())q.pop();
    q.push(s);

    while(q.size())
    {
        int u=q.front();
        q.pop();
        if(taken[u])continue;
        taken[u]=1;
        takennodes.push_back(u);
        if(Find(u)!=Find(s))
        {
            if(!calc)
            {
                pairs.push_back({s,u});
                break;
            }
        }

        keys[key[u]]=1;
        for(int v:wait[key[u]])q.push(v);
        wait[key[u]].clear();

        for(int id=0;id<g[u].size();id++)
        {
            int v,c;
            tie(v,c)=g[u][id];
            if(keys[c])q.push(v);
            else
            {
                waitclear.push_back(c);
                wait[c].push_back(v);
            }
        }
    }

    int cnt=takennodes.size();

    for(int u:takennodes)
    {
        keys[key[u]]=0;
        taken[u]=0;
    }
    for(int c:waitclear)
    {
        wait[c].clear();
    }
    takennodes.clear();
    waitclear.clear();

    return cnt;
}
bool usedminnodes[MAX_N];
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c)
{
    key=r;
    N=r.size();
    for(int i=0;i<u.size();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++)
    {
        parent[i]=i;
        sz[i]=1;
    }
    for(int times=0;times<30;times++)
    {
        pairs.clear();
        for(int i=0;i<N;i++)
        {
            if(parent[i]!=i)continue;
            bfs(i);
        }
        for(int id=0;id<pairs.size();id++)
        {
            int x,y;
            tie(x,y)=pairs[id];
            Merge(x,y);
        }
    }

    calc=1;

    int mi=1e9;
    vector<int>minnodes;
    for(int i=0;i<N;i++)
    {
        if(parent[i]!=i)continue;

        int cur=bfs(i);
        if(cur<mi)
        {
            minnodes.clear();
            minnodes.push_back(i);
            mi=cur;
        }
        else if(cur==mi)minnodes.push_back(i);
    }

    vector<int>ans;
    ans.resize(N);
    for(int u:minnodes)usedminnodes[u]=1;

    for(int i=0;i<N;i++)
    {
        if(usedminnodes[parent[i]])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