Submission #357744

#	Time	Username	Problem	Language	Result	Execution time	Memory
357744		AriaH	Swapping Cities (APIO20_swap)	C++11	100 / 100	460 ms	66668 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, 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;
    ptr = n;
    for(int i = 1; i <= m; i ++)
    {
	E[i] = {V[i - 1] + 1, U[i - 1] + 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)
{
    u ++;
    v ++;
    int lca = LCA(u, v);
    if(up[lca] == 0)
    {
	return -1;
    }
    return E[up[lca] - _n].c;
}

/*
case 1:
5 6
1 2 4
1 3 4
3 4 3
4 2 2
2 5 10
2 3 1
3
2 3
3 5
1 2
case 2:
3 2
1 2 5
1 3 5
1
2 3
*/

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