Submission #751860

#	Time	Username	Problem	Language	Result	Execution time	Memory
751860		snpmrnhlol	Swapping Cities (APIO20_swap)	C++17	13 / 100	407 ms	40228 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int M = 2e5;
const int inf = 2e9;
int id[M],deg[N];
struct nodedata{
    int parent,active;
};
vector <nodedata> nodes;///parent,active
vector <int> e[2*N - 1];
int p2[2*N - 1][20];
int dpth[2*N - 1];
struct dsu{
    int id,parent,active,sz;
};
dsu v[N];
int leader(int node){
    if(node == v[node].parent)return node;
    int l = leader(v[node].parent);
    v[node].parent = l;
    return v[node].parent;
}
void connect(int a,int b,int w){
    deg[a]++;deg[b]++;
    int active = inf;
    if(deg[a] >= 3 || deg[b] >= 3)active = min(active,w);
    a = leader(a);b = leader(b);
    if(a == b){
        nodes[v[a].id].active = min(nodes[v[a].id].active,w);
        v[a].active = min(v[a].active,w);
    }else{
        nodes[v[a].id].parent = nodes.size();
        nodes[v[b].id].parent = nodes.size();
        if(v[a].sz < v[b].sz)swap(a,b);
        v[b].parent = a;
        v[a].sz+=v[b].sz;
        v[a].id = nodes.size();
        nodes.push_back({-1,active});
        v[a].active = min(v[b].active,v[a].active);
    }
}
void dfs(int node,int p = -1,int d = 0){
    dpth[node] = d;
    p2[node][0] = p;
    for(auto i:e[node]){
        if(i == p)continue;
        dfs(i,node,d + 1);
    }
}
void init(int n, int m,vector<int> u,vector<int> u2,vector<int> w) {
    int i,j;
    for(i = 0;i < m;i++)id[i] = i;
    for(i = 0;i < n;i++){
        nodes.push_back({-1,inf});
        v[i] = {i,i,inf,1};
    }
    sort(id,id + m,[&](int a,int b){
        return w[a] < w[b];
    });
    for(i = 0;i < m;i++){
        ///connect u[id[i]] with v[id[i]]
        connect(u[id[i]],u2[id[i]],w[id[i]]);
        //cout<<u[id[i]]<<' '<<u2[id[i]]<<'\n';
    }
    int cnt = 0;
    for(auto i:nodes){
        if(i.parent != -1){
            e[i.parent].push_back(cnt);
        }
        cnt++;
    }
    dfs(nodes.size() - 1,-1);
    for(j = 1;j < 20;j++){
        for(i = 0;i < 2*n - 1;i++){
            if(p2[i][j - 1] == -1)p2[i][j] = -1;
            else p2[i][j] = p2[p2[i][j - 1]][j - 1];
        }
    }
    /*for(i = 0;i < 2*n - 1;i++){
        for(j = 0;j < 20;j++)cout<<p2[i][j]<<' ';
        cout<<'\n';
    }
    for(i = 0;i < 2*n - 1;i++){
        cout<<p2[i][0]<<' '<<dpth[i]<<' '<<nodes[i].active<<' '<<i<<'\n';
    }*/
}

int getMinimumFuelCapacity(int x, int y) {
    if(dpth[x] < dpth[y])swap(x,y);
    for(int i = 19;i >= 0;i--){
        if(dpth[x] - (1<<i) >= dpth[y]){
            x = p2[x][i];
        }
    }
    for(int i = 19;i >= 0;i--){
        if(p2[x][i] != p2[y][i]){
            x = p2[x][i];y = p2[y][i];
        }
    }
    if(x != y)x = p2[x][0];
    //cout<<x<<'\n';
    for(int i = 19;i >= 0;i--){
        //cout<<x<<' '<<p2[x][i]<<'\n';
        if(p2[x][i] != -1 && nodes[p2[x][i]].active == inf){
            x = p2[x][i];
        }
    }
    if(nodes[x].active == inf){
        x = p2[x][0];
    }
    return (x==-1?-1:nodes[x].active);
}
/**
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1

3 2
0 1 5
0 2 5
1
1 2
**/

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