Submission #1050638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050638		shiocan	Swapping Cities (APIO20_swap)	C++17	100 / 100	180 ms	179388 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;
};
 
const int K = 26;
vector<vector<int>> st;
vector<int> euler, h, first, d;
 
void build(vector<int> & height){
    int n = height.size();
    st = vector<vector<int>> (K, vector<int> (n+2, 0));
 
    for(int i = 0; i<n; i++)
        st[0][i] = i;
        
    for(int i = 1; i<K; i++)
        for(int j = 0; j + (1 << i) <= n; j++)
            if(height[st[i-1][j]] < height[st[i-1][j + (1 << (i - 1))]])
                st[i][j] = st[i-1][j];
            else
                st[i][j] = st[i-1][j + (1 << (i - 1))];
}
 
int get(vector<int> & height, int l, int r){
    int i = 64 - __builtin_clzll(r - l + 1) - 1;
 
    if(height[st[i][l]] < height[st[i][r - (1 << i) + 1]])
        return st[i][l];
    return st[i][r - (1 << i) + 1];    
}
 
vector<int> first_reachable, is_reachable;
 
void dfs(int u, int p = -1, int k = 0){
    euler.push_back(u);
    h[euler.size() - 1] = k;
    first[u] = euler.size() - 1;   
 
    if(p > -1 && !is_reachable[u])
        first_reachable[u] = first_reachable[p];
 
    for(auto i : a[u])
        if(i != p){
            dfs(i, u, k + 1);
 
            euler.push_back(u);
            h[euler.size() - 1] = k;
        }
}
 
int lca(int u, int v){
    if(first[u] > first[v])
        swap(u, v);
 
    return euler[get(h, first[u], first[v])];
}
 
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 = vector<int> (2 * (n + m + 5));
    h = vector<int> (4 * (n + m + 5));
 
    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;
 
    dfs(ds.sz - 1);
 
    build(h);
}
 
int getMinimumFuelCapacity(int u, int v){
    int l = lca(u, v);
 
    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