답안 #410209

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
410209	2021-05-22T09:30:49 Z	CSQ31	자매 도시 (APIO20_swap)	C++14	100 / 100	622 ms	93732 KB

swap

#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
const int MAXN = 3e5+5;
vii adj(MAXN);
int cnt = 0;
vector<int>p(MAXN),deg(MAXN),ans(MAXN,2e9);
vector<bool>can(MAXN);
vii mn(20,vector<int>(MAXN,2e9)),par(20,vector<int>(MAXN,0));
int find(int x){
	if(p[x] == x)return x;
	else return p[x] = find(p[x]);
}
bool unite(int a,int b){
	a = find(a);
	b = find(b);
	if(a==b)return 0;
	p[a] = p[b] = cnt;
	can[cnt] = can[a] | can[b];
	
	adj[cnt].pb(a);
	adj[cnt].pb(b);
	cnt++;
	return 1;
}
ll tin[MAXN],tout[MAXN],depth[MAXN];
int timer = 0;
void euler(int v,int u){
	tin[v] = timer++;
	for(int x:adj[v]){
		if(x == u)continue;
		euler(x,v);
	}
	tout[v] = timer;
}
void dfs(int v,int u){
	tin[v] = timer++;
	if(can[v])mn[0][v] = ans[v];
	for(int x:adj[v]){
	    if(x == u)continue;	
	    par[0][x] = v;
	   if(can[x]) mn[0][x] = ans[x];
	   if(can[v]) mn[0][x] = min(mn[0][x],ans[v]);
	    depth[x] = depth[v]+1;
	    for(int i=1;i<=19;i++){
			par[i][x] = par[i-1][par[i-1][x]];
			mn[i][x] = min(mn[i-1][x],mn[i-1][par[i-1][x]]);
		}
		dfs(x,v);
	}
	tout[v] = timer;
}
bool ancestor(int v,int u){return(tin[v] >= tin[u] && tout[u] >= tout[v]);}//is u an ancestor of v?
int lca(int v,int u){
	if(depth[v] > depth[u])swap(u,v);
	int dist = depth[u]-depth[v];
	for(int i=0;dist;i++,dist>>=1){
		if(dist&1)u = par[i][u];
	}
	if(u == v)return u;
	for(int i=19;i>=0;i--){
		if(par[i][v] != par[i][u]){
			u = par[i][u];
			v = par[i][v];
		}
	}
	return par[0][v];
}	
void init(int n, int m,vector<int> u,vector<int> v,vector<int> w) {
	vector<pair<int,pii>>e;
	cnt=n+1;
	for(int i=1;i<=n+m;i++)p[i] = i;
	for(int i=0;i<m;i++)e.pb({w[i],{u[i]+1,v[i]+1}});
	sort(all(e));
	for(auto z : e){
		int ww = z.fi;
		pii v = z.se;
		ans[cnt] = ww;
		if(!unite(v.fi,v.se)){
			adj[cnt].pb(find(v.fi));
			p[find(v.fi)] = cnt;
			can[cnt] = 1;
			cnt++;
		}
		else{
			deg[v.fi]++;
			deg[v.se]++;
			if(deg[v.fi]>=3 || deg[v.se]>=3)can[find(v.fi)] = 1;
		}
	}
	dfs(cnt-1,-1);
}

int getMinimumFuelCapacity(int x, int y) {
	int v = lca(x+1,y+1);
	int a = mn[0][v];
	//cout<<v<<'\n';
	for(int i=19;i>=0;i--){
		if(par[i][v]){
			a = min(a,mn[i][v]);
			v = par[i][v];
		}
	}
	if(a == 2e9)a=-1;
	return a;
}

Subtask #1

6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	58952 KB	Output is correct
2	Correct	28 ms	58988 KB	Output is correct
3	Correct	27 ms	58976 KB	Output is correct
4	Correct	29 ms	59056 KB	Output is correct
5	Correct	30 ms	59024 KB	Output is correct
6	Correct	28 ms	59064 KB	Output is correct
7	Correct	29 ms	59120 KB	Output is correct
8	Correct	29 ms	59064 KB	Output is correct
9	Correct	191 ms	68124 KB	Output is correct
10	Correct	227 ms	70064 KB	Output is correct
11	Correct	225 ms	70000 KB	Output is correct
12	Correct	234 ms	70636 KB	Output is correct
13	Correct	199 ms	75952 KB	Output is correct
14	Correct	205 ms	68248 KB	Output is correct
15	Correct	410 ms	71768 KB	Output is correct
16	Correct	401 ms	71376 KB	Output is correct
17	Correct	420 ms	72112 KB	Output is correct
18	Correct	513 ms	77488 KB	Output is correct
19	Correct	136 ms	64176 KB	Output is correct
20	Correct	400 ms	72192 KB	Output is correct
21	Correct	411 ms	72056 KB	Output is correct
22	Correct	430 ms	72748 KB	Output is correct
23	Correct	479 ms	78236 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	58952 KB	Output is correct
2	Correct	28 ms	58988 KB	Output is correct
3	Correct	490 ms	82488 KB	Output is correct
4	Correct	472 ms	83252 KB	Output is correct
5	Correct	489 ms	82768 KB	Output is correct
6	Correct	468 ms	83212 KB	Output is correct
7	Correct	502 ms	83080 KB	Output is correct
8	Correct	478 ms	82188 KB	Output is correct
9	Correct	476 ms	82836 KB	Output is correct
10	Correct	465 ms	81996 KB	Output is correct

