Submission #334860

#	Time	Username	Problem	Language	Result	Execution time	Memory
334860		limabeans	Swapping Cities (APIO20_swap)	C++17	100 / 100	486 ms	63676 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"

using namespace std;


const int maxn = 1e6 + 10;

int n, m;
vector<int> g[maxn];
vector<pair<int,pair<int,int>>> edges;
int head;

int par[maxn];
int indx[maxn];
int deg[maxn];
bool good[maxn];
int cost[maxn];

int parent(int x) {
    if (par[x]==x) return x;
    return par[x]=parent(par[x]);
}

const int LOG = 20;
int st[LOG+1][maxn];
int ht[maxn];

void dfs(int at, int p=-1) {
    for (int j=1; j<LOG; j++) {
	st[j][at]=st[j-1][st[j-1][at]];
    }
    for (int to: g[at]) {
	if (to == p) continue;
	st[0][to]=at;
	ht[to] = 1+ht[at];
	dfs(to, at);
    }
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n=N;
    m=M;
    head = n;
    for (int i=0; i<M; i++) {
	edges.push_back({W[i],{U[i],V[i]}});
    }

    sort(edges.begin(),edges.end());


    for (int i=0; i<n; i++) {
	par[i]=i;
	indx[i]=i;
	deg[i]=0;
	good[i]=false;
    }



    for (auto ed: edges) {
	int w = ed.first;
	int U = ed.second.first;
	int V = ed.second.second;
	int u = parent(U);
	int v = parent(V);
	
	if (u==v) {
	    if (!good[indx[u]]) {
		g[head].push_back(indx[u]);
		good[head]=true;
		cost[head]=w;
		indx[u] = head++;
	    }
	} else {
	    deg[U]++;
	    deg[V]++;
	    
	    bool ok = (good[indx[u]] || good[indx[v]] || deg[U]>2 || deg[V]>2);
	    par[v]=u;
	    g[head].push_back(indx[u]);
	    g[head].push_back(indx[v]);
	    good[head] = ok;
	    cost[head] = w;
	    indx[u] = head++;
	}
    }

    st[0][head-1] = head-1;
    dfs(head-1);
}

int lca(int u, int v) {
    if (ht[u]<ht[v]) {
	swap(u,v);
    }
    int dx = ht[u]-ht[v];
    for (int j=LOG-1; j>=0; j--) {
	if (dx>>j&1) {
	    u=st[j][u];
	}
    }
    if (u==v) return v;
    
    for (int j=LOG-1; j>=0; j--) {
	if (st[j][u]!=st[j][v]) {
	    u=st[j][u];
	    v=st[j][v];
	}
    }
    
    return st[0][v];
}

int getMinimumFuelCapacity(int u, int v) {
    if (!good[head-1]) return -1;

    int mid = lca(u,v);
    if (good[mid]) {
	return cost[mid];
    }

    for (int j=LOG-1; j>=0; j--) {
	if (ht[mid] < (1<<j)) continue;
	if (!good[st[j][mid]]) {
	    mid=st[j][mid];
	}
    }

    return cost[st[0][mid]];
}

/*
int main() {
    // init(4,4,{0,1,2,3},{1,2,3,0},{1,1,1,1});
    // cout<<getMinimumFuelCapacity(1, 2)<<endl;

    
    init(5, 6, {0, 0, 1, 1, 1, 2}, {1, 2, 2, 3, 4, 3}, {4, 4, 1, 2, 10, 3});
    cout<<getMinimumFuelCapacity(1, 2)<<endl;
    cout<<getMinimumFuelCapacity(2, 4)<<endl;
    cout<<getMinimumFuelCapacity(0, 1)<<endl;
    
    return 0;
}
*/

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