Submission #497453

#	Time	Username	Problem	Language	Result	Execution time	Memory
497453		David_M	Keys (IOI21_keys)	C++17	100 / 100	1453 ms	952924 KiB

keys

#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define lb lower_bound
 
const int N=1000006, INF=1e9+7;
int p[N], p2[N], f[N];
vector<vi> Ans;
 
struct abc{
    set<pii> s;
    set<int> k;
    queue<int> d;
    int pa;
    vi v;
    int sz;
} e[N];
 
void add_key(int x, int c){
    auto &[s, k, d, pa, v, sz] = e[x];
    if(k.find(c)!=k.end()) return;
    k.insert(c);
    for (auto it = s.lb({c,0}); it != s.lb({c,INF}); it=s.lb({c, 0}))
        d.push((*it).second), s.erase(it);
}
void add_door(int x, int y, int c){
    auto &[s, k, d, pa, v, sz] = e[x];
    if(k.find(c)!=k.end()) d.push(y);
    else s.insert({c, y});
}
 
int P(int x){ return (p[x]<0) ? x : p[x] = P(p[x]); }
int sz(int x){ return -P(x); }
void unite(int x, int y){
    if((x=P(x))==(y=P(y)))return;
    if(sz(x)<sz(y))swap(x, y);
    p[x]+=p[y];
    p[y]=x;
}
 
int P2(int x){ return (p2[x]<0) ? x : p2[x] = P2(p2[x]); }
int sz2(int x){ return -P2(x); }
void unite2(int x, int y){
    if((x=P2(x))==(y=P2(y)))return;
    if(sz2(x)<sz2(y))swap(x, y);
    p2[x]+=p2[y];
    p2[y]=x;
}
 
void un(int x, int y){
    int PA=e[y].pa;
    unite2(x, y);
    if(e[x].sz<e[y].sz)swap(e[x], e[y]);
    if(P2(x)==y)swap(e[x], e[y]), swap(x, y);
    auto &[xs, xk, xd, xpa, xv, xsz]=e[x];
    auto &[ys, yk, yd, ypa, yv, ysz]=e[y];
 
    for (auto [k,Y]:ys) add_door(x, Y, k);
    for (auto k:yk) add_key(x, k);
    while(!yd.empty()) xd.push(yd.front()), yd.pop();
    xpa=PA;
    for (auto Y:yv) xv.pb(Y);
    xsz=xv.size();
}
void next(int x, int w=-1){
    //cout<<"BBB"<<" "<<x<<endl;
    //for (int i=0; i<4; i++){
    //    cout<<P(i)<<" "<<P2(i)<<"A"<<endl;
    //}
 
    int X=P2(x), PA;
    auto &[s, k, d, pa, v, sz]=e[X];
    if(!d.empty()){
        pa=d.front();
        d.pop();
        PA=P2(pa);
        while(PA==X && !d.empty()){
            pa=d.front();
            d.pop();
            PA=P2(pa);
        }
    }
    //cout<<"_"<<x<<" "<<pa<<endl;
    if(pa==-1 || PA==X){
        //cout<<"LEFJdsifjo"<<endl;
        //for (auto E:v)cout<<E<<" ";cout<<endl;
        Ans.pb(v);
        f[P(X)]=1;
        return;
    }
    //cout<<"CCC"<<" "<<x<<endl;
    if(P(X)==P(PA)){
        while(PA!=X) /*cout<<"WWW"<<x<<" "<<X<<" "<<pa<<" "<<PA<<endl,*/ un(X, PA), X=P2(x), PA=P2(e[X].pa);
        e[X].pa=-1;
        next(X);
    }else{
        //cout<<x<<" "<<X<<" "<<pa<<" "<<PA<<endl;
        if(f[P(PA)])f[P(X)]=1;
        unite(X, PA);
    }
 
}
 
vi find_reachable(vi r, vi u, vi v, vi c) {
	vi ans(r.size(), 0);
    int n=r.size(), m=u.size();
    vector<pii> V[n];
    for (int i=0; i<m; i++){
        int x=u[i], y=v[i], k=c[i];
        V[x].pb({y, k});
        V[y].pb({x, k});
    }
 
    for (int i=0; i<n; i++){
        p[i]=p2[i]=-1;
        for (auto[y,c]:V[i])e[i].s.insert({c, y});
        add_key(i, r[i]);
        e[i].pa=-1;
        e[i].v.pb(i);
        e[i].sz=1;
        if(e[i].d.empty())Ans.pb({i});
    }
    /*
    for (int i=0; i<n; i++){
        auto &[s, k, d, pa, v, sz] = e[i];
        cout<<i<<":"<<endl;
        cout<<"locked:   ";for (auto [x, y] : s)cout<<x<<"_"<<y<<" ";cout<<endl;
        cout<<"keys:     ";for (auto x : k)cout<<x<<" ";cout<<endl;
        cout<<"doors:    ";while(!d.empty())cout<<d.front()<<" ",d.pop();cout<<endl;
        cout<<"pa:       ";cout<<pa<<" ";cout<<endl;
        cout<<"sz:       ";cout<<sz<<" ";cout<<endl;
    }return {0};
    */
 
    //cout<<"AAA"<<endl;
    for (int i=0; i<n; i++)
        if(f[P(i)]==0 && e[P2(i)].pa==-1)next(i);
 
    int an=INF;
    for (auto v:Ans)an=min(an, (int)v.size());
    //cout<<"OIEJSOJIP"<<an<<endl;
    for (auto v:Ans){
        if(an<v.size())continue;
        for (auto x:v) ans[x]=1;
    }
	return ans;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:146:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |         if(an<v.size())continue;
      |            ~~^~~~~~~~~
keys.cpp: In function 'void next(int, int)':
keys.cpp:102:14: warning: 'PA' may be used uninitialized in this function [-Wmaybe-uninitialized]
  102 |         unite(X, PA);
      |         ~~~~~^~~~~~~

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