제출 #608897

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
608897		jk410	열쇠 (IOI21_keys)	C++17	9 / 100	3062 ms	197888 KiB

keys

//koosaga is god and I'm invincible
//upsolving
#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
#define sz(v) ((int)(v).size())
using namespace std;
const int INF=(int)1e9;
struct dsjs{
    vector<int> par;
    void init(int n){
        par.resize(n);
        for (int i=0; i<n; i++)
            par[i]=i;
    }
    int get_par(int v){
        if (v==par[v])
            return v;
        return par[v]=get_par(par[v]);
    }
    bool my_merge(int a,int b){
        a=get_par(a);
        b=get_par(b);
        if (a==b)
            return false;
        par[b]=a;
        return true;
    }
};
vector<stack<int>> psb_edge;
vector<multiset<pair<int,int>>> impsb_edge;
vector<set<int>> key;
vector<int> nxt;
dsjs idx,graph;
void merge_vertex(int cur,int to){
    if (sz(psb_edge[cur])>sz(psb_edge[to]))
        swap(psb_edge[cur],psb_edge[to]);
    while (!psb_edge[cur].empty()){
        psb_edge[to].push(psb_edge[cur].top());
        psb_edge[cur].pop();
    }
    if (sz(impsb_edge[cur])<sz(impsb_edge[to]))
        swap(impsb_edge[cur],impsb_edge[to]);
    for (auto i=impsb_edge[cur].begin(); i!=impsb_edge[cur].end(); i=impsb_edge[cur].erase(i))
        impsb_edge[to].insert(*i);
    if (sz(key[cur])>sz(key[to]))
        swap(key[cur],key[to]);
    for (auto i=key[cur].begin(); i!=key[cur].end(); i=key[cur].erase(i))
        key[to].insert(*i);
    for (int i:key[to]){
        auto it=impsb_edge[to].lower_bound({i,-1});
        while (it!=impsb_edge[to].end()&&it->first==i){
            psb_edge[to].push(it->second);
            it=impsb_edge[to].erase(it);
        }
    }
}
vector<int> find_reachable(vector<int> r,vector<int> u,vector<int> v,vector<int> c){
    int n=sz(r);
    int m=sz(c);
    psb_edge.resize(n*2);
    impsb_edge.resize(n*2);
    nxt.resize(n*2);
    key.resize(n*2);
    idx.init(n*2);
    graph.init(n*2);
    vector<int> ret(n);
    for (int i=0; i<m; i++){
        if (c[i]==r[u[i]])
            psb_edge[u[i]].push(v[i]);
        else
            impsb_edge[u[i]].insert({c[i],v[i]});
        if (c[i]==r[v[i]])
            psb_edge[v[i]].push(u[i]);
        else
            impsb_edge[v[i]].insert({c[i],u[i]});
    }
    for (int i=0; i<n; i++){
        key[i].insert(r[i]);
        nxt[i]=i;
        if (!psb_edge[i].empty()){
            nxt[i]=psb_edge[i].top();
            psb_edge[i].pop();
        }
    }
    for (int i=0; i<n; i++){
        //cout<<i<<" "<<nxt[i]<<" "<<idx.get_par(i)<<" "<<idx.get_par(nxt[i])<<"\n";
        if (idx.get_par(i)==idx.get_par(nxt[i]))
            continue;
        if (!graph.my_merge(idx.get_par(i),idx.get_par(nxt[i]))){
            //cout<<"!"<<idx.get_par(i)<<" "<<graph.get_par(idx.get_par(i))<<"\n";
            graph.par[graph.get_par(idx.get_par(i))]=n;
            for (int j=idx.get_par(i);;){
                merge_vertex(j,n);
                int tmp=j;
                j=idx.get_par(nxt[j]);
                idx.par[idx.get_par(tmp)]=n;
                if (j==idx.get_par(i))
                    break;
            }
            nxt[n]=n;
            while (!psb_edge[n].empty()&&idx.get_par(psb_edge[n].top())==n){
                //cout<<psb_edge[n].top()<<" "<<idx.get_par(psb_edge[n].top())<<"\n";
                psb_edge[n].pop();
            }
            if (!psb_edge[n].empty()){
                nxt[n]=psb_edge[n].top();
                psb_edge[n].pop();
            }
            //cout<<n<<" "<<nxt[n]<<" "<<idx.get_par(nxt[n])<<"\n";
            n++;
        }
    }
    vector<int> cnt(n);
    for (int i=0; i<sz(ret); i++)
        cnt[idx.get_par(i)]++;
    for (int i=0; i<sz(ret); i++){
        ret[i]=INF;
        if (idx.get_par(i)==idx.get_par(nxt[i]))
            ret[i]=cnt[idx.get_par(i)];
        //cout<<i<<" "<<idx.get_par(i)<<" "<<idx.get_par(nxt[i])<<" "<<ret[i]<<"\n";
    }
    //cout<<"\n";
    int minv=*min_element(all(ret));
    for (int i=0; i<sz(ret); i++)
        ret[i]=(ret[i]==minv);
    return ret;
}

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