Submission #1070671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070671		TVSown	Swapping Cities (APIO20_swap)	C++17	100 / 100	642 ms	136844 KiB

swap

///*** Sown_Vipro ***///
/// ->TUYEN QUOC GIA<- ///

#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
#define F first
#define S second
#define pb push_back
#define pi pair<long long, int>
#define pii pair<int, pair<int, int> >
#define all(a) a.begin(), a.end()
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
#define out(name) if(fopen(name, "w")) freopen(name, "w", stdout);
#define szz(s) int(s.size())
const int N = 1e6 + 5, MAX = 1e6, oo = 1e9 + 5, MOD = 1e9 + 7;
int n, q, nn, m;
long long p[N], b[N], check[N], nxt[25][N], h[N];
vector<long long> adj[N];

struct edge{
    long long u, v, w;
} e[N];

bool cmp(edge a, edge b){
    return a.w < b.w;
}

long long Find(long long u){
    if(u == p[u]) return u;
    return p[u] = Find(p[u]);
}

void Union(long long u, long long v){
    ++b[u]; ++b[v];
    long long uu = u, vv = v;
    ++n;
    p[n] = n;
    u = Find(u); v = Find(v);
    if(u == v){
        p[u] = n;
        adj[u].pb(n);
        adj[n].pb(u);
        check[n] = 1;
//        cout << uu << " " << vv << " " << n << " " << Find(4) << " " << Find(5) << "\n";
    }else{
        p[u] = n; p[v] = n;
        check[n] = (check[u] || check[v] || b[uu] > 2 || b[vv] > 2);
        adj[u].pb(n);
        adj[n].pb(u);
        adj[v].pb(n);
        adj[n].pb(v);
//        cout << uu << " " << vv << " " << n << " " << Find(4) << " " << Find(5) << "\n";
    }
}

void dfs(long long u){
//    cout << u << " " << h[u] << " " << nxt[0][u] << "\n";
    for(long long v : adj[u]){
        if(v == nxt[0][u]) continue;
        h[v] = h[u] + 1;
        nxt[0][v] = u;
        dfs(v);
    }
}

long long lca(long long u, long long v){
    if(h[u] < h[v]) swap(u, v);
    REP(k, 20, 0){
        long long pu = nxt[k][u];
//        cout << k << " " << u << " " << pu << "\n";
//        cout << u << " " << v << " " << h[u] << " " << h[v] << "\n";
        if(h[pu] >= h[v]){
            u = pu;
        }
    }
    if(u == v) return u;
    REP(k, 20, 0){
        long long pu = nxt[k][u], pv = nxt[k][v];
        if(pu != pv){
            u = pu; v = pv;
        }
    }
    return nxt[0][u];
}

long long lift(long long u, long long mid){
    REP(k, 20, 0){
        if((1 << k) <= mid){
            u = nxt[k][u];
            mid -= (1 << k);
        }
    }
    return u;
}

int getMinimumFuelCapacity(int u, int v){
    long long p = lca(u, v);
    long long l = 0, r = h[p];
//    cout << lca << "\n";
    while(l <= r){
        long long mid = (l + r) / 2;
        if(check[lift(p, mid)]) r = mid - 1;
        else l = mid + 1;
    }

    if(l > h[p]) return -1;
    return e[lift(p, l) - nn].w;
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W){
    n = N; m = M;
    nn = N;
    FOR(i, 1, m){
        e[i] = {U[i - 1], V[i - 1], W[i - 1]};
    }
    sort(e + 1, e + 1 + m, cmp);
    FOR(u, 0, n) p[u] = u;
    FOR(i, 1, m){
        long long u = e[i].u, v = e[i].v;

        Union(u, v);
    }

    FOR(k, 0, 20){
        FOR(u, 0, n + 1){
            nxt[k][u] = n + 1;
        }
    }

    h[n] = 1;
    dfs(n);

    FOR(k, 1, 20){
        FOR(u, 0, n){
            nxt[k][u] = nxt[k - 1][nxt[k - 1][u]];
        }
    }
}

//int main(){
//    inp("in.txt");
//////    out("out.txt");
//    cin >> n >> m;
//    nn = n;
//    FOR(i, 1, m){
//        int u, v, w; cin >> u >> v >> w;
//        e[i] = {u, v, w};
//    }
//    sort(e + 1, e + 1 + m, cmp);
//    FOR(u, 0, n) p[u] = u;
//    FOR(i, 1, m){
//        long long u = e[i].u, v = e[i].v;
//
//        Union(u, v);
//    }
//
//    FOR(k, 0, 20){
//        FOR(u, 0, n + 1){
//            nxt[k][u] = n + 1;
//        }
//    }
//
//    h[n] = 1;
//    dfs(n);
//    FOR(k, 1, 20){
//        FOR(u, 0, n){
//            nxt[k][u] = nxt[k - 1][nxt[k - 1][u]];
//        }
//    }
////    cout << nxt[2][nxt[2][4]] << '\n';
//
//    cin >> q;
//    while(q--){
//        int u, v; cin >> u >> v;
//        cout << getMinimumFuelCapacity(u, v) << "\n";
//    }
//}

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