Submission #289681

# Submission time Handle Problem Language Result Execution time Memory
289681 2020-09-02T22:36:18 Z b00n0rp Swapping Cities (APIO20_swap) C++17
100 / 100
651 ms 47608 KB
/*
Soln:
Basically we need to find some 3-degree vertex or a cycle
and we want the minimum value of 
-> max(path from (x,y), path from x to the vertex,(3rd shortest edge or cycle edge))
First compute mst then use dp on tree
dp[u] = best such vertex in subtree of u
dp_par[u] = best such vertex outside subtree of u
*/
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long double LD;
typedef long long ll;
// #define int ll
#define pb push_back
#define mp make_pair
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
typedef map<int,int> mii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
#define F first
#define S second
#define PQ(type) priority_queue<type>
#define PQD(type) priority_queue<type,vector<type>,greater<type> >
#define WL(t) while(t --)
#define SZ(x) ((int)(x).size())
#define runtime() ((double)clock() / CLOCKS_PER_SEC)
#define inrange(i,a,b) ((i>=min(a,b)) && (i<=max(a,b)))

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const int MAXN = 100005;
const int SQRTN = 1003;
const int LOGN = 22;
const double PI=acos(-1);
 
#ifdef int
const int INF=1e16;
#else
const int INF=1e9+5;
#endif
 
const int MOD = 1000000007;
const int FMOD = 998244353;
const double eps = 1e-9;


int n,m;
vpii adj[MAXN];
vpii extra[MAXN];
vector<pair<int,pii> > edges;

int dsusz[MAXN],dsupar[MAXN];

int find(int x){
	if(dsupar[x] == x) return x;
	return dsupar[x] = find(dsupar[x]);
}

void merge(int x,int y,int w){
	int x0 = find(x);
	int y0 = find(y);
	if(x0 == y0){
		extra[x].pb({y,w});
		extra[y].pb({x,w});
		return;
	}
	adj[x].pb({y,w});
	adj[y].pb({x,w});

	if(dsusz[x0] > dsusz[y0]) swap(x0,y0);
	dsupar[x0] = y0;
	dsusz[y0] += dsusz[x0]; 
}

pii par[MAXN][21];
int dep[MAXN],st[MAXN],fin[MAXN];
int dp[MAXN],dp_par[MAXN],val[MAXN];
int tim = 0;

void dfs0(int u,int p,int w,int d){
	val[u] = INF;
	if(extra[u].size()) remin(val[u],extra[u][0].S);
	if(adj[u].size() >= 3) remin(val[u],adj[u][2].S);
	dp[u] = val[u];
	dp_par[u] = val[u];
	st[u] = tim++;
	par[u][0] = {p,w};
	dep[u] = d;
	for(auto v:adj[u]){
		if(v.F != p){
			dfs0(v.F,u,v.S,d+1);
			remin(dp[u],max(v.S,dp[v.F]));
		}
	}
	fin[u] = tim;
}

void dfs_par(int u){
	vpii gg;
	for(auto v:adj[u]){
		if(v.F == par[u][0].F) continue;
		remin(dp_par[v.F],max(v.S,dp_par[u]));
		gg.pb({max(v.S,dp[v.F]),v.S});
	}
	sort(all(gg));
	for(auto v:adj[u]){
		if(v.F == par[u][0].F) continue;
		if(v.F == gg[0].S){
			if(gg.size() != 1){
				remin(dp_par[v.F],max(v.S,gg[1].F));
			}
		}
		else{
			remin(dp_par[v.F],max(v.S,gg[0].F));
		}
		dfs_par(v.F);
	}
}

void init(int N, int M,vi U, vi V, vi W) {
	n = N;
	m = M;
	REP(i,m) edges.pb({W[i],{U[i],V[i]}});
	REP(i,N){
		dsusz[i] = 1;
		dsupar[i] = i;
	}
	sort(all(edges));
	REP(i,m) merge(edges[i].S.F,edges[i].S.S,edges[i].F);
	tim = 0;
	dfs0(1,1,0,0);
	dfs_par(1);
	FOR(j,1,21){
		REP(i,n){
			par[i][j].F = par[par[i][j-1].F][j-1].F;
			par[i][j].S = max(par[i][j-1].S,par[par[i][j-1].F][j-1].S);
		}
	}
}

int lca(int u,int v){
	if(dep[u] < dep[v]) swap(u,v);
	int res = 0;
	FORD(j,20,0){
		if(dep[u]-(1<<j) >= dep[v]){
			remax(res,par[u][j].S);
			u = par[u][j].F;
		}
	}
	if(u == v) return res;
	FORD(j,20,0){
		if(par[u][j].F != par[v][j].F){
			remax(res,par[u][j].S);
			remax(res,par[v][j].S);
			u = par[u][j].F;
			v = par[v][j].F;
		}
	}
	remax(res,par[u][0].S);
	remax(res,par[v][0].S);
	return res;
}

