Submission #1094556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094556		azberjibiou	Keys (IOI21_keys)	C++17	9 / 100	279 ms	152248 KiB

keys

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=300050;
const int mxM=10000;
const int mxK=60;
const ll INF=1e18;
struct uf{
    int par[mxN];
    set <pii> noE[mxN];
    set <int> keys[mxN];
    vector <int> okE[mxN];
    int fp(int a){return par[a]==a ? a : par[a]=fp(par[a]);}
    void mrg1(int a, int b){
        int p=fp(a), q=fp(b);
        if(p==q) return;
        int szp=keys[p].size()+noE[p].size(), szq=keys[q].size()+noE[q].size();
        if(szp>szq) swap(p, q);
        for(int x : keys[p]){
            while(true){
                auto it=noE[q].lower_bound(pii(x, 0));
                if(it!=noE[q].end() && it->fi==x){
                    okE[q].push_back(it->se);
                    noE[q].erase(it);
                }
                else break;
            }
        }
        for(auto [x, y] : noE[p]){
            if(keys[q].find(x)!=keys[q].end()) okE[q].push_back(y);
            else noE[q].insert(pii(x, y));
        }
        if(okE[p].size()>okE[q].size()) swap(okE[p], okE[q]);
        for(int x : okE[p]) okE[q].push_back(x);
        par[p]=q;
    }
    void mrg2(int a, int b){par[fp(a)]=fp(b);}
};
int N, M;
int R[mxN];
vector<pii> v[mxN];
uf U1, U2;
void input(){
    cin >> N >> M;
    for(int i=0;i<N;i++) cin >> R[i];
    for(int i=0;i<M;i++){
        int a, b, c;
        cin >> a >> b >> c;
        v[a].emplace_back(b, c);
        v[b].emplace_back(a, c);
    }
}
void set_uf(){
    for(int i=0;i<N;i++) U1.par[i]=i;
    for(int i=0;i<N;i++) U1.keys[i].insert(R[i]);
    for(int i=0;i<N;i++){
        for(auto [x, y] : v[i]){
            if(R[i]==y) U1.okE[i].push_back(x);
            else U1.noE[i].insert(pii(x, y));
        }
    }
    for(int i=0;i<N;i++) U2.par[i]=i;
}
void make_graph(){
    for(int i=0;i<N;i++){
        while(true){
            int now=U1.fp(i);
            if(U1.okE[now].empty()) break;
            int nxt=U1.okE[now].back();
            nxt=U1.fp(nxt);
            U1.okE[now].pop_back();
            if(nxt==now) continue;
            if(U2.fp(nxt)!=U2.fp(now)){
                U1.okE[now].push_back(nxt);
                U2.mrg2(nxt, now);
                //printf("%d -> %d\n", now, nxt);
                break;
            }
            vector <int> mrgv;
            while(nxt!=now){
                mrgv.push_back(nxt);
                nxt=U1.okE[nxt].back();
                nxt=U1.fp(nxt);
                //printf("mrg(%d %d)\n", nxt, now);
            }
            for(int x : mrgv) U1.mrg1(nxt, x);
        }
    }
    //for(int i=0;i<N;i++) printf("par[%d]=%d %d\n", i, U1.fp(i), U2.fp(i));
    //for(int i=0;i<N;i++) printf("E[%d]=%d\n", i, U1.okE[i].empty());
}
vector <int> ans;
int cnt[mxN];
int sz[mxN];
void count(){
    for(int i=0;i<N;i++) sz[U1.fp(i)]++;
    for(int i=0;i<N;i++){
        int p=U1.fp(i);
        if(U1.okE[p].empty()) cnt[i]=sz[p];
        else cnt[i]=999999;
    }
    int mini=999999;
    for(int i=0;i<N;i++) mini=min(mini, cnt[i]);
    ans.resize(N);
    for(int i=0;i<N;i++) ans[i]=(cnt[i]==mini);
}
vector<int> find_reachable(vector<int> r, vector<int> u1, vector<int> u2, vector<int> c) {
	N=r.size(), M=u1.size();
    for(int i=0;i<N;i++) R[i]=r[i];
    for(int i=0;i<M;i++){
        int a=u1[i], b=u2[i], t=c[i];
        v[a].emplace_back(b, t);
        v[b].emplace_back(a, t);
    }
    set_uf();
    make_graph();
    count();
	return ans;
}
/*
int main(){
    gibon
    input();
    set_uf();
    make_graph();
    count();
    for(int x : ans) printf("%d ", x);
}
*/

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