제출 #748744

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

keys

    #define here cerr<<"===========================================\n"
    #define dbg(x) cerr<<#x<<": "<<x<<endl;
    #include <bits/stdc++.h>
    #define ld double
    #define ll int
    #define ull unsigned long long
    #define llinf 100000000000000000LL // 10^17
    #define iinf 2000000000 // 2*10^9
    #define pb push_back
    #define popb pop_back
    #define fi first
    #define sc second
    #define endl '\n'
    #define pii pair<int,int>
    #define pll pair<ll,ll>
    #define pld pair<ld,ld>
    #define all(a) a.begin(),a.end()
    #define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
    #define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
    #define si(a) (ll)(a.size())
    using namespace std;
     
    #define maxn 300005
    ll n,m;
    vector<pll> g[maxn];
    set<ll> key[maxn];
    map<ll,vector<ll> > mp[maxn];
    vector<ll> use[maxn];
    ll a[maxn];
    vector<ll> ans;
    ll dsu[maxn],sz[maxn];
    ll root(ll x){
        while(x!=dsu[x]){
            dsu[x] = dsu[dsu[x]];
            x = dsu[x];
        }
        return x;
    }
    ll par[maxn];
    void upd(ll x,ll y){
        x = root(x); y = root(y);
        ll fa = par[y];
        if(sz[x]<sz[y]) swap(x,y);
        dsu[y] = x;
        sz[x]+=sz[y];
        for(ll z : use[y]) use[x].pb(z);
        for(auto it : mp[y]){
            for(ll z : it.sc){
                if(key[x].count(it.fi)==0){
                    mp[x][it.fi].pb(z);
                }else{
                    use[x].pb(z);
                }
            }
        }
        for(ll z : key[y]){
            while(mp[x][z].size()){
                use[x].pb(mp[x][z].back());
                mp[x][z].popb();
            }
            key[x].insert(z);
        }
        par[x] = fa;
        vector<ll>().swap(use[y]);
        map<ll,vector<ll> >().swap(mp[y]);
        set<ll>().swap(key[y]);
    }
    bool check0(){
        bool bad = 0;
        for(ll i = 1;i<=n;i++){
            ll cnt = 0;
            for(pll p : g[i]){
                if(p.sc==a[i]) cnt++;
            }
            if(cnt==0) ans[i] = 1,bad = 1;
        }
        return bad;
    }
    ll dsu2[maxn];
    ll sz2[maxn];
    ll root2(ll u){
        while(u!=dsu2[u]){
            dsu2[u] = dsu2[dsu2[u]];
            u = dsu2[u];
        }
        return u;
    }
    void upd2(ll x,ll y){
        x = root2(x); y = root2(y);
        if(sz2[x]>sz2[y]) swap(x,y);
        dsu2[x] = y;
        sz2[y]+=sz2[x];
    }
    vector<int> find_reachable(vector<int> r,vector<int> u,vector<int> v,vector<int> c) {
        n = si(r);
        m = si(u);
        for(ll i = 1;i<=n;i++) a[i] = r[i-1];
        for(ll i = 1;i<=m;i++){
            ll x,y,w;
            x = u[i-1];
            y = v[i-1];
            w = c[i-1];
            x++; y++;
            g[x].pb({y,w});
            g[y].pb({x,w});
        }
        ans.resize(n+1);
        if(check0()){
            reverse(all(ans));
            ans.popb();
            reverse(all(ans));
            return ans;
        }
        iota(dsu+1,dsu+1+n,1);
        iota(dsu2+1,dsu2+1+n,1);
        fill(sz+1,sz+1+n,1);
        fill(sz2+1,sz2+1+n,1);
        for(ll i = 1;i<=n;i++){
            for(pll p : g[i]){
                ll j = p.fi,z = p.sc;
                if(z==a[i]){
                    use[i].pb(j);
                }else{
                    mp[i][z].pb(j);
                }
            }
            key[i].insert(a[i]);
        }
        vector<ll> roots;
        for(ll i = 1;i<=n;i++) roots.pb(i);
        ll mn = llinf;
        while(roots.size()){
            ll i = roots.back();
            i = root(i);
            roots.popb();
            while(use[i].size()){
                ll j = use[i].back();
                use[i].popb();
                j = root(j);
                if(root(i)==root(j)) continue;
                if(root2(i)==root2(j)){
                    while(par[j]){
                        upd(j,par[j]);
                        j = root(j);
                    }
                    i = root(i);
                }else{
                    par[i] = j;
                    upd2(i,j);
                  break;
                }
            }
            if(!par[i]) mn = min(mn,sz[i]);
        }
        for(ll i = 1;i<=n;i++) ans[i] = (mn==sz[root(i)]);
        reverse(all(ans));
        ans.popb();
        reverse(all(ans));
    	return ans;
    }
    /**
    4 5
    0 1 1 2
    0 1 0
    0 2 0
    1 2 1
    1 3 0
    3 1 2
    **/

컴파일 시 표준 에러 (stderr) 메시지

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:7:19: warning: overflow in conversion from 'long long int' to 'int' changes value from '100000000000000000' to '1569325056' [-Woverflow]
    7 |     #define llinf 100000000000000000LL // 10^17
      |                   ^~~~~~~~~~~~~~~~~~~~
keys.cpp:131:17: note: in expansion of macro 'llinf'
  131 |         ll mn = llinf;
      |                 ^~~~~

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