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

swap

/*
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;	
}

Subtask #1

6.0 / 6.0

#	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

Subtask #2

7.0 / 7.0

#	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

Subtask #3

17.0 / 17.0

#	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

Subtask #4

20.0 / 20.0

#	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

Subtask #5

23.0 / 23.0

#	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

Subtask #6

27.0 / 27.0

#	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