Submission #1126760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126760		InvMOD	Swapping Cities (APIO20_swap)	C++20	100 / 100	439 ms	62312 KiB

swap

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define gcd __gcd
#define sz(v) (int) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REV(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) "[" #x " = " << (x) << "]"
///#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}

const int N = 3e5+5;
const int lg = 18;


int timerDFS, tin[N], tout[N], value[N];

vector<int> par[lg];

bool can[N]; vector<bool> passable[lg];

vector<int> adj[N];

namespace dsu{
    vector<int> dsu, sz, sumDeg, deg;

    int node = 0;
    int f(int x){
        if(x == dsu[x]) return x;
        return dsu[x] = f(dsu[x]);
    }

    void addEdge(int u, int v, int w){
        int fau = f(u), fav = f(v);

        deg[u]++, deg[v]++;

        dsu.push_back(++node);
        sumDeg.push_back(0), sz.push_back(0);

        dsu[fau] = dsu[fav] = node;

        if(fau != fav){
            sumDeg[node] = sumDeg[fau] + sumDeg[fav] + 2;
            sz[node] = sz[fau] + sz[fav];
            adj[node].push_back(fau);
            adj[node].push_back(fav);
        }
        else{
            sumDeg[node] = sumDeg[fau] + 2;
            sz[node] = sz[fau];
            adj[node].push_back(fau);
        }

        can[node] |= (deg[u] > 2 || deg[v] > 2);
        can[node] |= (can[fau] || can[fav]);
        can[node] |= (sumDeg[node] >= sz[node] * 2);

        value[node] = w;
        return;
    }

    void build(int n){
        sz.resize(n + 1), deg.resize(n + 1);
        dsu.resize(n + 1), sumDeg.resize(n + 1);

        for(int i = 1; i <= n; i++){
            dsu[i] = i;
            sumDeg[i] = 0, sz[i] = 1;
        }
        node = n;
        return;
    }
}

void preDFS(int x){
    tin[x] = ++timerDFS;
    for(int v : adj[x]){
        par[0][v] = x;
        passable[0][v] = can[x];

        for(int i = 1; i < lg; i++){
            par[i][v] = par[i - 1][par[i - 1][v]];
            passable[i][v] = (passable[i - 1][v] | passable[i - 1][par[i - 1][v]]);
        }

        preDFS(v);
    }
    tout[x] = timerDFS;
    return;
}

bool inSub(int u, int v){
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int get_LCA(int u, int v){
    if(inSub(u, v)) return u;
    if(inSub(v, u)) return v;

    for(int i = lg - 1; i >= 0; i--){
        if(par[i][u] > 0 && !inSub(par[i][u], v)){
            u = par[i][u];
        }
    }
    return par[0][u];
}

int findPass(int u){
    if(can[u]) return u;
    for(int i = lg - 1; i >= 0; i--){
        if(par[i][u] > 0 && !passable[i][u]){
            u = par[i][u];
        }
    }
    return par[0][u];
}

void init(int n, int M, vector<int> U, vector<int> V, vector<int> W){
    vector<int> id(M); iota(all(id), 0);

    sort(all(id), [&](int x, int y){return W[x] < W[y];});

    dsu::build(n);
    for(int i = 0; i < sz(id); i++){
        int eid = id[i];
        U[eid]++, V[eid]++;

        dsu::addEdge(U[eid], V[eid], W[eid]);
    }

    for(int i = 0; i < lg; i++){
        par[i].resize(n + M + 1);
        passable[i].resize(n + M + 1);
    }

    // LCA and check Comp ?
    for(int i = 1; i <= dsu::node; i++){
        if(i == dsu::f(i)){
            preDFS(i);
        }
    }
    return;
}

int getMinimumFuelCapacity(int X, int Y){
    if(dsu::f(++X) != dsu::f(++Y)) return -1;

    int lca = get_LCA(X, Y);

    int nearPass = findPass(lca);
    return nearPass > 0 ? value[nearPass] : -1;
}

//#define name "InvMOD"
#ifdef name
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

    int n,m; cin >> n >> m;

    vector<vector<int>> a(3, vector<int>(m));
    FOR(i, 0, 2){
        FOR(j, 0, m - 1){
            cin >> a[i][j];
        }
    }

    init(n, m, a[0], a[1], a[2]);

    int q; cin >> q;

    vector<vector<int>> Q(2, vector<int>(q + 1));

    FOR(i, 0, 1){
        FOR(j, 1, q){
            cin >> Q[i][j];
        }
    }

    FOR(i, 1, q){
        cout << getMinimumFuelCapacity(Q[0][i], Q[1][i]) <<"\n";
    }

    return 0;
}
#endif // name

/* Test case 1:

5 6
0 0 1 1 1 2
1 2 2 3 4 3
4 4 1 2 10 3
3
1 2 0
2 4 1

*/

/* Test case 2:

3 2
0 0
1 2
5 5
1
1 2

*/

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