Subtask #3

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	58952 KB	Output is correct
2	Correct	28 ms	58988 KB	Output is correct
3	Correct	27 ms	58976 KB	Output is correct
4	Correct	29 ms	59056 KB	Output is correct
5	Correct	30 ms	59024 KB	Output is correct
6	Correct	28 ms	59064 KB	Output is correct
7	Correct	29 ms	59120 KB	Output is correct
8	Correct	29 ms	59064 KB	Output is correct
9	Correct	27 ms	59016 KB	Output is correct
10	Correct	28 ms	59136 KB	Output is correct
11	Correct	29 ms	59004 KB	Output is correct
12	Correct	30 ms	59040 KB	Output is correct
13	Correct	29 ms	59024 KB	Output is correct
14	Correct	28 ms	59064 KB	Output is correct
15	Correct	29 ms	59032 KB	Output is correct
16	Correct	28 ms	59092 KB	Output is correct
17	Correct	29 ms	59068 KB	Output is correct
18	Correct	29 ms	58992 KB	Output is correct
19	Correct	29 ms	59128 KB	Output is correct
20	Correct	28 ms	59068 KB	Output is correct
21	Correct	29 ms	59064 KB	Output is correct
22	Correct	29 ms	59204 KB	Output is correct
23	Correct	29 ms	59004 KB	Output is correct
24	Correct	30 ms	59144 KB	Output is correct
25	Correct	30 ms	59196 KB	Output is correct
26	Correct	30 ms	59180 KB	Output is correct
27	Correct	29 ms	59056 KB	Output is correct
28	Correct	29 ms	59188 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	59016 KB	Output is correct
2	Correct	27 ms	58952 KB	Output is correct
3	Correct	28 ms	58988 KB	Output is correct
4	Correct	27 ms	58976 KB	Output is correct
5	Correct	29 ms	59056 KB	Output is correct
6	Correct	30 ms	59024 KB	Output is correct
7	Correct	28 ms	59064 KB	Output is correct
8	Correct	29 ms	59120 KB	Output is correct
9	Correct	29 ms	59064 KB	Output is correct
10	Correct	191 ms	68124 KB	Output is correct
11	Correct	227 ms	70064 KB	Output is correct
12	Correct	225 ms	70000 KB	Output is correct
13	Correct	234 ms	70636 KB	Output is correct
14	Correct	199 ms	75952 KB	Output is correct
15	Correct	28 ms	59136 KB	Output is correct
16	Correct	29 ms	59004 KB	Output is correct
17	Correct	30 ms	59040 KB	Output is correct
18	Correct	29 ms	59024 KB	Output is correct
19	Correct	28 ms	59064 KB	Output is correct
20	Correct	29 ms	59032 KB	Output is correct
21	Correct	28 ms	59092 KB	Output is correct
22	Correct	29 ms	59068 KB	Output is correct
23	Correct	29 ms	58992 KB	Output is correct
24	Correct	29 ms	59128 KB	Output is correct
25	Correct	28 ms	59068 KB	Output is correct
26	Correct	29 ms	59064 KB	Output is correct
27	Correct	29 ms	59204 KB	Output is correct
28	Correct	29 ms	59004 KB	Output is correct
29	Correct	30 ms	59144 KB	Output is correct
30	Correct	30 ms	59196 KB	Output is correct
31	Correct	30 ms	59180 KB	Output is correct
32	Correct	29 ms	59056 KB	Output is correct
33	Correct	29 ms	59188 KB	Output is correct
34	Correct	46 ms	59960 KB	Output is correct
35	Correct	238 ms	70544 KB	Output is correct
36	Correct	245 ms	70576 KB	Output is correct
37	Correct	244 ms	70568 KB	Output is correct
38	Correct	235 ms	70424 KB	Output is correct
39	Correct	233 ms	70428 KB	Output is correct
40	Correct	214 ms	69408 KB	Output is correct
41	Correct	242 ms	70572 KB	Output is correct
42	Correct	239 ms	70448 KB	Output is correct
43	Correct	197 ms	77728 KB	Output is correct
44	Correct	239 ms	70608 KB	Output is correct
45	Correct	255 ms	84480 KB	Output is correct
46	Correct	238 ms	70528 KB	Output is correct
47	Correct	232 ms	70960 KB	Output is correct
48	Correct	235 ms	75732 KB	Output is correct
49	Correct	162 ms	90668 KB	Output is correct
50	Correct	135 ms	82856 KB	Output is correct
51	Correct	213 ms	81612 KB	Output is correct
52	Correct	297 ms	82800 KB	Output is correct
53	Correct	332 ms	83820 KB	Output is correct
54	Correct	349 ms	90564 KB	Output is correct
55	Correct	222 ms	77036 KB	Output is correct
56	Correct	306 ms	88128 KB	Output is correct