int getMinimumFuelCapacity(int x, int y){
	int ans = lca(x,y);
	remax(ans,min(dp[x],dp_par[x]));
	if(ans >= INF) return -1;
	return ans;	
}
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 5248 KB Output is correct
5 Correct 5 ms 5376 KB Output is correct
6 Correct 5 ms 5376 KB Output is correct
7 Correct 4 ms 5376 KB Output is correct
8 Correct 5 ms 5504 KB Output is correct
9 Correct 212 ms 35620 KB Output is correct
10 Correct 229 ms 43888 KB Output is correct
11 Correct 229 ms 40136 KB Output is correct
12 Correct 234 ms 41952 KB Output is correct
13 Correct 207 ms 45804 KB Output is correct
14 Correct 194 ms 33216 KB Output is correct
15 Correct 651 ms 43968 KB Output is correct
16 Correct 519 ms 40044 KB Output is correct
17 Correct 537 ms 43236 KB Output is correct
18 Correct 508 ms 45296 KB Output is correct
19 Correct 129 ms 14580 KB Output is correct
20 Correct 602 ms 44536 KB Output is correct
21 Correct 511 ms 44320 KB Output is correct
22 Correct 531 ms 46672 KB Output is correct
23 Correct 643 ms 41800 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 349 ms 33952 KB Output is correct
4 Correct 273 ms 35204 KB Output is correct
5 Correct 298 ms 34452 KB Output is correct
6 Correct 275 ms 35180 KB Output is correct
7 Correct 281 ms 34800 KB Output is correct
8 Correct 316 ms 33748 KB Output is correct
9 Correct 284 ms 34668 KB Output is correct
10 Correct 273 ms 33488 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 5120 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 5248 KB Output is correct
6 Correct 5 ms 5376 KB Output is correct
7 Correct 5 ms 5376 KB Output is correct
8 Correct 4 ms 5376 KB Output is correct
9 Correct 5 ms 5504 KB Output is correct
10 Correct 5 ms 5376 KB Output is correct
11 Correct 5 ms 5376 KB Output is correct
12 Correct 5 ms 5376 KB Output is correct
13 Correct 4 ms 5248 KB Output is correct
14 Correct 4 ms 5248 KB Output is correct
15 Correct 4 ms 5376 KB Output is correct
16 Correct 4 ms 5376 KB Output is correct
17 Correct 4 ms 5376 KB Output is correct
18 Correct 4 ms 5376 KB Output is correct
19 Correct 4 ms 5248 KB Output is correct
20 Correct 5 ms 5376 KB Output is correct
21 Correct 5 ms 5376 KB Output is correct
22 Correct 4 ms 5248 KB Output is correct
23 Correct 5 ms 5248 KB Output is correct
24 Correct 5 ms 5376 KB Output is correct
25 Correct 5 ms 5376 KB Output is correct
26 Correct 5 ms 5504 KB Output is correct
27 Correct 4 ms 5376 KB Output is correct
28 Correct 5 ms 5376 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 5120 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 5248 KB Output is correct
6 Correct 5 ms 5376 KB Output is correct
7 Correct 5 ms 5376 KB Output is correct
8 Correct 4 ms 5376 KB Output is correct
9 Correct 5 ms 5504 KB Output is correct
10 Correct 212 ms 35620 KB Output is correct
11 Correct 229 ms 43888 KB Output is correct
12 Correct 229 ms 40136 KB Output is correct
13 Correct 234 ms 41952 KB Output is correct
14 Correct 207 ms 45804 KB Output is correct
15 Correct 5 ms 5376 KB Output is correct
16 Correct 5 ms 5376 KB Output is correct
17 Correct 5 ms 5376 KB Output is correct
18 Correct 4 ms 5248 KB Output is correct
19 Correct 4 ms 5248 KB Output is correct
20 Correct 4 ms 5376 KB Output is correct
21 Correct 4 ms 5376 KB Output is correct
22 Correct 4 ms 5376 KB Output is correct
23 Correct 4 ms 5376 KB Output is correct
24 Correct 20 ms 8768 KB Output is correct
25 Correct 212 ms 41068 KB Output is correct
26 Correct 210 ms 35052 KB Output is correct
27 Correct 203 ms 33260 KB Output is correct
28 Correct 210 ms 31596 KB Output is correct
29 Correct 193 ms 31084 KB Output is correct
30 Correct 179 ms 29056 KB Output is correct
31 Correct 220 ms 39276 KB Output is correct
32 Correct 218 ms 37868 KB Output is correct
33 Correct 209 ms 43148 KB Output is correct
34 Correct 189 ms 31852 KB Output is correct
35 Correct 4 ms 5248 KB Output is correct
36 Correct 5 ms 5376 KB Output is correct
37 Correct 5 ms 5376 KB Output is correct
38 Correct 4 ms 5248 KB Output is correct
39 Correct 5 ms 5248 KB Output is correct
40 Correct 5 ms 5376 KB Output is correct
41 Correct 5 ms 5376 KB Output is correct
42 Correct 5 ms 5504 KB Output is correct
43 Correct 4 ms 5376 KB Output is correct
44 Correct 5 ms 5376 KB Output is correct
45 Correct 212 ms 30892 KB Output is correct
46 Correct 218 ms 34748 KB Output is correct
47 Correct 191 ms 31464 KB Output is correct
48 Correct 191 ms 32108 KB Output is correct
49 Correct 100 ms 15720 KB Output is correct
50 Correct 87 ms 14188 KB Output is correct
51 Correct 169 ms 26604 KB Output is correct
52 Correct 263 ms 38632 KB Output is correct
53 Correct 296 ms 38264 KB Output is correct
54 Correct 326 ms 45412 KB Output is correct
55 Correct 196 ms 42480 KB Output is correct
56 Correct 302 ms 37096 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 5248 KB Output is correct
5 Correct 5 ms 5376 KB Output is correct
6 Correct 5 ms 5376 KB Output is correct
7 Correct 4 ms 5376 KB Output is correct
8 Correct 5 ms 5504 KB Output is correct
9 Correct 212 ms 35620 KB Output is correct
10 Correct 229 ms 43888 KB Output is correct
11 Correct 229 ms 40136 KB Output is correct
12 Correct 234 ms 41952 KB Output is correct
13 Correct 207 ms 45804 KB Output is correct
14 Correct 194 ms 33216 KB Output is correct
15 Correct 651 ms 43968 KB Output is correct
16 Correct 519 ms 40044 KB Output is correct
17 Correct 537 ms 43236 KB Output is correct
18 Correct 508 ms 45296 KB Output is correct
19 Correct 349 ms 33952 KB Output is correct
20 Correct 273 ms 35204 KB Output is correct
21 Correct 298 ms 34452 KB Output is correct
22 Correct 275 ms 35180 KB Output is correct
23 Correct 281 ms 34800 KB Output is correct
24 Correct 316 ms 33748 KB Output is correct
25 Correct 284 ms 34668 KB Output is correct
26 Correct 273 ms 33488 KB Output is correct
27 Correct 5 ms 5376 KB Output is correct
28 Correct 5 ms 5376 KB Output is correct
29 Correct 5 ms 5376 KB Output is correct
30 Correct 4 ms 5248 KB Output is correct
31 Correct 4 ms 5248 KB Output is correct
32 Correct 4 ms 5376 KB Output is correct
33 Correct 4 ms 5376 KB Output is correct
34 Correct 4 ms 5376 KB Output is correct
35 Correct 4 ms 5376 KB Output is correct
36 Correct 20 ms 8768 KB Output is correct
37 Correct 212 ms 41068 KB Output is correct
38 Correct 210 ms 35052 KB Output is correct
39 Correct 203 ms 33260 KB Output is correct
40 Correct 210 ms 31596 KB Output is correct
41 Correct 193 ms 31084 KB Output is correct
42 Correct 179 ms 29056 KB Output is correct
43 Correct 220 ms 39276 KB Output is correct
44 Correct 218 ms 37868 KB Output is correct
45 Correct 209 ms 43148 KB Output is correct
46 Correct 189 ms 31852 KB Output is correct
47 Correct 30 ms 8760 KB Output is correct
48 Correct 513 ms 41044 KB Output is correct
49 Correct 502 ms 37328 KB Output is correct
50 Correct 480 ms 35800 KB Output is correct
51 Correct 442 ms 34912 KB Output is correct
52 Correct 393 ms 32668 KB Output is correct
53 Correct 296 ms 26592 KB Output is correct
54 Correct 526 ms 39380 KB Output is correct
55 Correct 518 ms 40656 KB Output is correct
56 Correct 465 ms 45780 KB Output is correct
57 Correct 375 ms 35028 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 5120 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 5248 KB Output is correct
6 Correct 5 ms 5376 KB Output is correct
7 Correct 5 ms 5376 KB Output is correct
8 Correct 4 ms 5376 KB Output is correct
9 Correct 5 ms 5504 KB Output is correct
10 Correct 212 ms 35620 KB Output is correct
11 Correct 229 ms 43888 KB Output is correct
12 Correct 229 ms 40136 KB Output is correct
13 Correct 234 ms 41952 KB Output is correct
14 Correct 207 ms 45804 KB Output is correct
15 Correct 194 ms 33216 KB Output is correct
16 Correct 651 ms 43968 KB Output is correct
17 Correct 519 ms 40044 KB Output is correct
18 Correct 537 ms 43236 KB Output is correct
19 Correct 508 ms 45296 KB Output is correct
20 Correct 349 ms 33952 KB Output is correct
21 Correct 273 ms 35204 KB Output is correct
22 Correct 298 ms 34452 KB Output is correct
23 Correct 275 ms 35180 KB Output is correct
24 Correct 281 ms 34800 KB Output is correct
25 Correct 316 ms 33748 KB Output is correct
26 Correct 284 ms 34668 KB Output is correct
27 Correct 273 ms 33488 KB Output is correct
28 Correct 5 ms 5376 KB Output is correct
29 Correct 5 ms 5376 KB Output is correct
30 Correct 5 ms 5376 KB Output is correct
31 Correct 4 ms 5248 KB Output is correct
32 Correct 4 ms 5248 KB Output is correct
33 Correct 4 ms 5376 KB Output is correct
34 Correct 4 ms 5376 KB Output is correct
35 Correct 4 ms 5376 KB Output is correct
36 Correct 4 ms 5376 KB Output is correct
37 Correct 20 ms 8768 KB Output is correct
38 Correct 212 ms 41068 KB Output is correct
39 Correct 210 ms 35052 KB Output is correct
40 Correct 203 ms 33260 KB Output is correct
41 Correct 210 ms 31596 KB Output is correct
42 Correct 193 ms 31084 KB Output is correct
43 Correct 179 ms 29056 KB Output is correct
44 Correct 220 ms 39276 KB Output is correct
45 Correct 218 ms 37868 KB Output is correct
46 Correct 209 ms 43148 KB Output is correct
47 Correct 189 ms 31852 KB Output is correct
48 Correct 30 ms 8760 KB Output is correct
49 Correct 513 ms 41044 KB Output is correct
50 Correct 502 ms 37328 KB Output is correct
51 Correct 480 ms 35800 KB Output is correct
52 Correct 442 ms 34912 KB Output is correct
53 Correct 393 ms 32668 KB Output is correct
54 Correct 296 ms 26592 KB Output is correct
55 Correct 526 ms 39380 KB Output is correct
56 Correct 518 ms 40656 KB Output is correct
57 Correct 465 ms 45780 KB Output is correct
58 Correct 375 ms 35028 KB Output is correct
59 Correct 129 ms 14580 KB Output is correct
60 Correct 602 ms 44536 KB Output is correct
61 Correct 511 ms 44320 KB Output is correct
62 Correct 531 ms 46672 KB Output is correct
63 Correct 643 ms 41800 KB Output is correct
64 Correct 4 ms 5248 KB Output is correct
65 Correct 5 ms 5376 KB Output is correct
66 Correct 5 ms 5376 KB Output is correct
67 Correct 4 ms 5248 KB Output is correct
68 Correct 5 ms 5248 KB Output is correct
69 Correct 5 ms 5376 KB Output is correct
70 Correct 5 ms 5376 KB Output is correct
71 Correct 5 ms 5504 KB Output is correct
72 Correct 4 ms 5376 KB Output is correct
73 Correct 5 ms 5376 KB Output is correct
74 Correct 212 ms 30892 KB Output is correct
75 Correct 218 ms 34748 KB Output is correct
76 Correct 191 ms 31464 KB Output is correct
77 Correct 191 ms 32108 KB Output is correct
78 Correct 100 ms 15720 KB Output is correct
79 Correct 87 ms 14188 KB Output is correct
80 Correct 169 ms 26604 KB Output is correct
81 Correct 263 ms 38632 KB Output is correct
82 Correct 296 ms 38264 KB Output is correct
83 Correct 326 ms 45412 KB Output is correct
84 Correct 196 ms 42480 KB Output is correct
85 Correct 302 ms 37096 KB Output is correct
86 Correct 99 ms 15396 KB Output is correct
87 Correct 495 ms 36436 KB Output is correct
88 Correct 479 ms 37204 KB Output is correct
89 Correct 347 ms 33288 KB Output is correct
90 Correct 210 ms 17600 KB Output is correct
91 Correct 234 ms 18956 KB Output is correct
92 Correct 344 ms 29260 KB Output is correct
93 Correct 534 ms 41632 KB Output is correct
94 Correct 445 ms 39876 KB Output is correct
95 Correct 609 ms 47608 KB Output is correct
96 Correct 487 ms 42872 KB Output is correct
97 Correct 410 ms 37672 KB Output is correct