Submission #1050679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050679		shiocan	Swapping Cities (APIO20_swap)	C++17	100 / 100	330 ms	219836 KiB

swap

#include <bits/stdc++.h>
#include <cstdlib>
#include <stdlib.h>
using namespace std;
/*
    #define cin fin
    #define cout fout
    string __fname = ""; ifstream fin(__fname + ".in"); ofstream fout(__fname + ".out");
*/
#define ull unsigned long long 
//#define ll long long
//#define int long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
//ll mod = 1e9 + 7; 
//const int inf = 1e18;
//const int N = 3e5 + 100;

vector<vector<int>> a;
int n, m;

struct dsu{
    int sz = 0;
    vector<int> p, cnt;
    vector<bool> sw;
    dsu(int n, int m){
        sz = n;
        p.resize(n + m + 5);
        cnt.resize(n, 0);
        sw.resize(n + m + 5, 0);

        for(int i = 0; i < n + m + 5; i++)  
            p[i] = i;
    }

    int find(int u){
        return p[u] == u ? u : p[u] = find(p[u]);
    }

    void merge(int u, int v){
        if(u < n && v < n){
            cnt[u]++, cnt[v]++;
            if(cnt[u] > 2)
                sw[sz] = 1;
            if(cnt[v] > 2)
                sw[sz] = 1;
        }
        
        u = find(u);
        v = find(v);

        if(u == v){
            p[sz] = p[u] = sz;

            a[sz].push_back(u);
            
            sw[sz] = 1;

            sz++;
            return;
        }

        p[sz] = p[u] = p[v] = sz;
        a[sz].push_back(u);
        a[sz].push_back(v);

        if(sw[u] || sw[v])
            sw[sz] = 1;

        sz++;
    }
};

struct edge{
    int w, u, v;
};

vector<int> first_reachable, is_reachable;

const int K = 30;
vector<vector<int>> st;
vector<int> tin, tout;
int timer = 0;

void dfs(int u, int p){
    tin[u] = ++timer;
    
    st[u][0] = p;

    for(int i = 1; i < K; i++)
        st[u][i] = st[st[u][i - 1]][i - 1];

    if(p != u && !is_reachable[u])
        first_reachable[u] = first_reachable[p];

    for(auto i : a[u])
        if(i != p){
            dfs(i, u);
        }

    tout[u] = ++timer;
}

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

int lca(int u, int v){
    if(is_ancestor(u, v))
        return u;
    if(is_ancestor(v, u))
        return v;

    for(int i = K - 1; i >= 0; i--)
        if(!is_ancestor(st[u][i], v))
            u = st[u][i]; 

    return st[u][0];
}

vector<edge> edges;

void init(int N, int M, vector<int> u, vector<int> v, vector<int> w){
    n = N;
    m = M;

    a = vector<vector<int>> (n + m + 5);

    for(int i = 0; i<m; i++)
        edges.push_back({w[i], u[i], v[i]});

    sort(all(edges), [&] (edge a, edge b){
        return a.w < b.w;
    });

    dsu ds(n, m);

    for(auto i : edges)
        ds.merge(i.u, i.v);

    first_reachable = is_reachable = vector<int> (ds.sw.size(), 0ll);

    for(int i = 0; i < (int)first_reachable.size(); i++)
        if(ds.sw[i])
            is_reachable[i] = 1, first_reachable[i] = i;

    tin = tout = vector<int> (2 * (n + m + 5));
    st = vector<vector<int>> (4 * (n + m + 5), vector<int> (K));

    dfs(ds.sz - 1, ds.sz - 1);

    // cout << "tin : ";
    // for(auto i : tin)
    //     cout << i << ' ';
    // cout << '\n';

    // cout << "tout : ";
    // for(auto i : tout)
    //     cout << i << ' ';
    // cout << '\n';
}

int getMinimumFuelCapacity(int u, int v){
    int l = lca(u, v);

    // cout << u << ' ' << v << " : " << l << '\n';
    if(l >= n && is_reachable[l])
        return edges[l - n].w;
    if(first_reachable[l] >= n && is_reachable[first_reachable[l]])
        return edges[first_reachable[l] - n].w;
    return -1;
}

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