제출 #441550

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
441550		azberjibiou	열쇠 (IOI21_keys)	C++17	37 / 100	3051 ms	228020 KiB

keys

#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define fir first
#define sec second
const int mxN=300100;
int N, M;
queue <int> que;
queue <int> cque[mxN];
vector <pii> adj[mxN];
vector <int> ans;
bool Chk[mxN], CChk[mxN];
int cnt=1000000;
void unlock(int cnum)
{
    CChk[cnum]=true;
    while(!cque[cnum].empty())
    {
        int now=cque[cnum].front();
        cque[cnum].pop();
        if(Chk[now])    continue;
        Chk[now]=true;
        que.push(now);
    }
}
void push_in(int nnum, int cnum)
{
    if(CChk[cnum])
    {
        if(Chk[nnum])   return;
        Chk[nnum]=true;
        que.push(nnum);
    }
    else
    {
        cque[cnum].push(nnum);
    }
}
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();
	for(int i=0;i<M;i++)
    {
        adj[u[i]].push_back({v[i], c[i]});
        adj[v[i]].push_back({u[i], c[i]});
    }
    ans.resize(N);
    for(int i=0;i<N;i++)
    {
        while(!que.empty()) que.pop();
        for(int j=0;j<N;j++)    while(!cque[j].empty()) cque[j].pop();
        for(int j=0;j<N;j++)    Chk[j]=false, CChk[j]=false;
        que.push(i);
        Chk[i]=true;
        while(!que.empty())
        {
            int now=que.front();
            que.pop();
            if(!CChk[r[now]])
            {
                unlock(r[now]);
            }
            for(pii nxt : adj[now])
            {
                if(!Chk[nxt.fir])   push_in(nxt.fir, nxt.sec);
            }
        }
        for(int j=0;j<N;j++)    if(Chk[j])  ans[i]++;
    }
    for(int i=0;i<N;i++)    cnt=min(cnt, ans[i]);
    for(int i=0;i<N;i++)    ans[i]=(ans[i]==cnt ? 1 : 0);
	return ans;
}

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