Submission #357739

#	Time	Username	Problem	Language	Result	Execution time	Memory
357739		AriaH	Swapping Cities (APIO20_swap)	C++11	0 / 100	1006 ms	524292 KiB

swap

/** Im the best because i work as hard as i possibly can **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl                        "\n"

const int N = 5e5 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 21;

struct edge
{
    int v, u, c;
} E[N];

bool cmp(edge a, edge b) { return a.c < b.c; }

int n, m, ptr, D[N], par[N], ok[N], P[LOG][N], H[N], up[N];

vector < int > G[N];

int get(int x) { return (x == par[x]? x : par[x] = get(par[x])); }

void unify(int i)
{
    ++ ptr;
    D[E[i].v] ++;
    D[E[i].u] ++;
    int v = get(E[i].v), u = get(E[i].u);
    if(v == u)
    {
	ok[ptr] = 1;
	G[ptr].push_back(v);
	P[0][v] = par[v] = ptr;
	return;
    }
    ok[ptr] = max({ok[v], ok[u], int(D[E[i].v] > 2), int(D[E[i].u] > 2)});
    P[0][v] = P[0][u] = par[u] = par[v] = ptr;
    G[ptr].push_back(v);
    G[ptr].push_back(u);
}

void dfs(int v)
{
    if(ok[v] == 0) up[v] = up[P[0][v]];
    else up[v] = v;
    H[v] = H[P[0][v]] + 1;
    for(int T = 1; T < LOG; T ++)
	P[T][v] = P[T - 1][P[T - 1][v]];
    for(auto u : G[v])
	dfs(u);
}

int LCA(int v, int u)
{
    if(H[v] > H[u]) swap(u, v);
    int del = (H[u] - H[v]);
    for(int T = 0; T < LOG; T ++)
    {
	if(del >> T & 1)
	{
	    u = P[T][u];
	}
    }
    if(v == u) return v;
    for(int T = LOG - 1; ~T; T --)
    {
	if(P[T][v] != P[T][u])
	{
	    u = P[T][u];
	    v = P[T][v];
	}
    }
    return P[0][v];
}

void init(int _n, int _m, vector<int> U, vector<int> V, vector<int> W)
{
    n = _n, m = _m;
    for(int i = 1; i <= m; i ++)
    {
	E[i] = {V[i - 1], U[i - 1], W[i - 1]};
    }
    iota(par, par + N, 0);
    sort(E + 1, E + m + 1, cmp);
    for(int i = 1; i <= m; i ++)
    {
	unify(i);
    }
    dfs(ptr);
}

int getMinimumFuelCapacity(int u, int v)
{
    int lca = LCA(u, v);
    if(up[lca] == 0)
    {
	return -1;
    }
    return E[up[lca] - n].c;
}

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