Submission #502392

#	Time	Username	Problem	Language	Result	Execution time	Memory
502392		Victor	Swapping Cities (APIO20_swap)	C++17	100 / 100	450 ms	23020 KiB

swap

    // #pragma GCC target ("avx,avx2,fma")
    // #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
    // #pragma GCC optimize ("unroll-loops")
    #include "swap.h"
     
    #include <bits/stdc++.h>
     
    using namespace std;
     
    #define rep(i, a, b) for (int i = (a); i < (b); ++i)
    #define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
    #define trav(a, x) for (auto &a : x)
     
    #define all(x) x.begin(), x.end()
    #define sz(x) x.size()
    #define pb push_back
    #define debug(x) cout << #x << " = " << x << endl
     
    #define umap unordered_map
    #define uset unordered_set
     
    typedef pair<int, int> ii;
    typedef pair<int, ii> iii;
    typedef vector<int> vi;
    typedef vector<ii> vii;
    typedef vector<vi> vvi;
     
    typedef long long ll;
    typedef pair<ll, ll> pll;
    typedef vector<ll> vll;
    typedef vector<pll> vpll;
     
    const int INF = 1'000'000'007;
     
    struct ufds_rollback {
        vector<vii>p;
        vi rank,max_deg,possible,deg;
        vector<bool>cycle;
        
        ufds_rollback(int n) {
            deg.assign(n,0);
            rank.assign(n,0);
            cycle.assign(n,0);
            max_deg.assign(n,0);
            possible.assign(n,INF);
     
            p.resize(n);
            rep(i,0,n)p[i].emplace_back(0,i);
        }
     
        int find(int i,const int &mx) {
            auto it=upper_bound(all(p[i]),ii(mx,INF));
            --it;
            //cout<<"i = "<<i<<" mx = "<<mx<<" val = "<<it->first<<" p = "<<it->second<<endl;
            if(it->second==i)return i;
            else return find(it->second,mx);
            return 0;
        }
     
        void union_set(int i,int j,int val) {
            int u=find(i,val);
            int v=find(j,val);
            if(u==v) {
                cycle[u]=1;
                possible[u]=min(possible[u],val);
                return;
            }
     
            ++deg[i];
            ++deg[j];
            max_deg[u]=max(max_deg[u],deg[i]);
            max_deg[v]=max(max_deg[v],deg[j]);
     
            if(rank[u]<rank[v])swap(u,v);
          	if(rank[u]==rank[v])++rank[u];
            if(p[v].back().first==val)p[v].pop_back();
            p[v].emplace_back(val,u);
            max_deg[u]=max(max_deg[u],max_deg[v]);
            
            if(possible[v]!=INF||max_deg[u]>=3) possible[u]=min(possible[u],val);
        }
    };
     
    ufds_rollback ufds(100001);
    vector<iii> edges;
    int n,m;
     
    void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
        n=N;
        m=M;
        rep(i,0,m) edges.pb({W[i],{U[i],V[i]}});
        sort(all(edges));
        //rep(i,0,n) {
        //    auto it=ufds.p[i].begin();
        //    cout<<sz(ufds.p[i])<<' '<<it->first<<' '<<it->second<<' ';
        //    ufds.find(i,0);
        //}
        trav(edge,edges) {
            int u,v,w;
            w=edge.first;
            tie(u,v)=edge.second;
            ufds.union_set(u,v,w);
            //cout<<"u = "<<u<<" v = "<<v<<" w = "<<w<<endl;
        }
        edges.pb({-1,{0,0}});
    }
     
    int getMinimumFuelCapacity(int X, int Y) {
        int u=X,v=Y;
        int lo=0,hi=m;
        while(lo!=hi) {
            int mid=(lo+hi)/2;
            int w=edges[mid].first;
            int p=ufds.find(u,w);
            if(p==ufds.find(v,w)&&ufds.possible[p]<=w) hi=mid;
            else lo=mid+1;
        }
        return edges[lo].first;
    }
     
    /*
    int main() {
        int N, M;
        assert(2 == scanf("%d %d", &N, &M));
     
        std::vector<int> U(M), V(M), W(M);
        for (int i = 0; i < M; ++i) {
            assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
        }
     
        int Q;
        assert(1 == scanf("%d", &Q));
     
        std::vector<int> X(Q), Y(Q);
        for (int i = 0; i < Q; ++i) {
            assert(2 == scanf("%d %d", &X[i], &Y[i]));
        }
     
        init(N, M, U, V, W);
     
        std::vector<int> minimum_fuel_capacities(Q);
        for (int i = 0; i < Q; ++i) {
            minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
        }
     
        for (int i = 0; i < Q; ++i) {
            printf("%d\n", minimum_fuel_capacities[i]);
        }
     
        return 0;
    }*/

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 23 / 23
• Subtask 6: 27 / 27