제출 #1217751

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

keys

#include "keys.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

namespace{
    vector<set<pair<int,int>>> adj;
    vector<set<int>> C;
    vector<vector<int>> adj2;
    struct DSU{
        vector<int> e;
        DSU(int n){
            e=vector<int>(n,-1);
        }
        int find(int x){
            return (e[x]<0?x:e[x]=find(e[x]));
        }
        int sz(int x){
            return -e[find(x)];
        }
        bool unite(int a,int b){
            //cout<<a<<' '<<b<<'\n';
            a=find(a);
            b=find(b);
            if(a==b) return false;
            if(e[a]>e[b]) swap(a,b);
            e[a]+=e[b];
            e[b]=a;
            for(auto x:adj[b]){
                if(C[a].find(x.f)!=C[a].end()){
                    adj2[a].push_back(x.s);
                }
                else{
                    adj[a].insert(x);
                }
            }
            for(auto x:adj2[b]){
                adj2[a].push_back(x);
            }
            for(auto x:C[b]){
                if(C[a].find(x)==C[a].end()){
                    for(auto it=adj[a].lower_bound({x,0});it!=adj[a].lower_bound({x+1,0});){
                        it=adj[a].erase(it);
                    }
                }
                C[a].insert(x);
            }
            return true;
        }
    };
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
    int n=(int)r.size();
    int m=(int)u.size();
    adj.resize(n);
    adj2.resize(n);
    C.resize(n);
    for(int i=0;i<m;i++){
        adj[u[i]].insert({c[i],v[i]});
        adj[v[i]].insert({c[i],u[i]});
        if(c[i]==r[v[i]]) adj2[v[i]].push_back(u[i]);
        if(c[i]==r[u[i]]) adj2[u[i]].push_back(v[i]);
    }
    for(int i=0;i<n;i++){
        C[i].insert(r[i]);
    }
    DSU dsu(n);
    vector<bool> on(n);
    vector<bool> vis(n);
    vector<bool> qual(n,true);
    function<bool(int)> dfs=[&](int v){
        vis[v]=true;
        on[v]=true;
        //cout<<v<<'\n';
        while(!adj2[v].empty()){
            int u=adj2[v].back();
            adj2[v].pop_back();
            //cout<<"d "<<v<<' '<<u<<'\n';
            u=dsu.find(u);
            if(u==v) continue;
            if(on[u]){
                on[u]=false;
                on[v]=false;
                return true;
            }
            if(vis[u]){
                qual[v]=false;
                continue;
            }
            if(dfs(u)){
                dsu.unite(v,u);
                if(on[v]){
                    on[v]=false;
                    return true;
                }
                else{
                    on[v]=true;
                }
            }
            else{
                qual[v]=false;
            }
            v=dsu.find(v);
        }
        on[v]=false;
        return false;
    };
    for(int i=0;i<n;i++){
        if(!vis[i]) dfs(i);
        //cout<<'\n';
    }
    int mn=n;
    for(int i=0;i<n;i++){
        if(qual[dsu.find(i)]) mn=min(mn,dsu.sz(i));
    }
    vector<int> ans(n);
    for(int i=0;i<n;i++){
        if(qual[dsu.find(i)] and dsu.sz(i)==mn) 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