제출 #1192799

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192799		imarn	Keys (IOI21_keys)	C++20	100 / 100	448 ms	52540 KiB

keys

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define t3 tuple<int,int,int>
#define sz(x) (ll)x.size()
#define cd complex<long double>
using namespace std;
const int mxn=3e5+5;
vector<pii>g[mxn];
vector<int>rr;
int pr[mxn]{0},n,m,tt[mxn]{0};
bool use[mxn]{0},vis[mxn]{0};
vector<int>usek,usen,useb;
vector<int>key[mxn];
vector<pii>uni;
queue<int>q;
int rs=1e9;
int get(int r){
    return pr[r]==r?r:pr[r]=get(pr[r]);
}
void bfs(int st){
    q.push(st);
    bool ed=0;
    while(!q.empty()){
        auto u=q.front();q.pop();
        if(vis[u])continue;
        if(!use[rr[u]]){
            use[rr[u]]=1,usek.pb(rr[u]);
            while(!key[rr[u]].empty()){
                if(!vis[key[rr[u]].back()])q.push(key[rr[u]].back());
                key[rr[u]].pop_back();
            }
        }
        if(get(u)!=get(st))uni.pb({st,u}),ed=1;
        vis[u]=1;usen.pb(u);
        if(ed)break;
        for(auto [v,c]:g[u]){
            if(vis[v])continue;
            else if(!use[c])key[c].pb(v),useb.pb(c);
            else q.push(v);
        }
    }while(!q.empty())q.pop();
    for(auto it : useb)key[it].clear();
    for(auto it : usek)use[it]=0;
    for(auto it : usen)vis[it]=0;
    useb.clear();usek.clear();usen.clear();
}
void bfs2(int st){
    q.push(st);
    while(!q.empty()){
        auto u=q.front();q.pop();
        if(vis[u])continue;
        if(!use[rr[u]]){
            use[rr[u]]=1,usek.pb(rr[u]);
            while(!key[rr[u]].empty()){
                if(!vis[key[rr[u]].back()])q.push(key[rr[u]].back());
                key[rr[u]].pop_back();
            }
        }vis[u]=1;tt[st]++;
        for(auto [v,c]:g[u]){
            if(vis[v])continue;
            else if(!use[c])key[c].pb(v),useb.pb(c);
            else q.push(v);
        }
    }while(!q.empty())q.pop();
    for(auto it : useb)key[it].clear();
    for(auto it : usek)use[it]=0;
    useb.clear();usek.clear();usen.clear();
    rs=min(rs,tt[st]);
}
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();iota(pr,pr+n,0);rr=r;vector<int>ans;ans.resize(n,0);
    for(int i=0;i<m;i++){
        g[u[i]].pb({v[i],c[i]});
        g[v[i]].pb({u[i],c[i]});
    }bool dn=0;
    while(!dn){
        for(int i=0;i<n;i++){
            if(get(i)==i)bfs(i);
        }
        if(uni.empty())dn=1;
        if(dn)break;
        for(auto [a,b] : uni){
            pr[get(a)]=get(b);
        }uni.clear();
    }
    for(int i=0;i<n;i++){
        if(get(i)==i)bfs2(i);
    }
    for(int i=0;i<n;i++)if(vis[i]&&tt[get(i)]==rs)ans[i]=1;
    return ans;
}
/*int main(){
    vector<int>x=find_reachable({0, 1, 1, 2, 2, 1, 2},{0, 0, 1, 1, 2, 3, 3, 4, 4, 5},{1, 2, 2, 3, 3, 4, 5, 5, 6, 6},{0, 0, 1, 0, 0, 1, 2, 0, 2, 1});
    for(auto it : x)cout<<it<<' ';
}*/

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