Submission #1290861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290861		MMihalev	열쇠 (IOI21_keys)	C++20	37 / 100	3095 ms	22420 KiB

keys

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include "keys.h"
using namespace std;
const int MAX_N=3e5+5;
vector<pair<int,int>>g[MAX_N];
vector<int>wait[MAX_N];
bool taken[MAX_N];
bool keys[MAX_N];
queue<int>q;
int N;
vector<int>key;
int bfs(int s)
{
    while(q.size())q.pop();

    for(int i=0;i<N;i++){wait[i].clear();keys[i]=0;taken[i]=0;}
    q.push(s);

    while(q.size())
    {
        int u=q.front();
        q.pop();
        if(taken[u])continue;
        taken[u]=1;

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

        for(auto [v,c]:g[u])
        {
            if(keys[c])q.push(v);
            else
            {
                wait[c].push_back(v);
            }
        }
    }

    int cnt=0;
    for(int i=0;i<N;i++)
    {
        if(taken[i])cnt++;
    }
    return cnt;
}
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]});
    }

    int mi=1e9;
    vector<int>minnodes;
    for(int i=0;i<N;i++)
    {
        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)ans[u]=1;

	return ans;
}

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