Submission #412451

#	Time	Username	Problem	Language	Result	Execution time	Memory
412451		couplefire	Swapping Cities (APIO20_swap)	C++17	100 / 100	408 ms	47844 KiB

swap

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

const int N = 100005;
const int M = 200005;

int n, m;
array<int, 3> edges[M];
int fa[N+M], par[N+M];
bool isLine[N+M];
int e1[N+M], e2[N+M], weight[N+M];
int cur_id;
vector<int> adj[N+M];
int up[N+M][20], tin[N+M], tout[N+M], timer = -1;

int find(int v){
    return v==fa[v]?v:fa[v]=find(fa[v]);
}

int unite(int u, int v){
    int _u = u, _v = v;
    u = find(u), v = find(v);
    if(u == v){
        if(!isLine[u]) return -1;
        isLine[u] = 0;
        e1[u] = e2[u] = -1;
        return u;
    }
    fa[u] = fa[v] = par[u] = par[v] = cur_id++;
    if(!isLine[u] || !isLine[v]) return cur_id-1;
    for(int i = 0; i<2; i++){
        if(e1[u] == _u && e1[v] == _v) e1[fa[u]] = e2[u], e2[fa[u]] = e2[v];
        else if(e1[u] == _u && e2[v] == _v) e1[fa[u]] = e2[u], e2[fa[u]] = e1[v];
        else if(e2[u] == _u && e1[v] == _v) e1[fa[u]] = e1[u], e2[fa[u]] = e2[v];
        else if(e2[u] == _u && e2[v] == _v) e1[fa[u]] = e1[u], e2[fa[u]] = e1[v];
        swap(_u, _v);
    }
    if(e1[fa[u]] == -1) return cur_id-1;
    isLine[fa[u]] = 1;
    // if(_u == 3 && _v == 1) cout << isLine[6] << endl;
    return cur_id-1;
}

void dfs(int v){
    tin[v] = ++timer;
    up[v][0] = par[v];
    for(int i = 1; i<20; i++)
        up[v][i] = up[up[v][i-1]][i-1];
    for(auto u : adj[v])
        dfs(u);
    tout[v] = timer;
}

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

int LCA(int u, int v){
    if(isPar(u, v)) return u;
    if(isPar(v, u)) return v;
    for(int i = 19; i>=0; i--)
        if(!isPar(up[u][i], v)) u = up[u][i];
    return up[u][0];
}

int query(int v){
    if(!isLine[v]) return weight[v];
    for(int i = 19; i>=0; i--)
        if(isLine[up[v][i]]) v = up[v][i];
    v = up[v][0];
    if(isLine[v]) return -1;
    return weight[v];
}

void init(int _n, int _m, vector<int> U, vector<int> V, vector<int> W){
    n = _n, m = _m;
    for(int i = 0; i<m; i++)
        edges[i] = {W[i], V[i], U[i]};
    sort(edges, edges+m);
    for(int i = 0; i<n+m; i++) fa[i] = i, e1[i] = e2[i] = -1, par[i] = i;
    for(int i = 0; i<n; i++) isLine[i] = 1, e1[i] = e2[i] = i;
    cur_id = n;
    for(int i = 0; i<m; i++){
        int v = unite(edges[i][1], edges[i][2]);
        if(v==-1) continue;
        weight[v] = edges[i][0];
    }
    // cout << cur_id << endl;
    for(int i = 0; i<cur_id-1; i++)
        adj[par[i]].push_back(i);
    dfs(cur_id-1);
    // cout << weight[7] << endl;
}

int getMinimumFuelCapacity(int u, int v){
    return query(LCA(u, v));
}

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