Subtask #5

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	58952 KB	Output is correct
2	Correct	28 ms	58988 KB	Output is correct
3	Correct	27 ms	58976 KB	Output is correct
4	Correct	29 ms	59056 KB	Output is correct
5	Correct	30 ms	59024 KB	Output is correct
6	Correct	28 ms	59064 KB	Output is correct
7	Correct	29 ms	59120 KB	Output is correct
8	Correct	29 ms	59064 KB	Output is correct
9	Correct	191 ms	68124 KB	Output is correct
10	Correct	227 ms	70064 KB	Output is correct
11	Correct	225 ms	70000 KB	Output is correct
12	Correct	234 ms	70636 KB	Output is correct
13	Correct	199 ms	75952 KB	Output is correct
14	Correct	205 ms	68248 KB	Output is correct
15	Correct	410 ms	71768 KB	Output is correct
16	Correct	401 ms	71376 KB	Output is correct
17	Correct	420 ms	72112 KB	Output is correct
18	Correct	513 ms	77488 KB	Output is correct
19	Correct	490 ms	82488 KB	Output is correct
20	Correct	472 ms	83252 KB	Output is correct
21	Correct	489 ms	82768 KB	Output is correct
22	Correct	468 ms	83212 KB	Output is correct
23	Correct	502 ms	83080 KB	Output is correct
24	Correct	478 ms	82188 KB	Output is correct
25	Correct	476 ms	82836 KB	Output is correct
26	Correct	465 ms	81996 KB	Output is correct
27	Correct	28 ms	59136 KB	Output is correct
28	Correct	29 ms	59004 KB	Output is correct
29	Correct	30 ms	59040 KB	Output is correct
30	Correct	29 ms	59024 KB	Output is correct
31	Correct	28 ms	59064 KB	Output is correct
32	Correct	29 ms	59032 KB	Output is correct
33	Correct	28 ms	59092 KB	Output is correct
34	Correct	29 ms	59068 KB	Output is correct
35	Correct	29 ms	58992 KB	Output is correct
36	Correct	46 ms	59960 KB	Output is correct
37	Correct	238 ms	70544 KB	Output is correct
38	Correct	245 ms	70576 KB	Output is correct
39	Correct	244 ms	70568 KB	Output is correct
40	Correct	235 ms	70424 KB	Output is correct
41	Correct	233 ms	70428 KB	Output is correct
42	Correct	214 ms	69408 KB	Output is correct
43	Correct	242 ms	70572 KB	Output is correct
44	Correct	239 ms	70448 KB	Output is correct
45	Correct	197 ms	77728 KB	Output is correct
46	Correct	239 ms	70608 KB	Output is correct
47	Correct	57 ms	60208 KB	Output is correct
48	Correct	433 ms	72024 KB	Output is correct
49	Correct	417 ms	72092 KB	Output is correct
50	Correct	421 ms	71960 KB	Output is correct
51	Correct	416 ms	72016 KB	Output is correct
52	Correct	399 ms	71396 KB	Output is correct
53	Correct	325 ms	70048 KB	Output is correct
54	Correct	435 ms	72728 KB	Output is correct
55	Correct	442 ms	72040 KB	Output is correct
56	Correct	485 ms	77796 KB	Output is correct
57	Correct	448 ms	72860 KB	Output is correct

