제출 #839297

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

keys

#include <vector>
#include <bits/stdc++.h>
#include "keys.h"
//#include "grader.cpp"
using namespace std;
mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());
typedef pair<int,int> pii;
vector<pii> muchii[300005];
int use[300005];
int room[300005];
int cnt[300005];
int found[300005];
vector<pii> g[300005];
int seen[300005];
int n,m;
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++)
    {
        int a=u[i],b=v[i],cul=c[i];
        muchii[a].push_back({b,cul});
        muchii[b].push_back({a,cul});
        g[cul].push_back({a,b});
    }
    vector<int> ans;
    for(int i=0;i<n;i++)
    {
        ans.push_back(0);
        room[i]=r[i];
    }
    int minim=1e9;
    for(int i=0;i<n;i++)
    {
        queue<int> coada;
        coada.push(i);
        while(!coada.empty())
        {
            int nod=coada.front();
            coada.pop();
            if(use[nod]==i+1)
                continue;
            cnt[i]++;
            use[nod]=i+1;
            int cul=room[nod];
            if(found[cul]!=i+1)
            {
                found[cul]=i+1;
                for(pii p:g[cul])
                {
                    int a=p.first;
                    int b=p.second;
                    if(use[a]!=i+1)
                        swap(a,b);
                    if(use[a]==i+1&&use[b]!=i+1)
                        coada.push(b);
                }
            }
            for(pii p:muchii[nod])
            {
                int a=p.first;
                int cc=p.second;
                if(found[cc]==i+1)
                    if(use[a]!=i+1)
                        coada.push(a);
            }
        }
        minim=min(minim,cnt[i]);
    }
    for(int i=0;i<n;i++)
        if(cnt[i]==minim)
            ans[i]=1;
    return ans;
}

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