Submission #751866

#	Time	Username	Problem	Language	Result	Execution time	Memory
751866		snpmrnhlol	Swapping Cities (APIO20_swap)	C++17	0 / 100	2068 ms	33976 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 = 0;
    if(deg[a] >= 3 || deg[b] >= 3)active = 1;
    a = leader(a);
    b = leader(b);
    if(a == b)
    {
        if(nodes[v[a].id].active == inf)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].active != inf || v[b].active != inf)active = 1;
        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?w:inf});
        v[a].active = max(min(v[b].active,v[a].active),w);
        nodes[a].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,nodes.size() - 1);
    for(j = 1; j < 20; j++)
    {
        for(i = 0; i < 2*n - 1; i++)
        {
            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(nodes[nodes.size() - 1].active == inf)return -1;
    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];
    for(int i = 19; i >= 0; i--)
    {
        if(nodes[p2[x][i]].active == inf)
        {
            x = p2[x][i];
        }
    }
    if(nodes[x].active == inf)
    {
        x = p2[x][0];
    }*/
    while(dpth[x] > dpth[y])x = p2[x][0];
    while(x != y)x = p2[x][0],y = p2[y][0];
    while(nodes[x].active == inf)x = p2[x][0];
    return 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: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27