Subtask #6

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	59016 KB	Output is correct
2	Correct	27 ms	58952 KB	Output is correct
3	Correct	28 ms	58988 KB	Output is correct
4	Correct	27 ms	58976 KB	Output is correct
5	Correct	29 ms	59056 KB	Output is correct
6	Correct	30 ms	59024 KB	Output is correct
7	Correct	28 ms	59064 KB	Output is correct
8	Correct	29 ms	59120 KB	Output is correct
9	Correct	29 ms	59064 KB	Output is correct
10	Correct	191 ms	68124 KB	Output is correct
11	Correct	227 ms	70064 KB	Output is correct
12	Correct	225 ms	70000 KB	Output is correct
13	Correct	234 ms	70636 KB	Output is correct
14	Correct	199 ms	75952 KB	Output is correct
15	Correct	205 ms	68248 KB	Output is correct
16	Correct	410 ms	71768 KB	Output is correct
17	Correct	401 ms	71376 KB	Output is correct
18	Correct	420 ms	72112 KB	Output is correct
19	Correct	513 ms	77488 KB	Output is correct
20	Correct	490 ms	82488 KB	Output is correct
21	Correct	472 ms	83252 KB	Output is correct
22	Correct	489 ms	82768 KB	Output is correct
23	Correct	468 ms	83212 KB	Output is correct
24	Correct	502 ms	83080 KB	Output is correct
25	Correct	478 ms	82188 KB	Output is correct
26	Correct	476 ms	82836 KB	Output is correct
27	Correct	465 ms	81996 KB	Output is correct
28	Correct	28 ms	59136 KB	Output is correct
29	Correct	29 ms	59004 KB	Output is correct
30	Correct	30 ms	59040 KB	Output is correct
31	Correct	29 ms	59024 KB	Output is correct
32	Correct	28 ms	59064 KB	Output is correct
33	Correct	29 ms	59032 KB	Output is correct
34	Correct	28 ms	59092 KB	Output is correct
35	Correct	29 ms	59068 KB	Output is correct
36	Correct	29 ms	58992 KB	Output is correct
37	Correct	46 ms	59960 KB	Output is correct
38	Correct	238 ms	70544 KB	Output is correct
39	Correct	245 ms	70576 KB	Output is correct
40	Correct	244 ms	70568 KB	Output is correct
41	Correct	235 ms	70424 KB	Output is correct
42	Correct	233 ms	70428 KB	Output is correct
43	Correct	214 ms	69408 KB	Output is correct
44	Correct	242 ms	70572 KB	Output is correct
45	Correct	239 ms	70448 KB	Output is correct
46	Correct	197 ms	77728 KB	Output is correct
47	Correct	239 ms	70608 KB	Output is correct
48	Correct	57 ms	60208 KB	Output is correct
49	Correct	433 ms	72024 KB	Output is correct
50	Correct	417 ms	72092 KB	Output is correct
51	Correct	421 ms	71960 KB	Output is correct
52	Correct	416 ms	72016 KB	Output is correct
53	Correct	399 ms	71396 KB	Output is correct
54	Correct	325 ms	70048 KB	Output is correct
55	Correct	435 ms	72728 KB	Output is correct
56	Correct	442 ms	72040 KB	Output is correct
57	Correct	485 ms	77796 KB	Output is correct
58	Correct	448 ms	72860 KB	Output is correct
59	Correct	136 ms	64176 KB	Output is correct
60	Correct	400 ms	72192 KB	Output is correct
61	Correct	411 ms	72056 KB	Output is correct
62	Correct	430 ms	72748 KB	Output is correct
63	Correct	479 ms	78236 KB	Output is correct
64	Correct	29 ms	59128 KB	Output is correct
65	Correct	28 ms	59068 KB	Output is correct
66	Correct	29 ms	59064 KB	Output is correct
67	Correct	29 ms	59204 KB	Output is correct
68	Correct	29 ms	59004 KB	Output is correct
69	Correct	30 ms	59144 KB	Output is correct
70	Correct	30 ms	59196 KB	Output is correct
71	Correct	30 ms	59180 KB	Output is correct
72	Correct	29 ms	59056 KB	Output is correct
73	Correct	29 ms	59188 KB	Output is correct
74	Correct	255 ms	84480 KB	Output is correct
75	Correct	238 ms	70528 KB	Output is correct
76	Correct	232 ms	70960 KB	Output is correct
77	Correct	235 ms	75732 KB	Output is correct
78	Correct	162 ms	90668 KB	Output is correct
79	Correct	135 ms	82856 KB	Output is correct
80	Correct	213 ms	81612 KB	Output is correct
81	Correct	297 ms	82800 KB	Output is correct
82	Correct	332 ms	83820 KB	Output is correct
83	Correct	349 ms	90564 KB	Output is correct
84	Correct	222 ms	77036 KB	Output is correct
85	Correct	306 ms	88128 KB	Output is correct
86	Correct	150 ms	68172 KB	Output is correct
87	Correct	418 ms	72052 KB	Output is correct
88	Correct	419 ms	72084 KB	Output is correct
89	Correct	511 ms	76756 KB	Output is correct
90	Correct	295 ms	93732 KB	Output is correct
91	Correct	320 ms	89708 KB	Output is correct
92	Correct	486 ms	82116 KB	Output is correct
93	Correct	508 ms	83644 KB	Output is correct
94	Correct	622 ms	85416 KB	Output is correct
95	Correct	551 ms	91772 KB	Output is correct
96	Correct	490 ms	78160 KB	Output is correct
97	Correct	566 ms	82288 KB	Output is correct