답안 #369375

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
369375	2021-02-21T13:09:45 Z	YJU	자매 도시 (APIO20_swap)	C++14	100 / 100	550 ms	118636 KB

swap

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=1e6+5;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

struct edge{
	ll x,y,c;
	bool operator <(edge B){
		return c<B.c;
	}
}ed[N];

ll dir[N],cnt[N][2],weight[N],anc[N][20],dg[N],ptr;
vector<ll> v[N];

ll f(ll id){
	return (dir[id]==id?id:dir[id]=f(dir[id]));
}

void uni(ll par,ll son){
	cnt[par][0]+=cnt[son][0];
	cnt[par][1]+=cnt[son][1];
	dir[son]=par;
	v[par].pb(son);
}

ll dcnt=1,in[N],out[N];

bool is_anc(ll x,ll y){//x is y's ancestor? true : false
	return (in[x]<in[y]&&out[x]>out[y]);
}

void DFS(ll nd,ll pa){
	in[nd]=dcnt++;
	for(int i=1;i<20;i++){
		anc[nd][i]=anc[anc[nd][i-1]][i-1];
	}
	for(auto i:v[nd]){
		if(weight[i]==INF)weight[i]=weight[nd];
		//weight[i]=min(weight[i],weight[nd]);
		DFS(i,nd);
	}
	out[nd]=dcnt++;
}

void init(int _n,int _m,vector<int> _u,vector<int> _v,vector<int> _w){
	//prepare
	REP(i,N)dir[i]=i;
	ptr=_n;
	//
	REP(i,_m){
		ed[i].x=_u[i]+1,ed[i].y=_v[i]+1,ed[i].c=_w[i];
	}
	sort(ed,ed+_m);
	REP(i,_m){
		ll x=ed[i].x,y=ed[i].y;
		//cnt[i][0] for degree ==1,cnt[i][1] for degree >=3
		if(dg[x]==1)--cnt[f(x)][0];
		if(dg[y]==1)--cnt[f(y)][0];
		++dg[x];++dg[y];
		if(dg[x]==1)++cnt[f(x)][0];
		if(dg[y]==1)++cnt[f(y)][0];
		if(dg[x]==3)++cnt[f(x)][1];
		if(dg[y]==3)++cnt[f(y)][1];
		//
		weight[++ptr]=INF;
		if(f(x)==f(y)){
			anc[f(x)][0]=ptr;
			uni(ptr,f(x));
		}else{
			anc[f(x)][0]=ptr;
			anc[f(y)][0]=ptr;
			uni(ptr,f(x));
			uni(ptr,f(y));
		}
		if(cnt[ptr][0]==0||cnt[ptr][1]){
			weight[ptr]=ed[i].c;
		}
	}
	REP1(i,ptr){
		if(!anc[i][0])DFS(i,0);
	}
}

ll lca(ll nda,ll ndb){
	if(is_anc(nda,ndb))return nda;
	for(int i=19;i>=0;i--){
		if(anc[nda][i]&&!is_anc(anc[nda][i],ndb))nda=anc[nda][i];
	}
	return anc[nda][0];
}

int getMinimumFuelCapacity(int nda,int ndb){
	++nda;++ndb;
	return (f(nda)==f(ndb)?(weight[lca(nda,ndb)]==INF?-1:weight[lca(nda,ndb)]):-1);
}
/*
ll get(ll nda,ll ndb){
	return getMinimumFuelCapacity(nda,ndb);
}

int a[]={0,0};
int b[]={1,2};
int c[]={5,5};

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	init(3,2,a,b,c);
	cout<<get(1,2)<<"\n";
	return 0;
}

*/

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	31724 KB	Output is correct
2	Correct	21 ms	31724 KB	Output is correct
3	Correct	21 ms	31724 KB	Output is correct
4	Correct	24 ms	31852 KB	Output is correct
5	Correct	22 ms	32112 KB	Output is correct
6	Correct	23 ms	32236 KB	Output is correct
7	Correct	22 ms	32236 KB	Output is correct
8	Correct	22 ms	32236 KB	Output is correct
9	Correct	159 ms	70252 KB	Output is correct
10	Correct	186 ms	78828 KB	Output is correct
11	Correct	180 ms	78060 KB	Output is correct
12	Correct	193 ms	80876 KB	Output is correct
13	Correct	211 ms	83180 KB	Output is correct
14	Correct	169 ms	70464 KB	Output is correct
15	Correct	297 ms	83316 KB	Output is correct
16	Correct	331 ms	82072 KB	Output is correct
17	Correct	303 ms	84944 KB	Output is correct
18	Correct	418 ms	87376 KB	Output is correct
19	Correct	109 ms	44652 KB	Output is correct
20	Correct	295 ms	84600 KB	Output is correct
21	Correct	294 ms	83040 KB	Output is correct
22	Correct	314 ms	86224 KB	Output is correct
23	Correct	434 ms	88656 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	31724 KB	Output is correct
2	Correct	21 ms	31724 KB	Output is correct
3	Correct	466 ms	87436 KB	Output is correct
4	Correct	404 ms	89944 KB	Output is correct
5	Correct	415 ms	88640 KB	Output is correct
6	Correct	399 ms	89644 KB	Output is correct
7	Correct	421 ms	89320 KB	Output is correct
8	Correct	404 ms	87132 KB	Output is correct
9	Correct	432 ms	88936 KB	Output is correct
10	Correct	411 ms	86692 KB	Output is correct

Subtask #3
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	31724 KB	Output is correct
2	Correct	21 ms	31724 KB	Output is correct
3	Correct	21 ms	31724 KB	Output is correct
4	Correct	24 ms	31852 KB	Output is correct
5	Correct	22 ms	32112 KB	Output is correct
6	Correct	23 ms	32236 KB	Output is correct
7	Correct	22 ms	32236 KB	Output is correct
8	Correct	22 ms	32236 KB	Output is correct
9	Correct	23 ms	31724 KB	Output is correct
10	Correct	22 ms	32256 KB	Output is correct
11	Correct	22 ms	32108 KB	Output is correct
12	Correct	22 ms	32108 KB	Output is correct
13	Correct	21 ms	32108 KB	Output is correct
14	Correct	21 ms	32108 KB	Output is correct
15	Correct	23 ms	32236 KB	Output is correct
16	Correct	22 ms	32108 KB	Output is correct
17	Correct	22 ms	32236 KB	Output is correct
18	Correct	22 ms	32108 KB	Output is correct
19	Correct	24 ms	32108 KB	Output is correct
20	Correct	22 ms	32108 KB	Output is correct
21	Correct	25 ms	32236 KB	Output is correct
22	Correct	22 ms	32364 KB	Output is correct
23	Correct	22 ms	32108 KB	Output is correct
24	Correct	23 ms	32364 KB	Output is correct
25	Correct	23 ms	32492 KB	Output is correct
26	Correct	22 ms	32492 KB	Output is correct
27	Correct	22 ms	32236 KB	Output is correct
28	Correct	22 ms	32492 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	31724 KB	Output is correct
2	Correct	21 ms	31724 KB	Output is correct
3	Correct	21 ms	31724 KB	Output is correct
4	Correct	21 ms	31724 KB	Output is correct
5	Correct	24 ms	31852 KB	Output is correct
6	Correct	22 ms	32112 KB	Output is correct
7	Correct	23 ms	32236 KB	Output is correct
8	Correct	22 ms	32236 KB	Output is correct
9	Correct	22 ms	32236 KB	Output is correct
10	Correct	159 ms	70252 KB	Output is correct
11	Correct	186 ms	78828 KB	Output is correct
12	Correct	180 ms	78060 KB	Output is correct
13	Correct	193 ms	80876 KB	Output is correct
14	Correct	211 ms	83180 KB	Output is correct
15	Correct	22 ms	32256 KB	Output is correct
16	Correct	22 ms	32108 KB	Output is correct
17	Correct	22 ms	32108 KB	Output is correct
18	Correct	21 ms	32108 KB	Output is correct
19	Correct	21 ms	32108 KB	Output is correct
20	Correct	23 ms	32236 KB	Output is correct
21	Correct	22 ms	32108 KB	Output is correct
22	Correct	22 ms	32236 KB	Output is correct
23	Correct	22 ms	32108 KB	Output is correct
24	Correct	24 ms	32108 KB	Output is correct
25	Correct	22 ms	32108 KB	Output is correct
26	Correct	25 ms	32236 KB	Output is correct
27	Correct	22 ms	32364 KB	Output is correct
28	Correct	22 ms	32108 KB	Output is correct
29	Correct	23 ms	32364 KB	Output is correct
30	Correct	23 ms	32492 KB	Output is correct
31	Correct	22 ms	32492 KB	Output is correct
32	Correct	22 ms	32236 KB	Output is correct
33	Correct	22 ms	32492 KB	Output is correct
34	Correct	38 ms	38380 KB	Output is correct
35	Correct	193 ms	80492 KB	Output is correct
36	Correct	194 ms	80748 KB	Output is correct
37	Correct	193 ms	80492 KB	Output is correct
38	Correct	186 ms	79724 KB	Output is correct
39	Correct	193 ms	79596 KB	Output is correct
40	Correct	184 ms	75628 KB	Output is correct
41	Correct	196 ms	80876 KB	Output is correct
42	Correct	198 ms	80620 KB	Output is correct
43	Correct	205 ms	83692 KB	Output is correct
44	Correct	198 ms	80772 KB	Output is correct
45	Correct	242 ms	94744 KB	Output is correct
46	Correct	202 ms	80620 KB	Output is correct
47	Correct	204 ms	80492 KB	Output is correct
48	Correct	209 ms	85012 KB	Output is correct
49	Correct	173 ms	85408 KB	Output is correct
50	Correct	137 ms	73964 KB	Output is correct
51	Correct	208 ms	85996 KB	Output is correct
52	Correct	273 ms	101868 KB	Output is correct
53	Correct	296 ms	106732 KB	Output is correct
54	Correct	312 ms	114924 KB	Output is correct
55	Correct	186 ms	83308 KB	Output is correct
56	Correct	295 ms	106732 KB	Output is correct

Subtask #5
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	31724 KB	Output is correct
2	Correct	21 ms	31724 KB	Output is correct
3	Correct	21 ms	31724 KB	Output is correct
4	Correct	24 ms	31852 KB	Output is correct
5	Correct	22 ms	32112 KB	Output is correct
6	Correct	23 ms	32236 KB	Output is correct
7	Correct	22 ms	32236 KB	Output is correct
8	Correct	22 ms	32236 KB	Output is correct
9	Correct	159 ms	70252 KB	Output is correct
10	Correct	186 ms	78828 KB	Output is correct
11	Correct	180 ms	78060 KB	Output is correct
12	Correct	193 ms	80876 KB	Output is correct
13	Correct	211 ms	83180 KB	Output is correct
14	Correct	169 ms	70464 KB	Output is correct
15	Correct	297 ms	83316 KB	Output is correct
16	Correct	331 ms	82072 KB	Output is correct
17	Correct	303 ms	84944 KB	Output is correct
18	Correct	418 ms	87376 KB	Output is correct
19	Correct	466 ms	87436 KB	Output is correct
20	Correct	404 ms	89944 KB	Output is correct
21	Correct	415 ms	88640 KB	Output is correct
22	Correct	399 ms	89644 KB	Output is correct
23	Correct	421 ms	89320 KB	Output is correct
24	Correct	404 ms	87132 KB	Output is correct
25	Correct	432 ms	88936 KB	Output is correct
26	Correct	411 ms	86692 KB	Output is correct
27	Correct	22 ms	32256 KB	Output is correct
28	Correct	22 ms	32108 KB	Output is correct
29	Correct	22 ms	32108 KB	Output is correct
30	Correct	21 ms	32108 KB	Output is correct
31	Correct	21 ms	32108 KB	Output is correct
32	Correct	23 ms	32236 KB	Output is correct
33	Correct	22 ms	32108 KB	Output is correct
34	Correct	22 ms	32236 KB	Output is correct
35	Correct	22 ms	32108 KB	Output is correct
36	Correct	38 ms	38380 KB	Output is correct
37	Correct	193 ms	80492 KB	Output is correct
38	Correct	194 ms	80748 KB	Output is correct
39	Correct	193 ms	80492 KB	Output is correct
40	Correct	186 ms	79724 KB	Output is correct
41	Correct	193 ms	79596 KB	Output is correct
42	Correct	184 ms	75628 KB	Output is correct
43	Correct	196 ms	80876 KB	Output is correct
44	Correct	198 ms	80620 KB	Output is correct
45	Correct	205 ms	83692 KB	Output is correct
46	Correct	198 ms	80772 KB	Output is correct
47	Correct	46 ms	38252 KB	Output is correct
48	Correct	304 ms	85488 KB	Output is correct
49	Correct	306 ms	85328 KB	Output is correct
50	Correct	307 ms	85328 KB	Output is correct
51	Correct	302 ms	85120 KB	Output is correct
52	Correct	304 ms	82428 KB	Output is correct
53	Correct	258 ms	70112 KB	Output is correct
54	Correct	310 ms	86352 KB	Output is correct
55	Correct	319 ms	85472 KB	Output is correct
56	Correct	431 ms	87932 KB	Output is correct
57	Correct	329 ms	86352 KB	Output is correct

Subtask #6
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	31724 KB	Output is correct
2	Correct	21 ms	31724 KB	Output is correct
3	Correct	21 ms	31724 KB	Output is correct
4	Correct	21 ms	31724 KB	Output is correct
5	Correct	24 ms	31852 KB	Output is correct
6	Correct	22 ms	32112 KB	Output is correct
7	Correct	23 ms	32236 KB	Output is correct
8	Correct	22 ms	32236 KB	Output is correct
9	Correct	22 ms	32236 KB	Output is correct
10	Correct	159 ms	70252 KB	Output is correct
11	Correct	186 ms	78828 KB	Output is correct
12	Correct	180 ms	78060 KB	Output is correct
13	Correct	193 ms	80876 KB	Output is correct
14	Correct	211 ms	83180 KB	Output is correct
15	Correct	169 ms	70464 KB	Output is correct
16	Correct	297 ms	83316 KB	Output is correct
17	Correct	331 ms	82072 KB	Output is correct
18	Correct	303 ms	84944 KB	Output is correct
19	Correct	418 ms	87376 KB	Output is correct
20	Correct	466 ms	87436 KB	Output is correct
21	Correct	404 ms	89944 KB	Output is correct
22	Correct	415 ms	88640 KB	Output is correct
23	Correct	399 ms	89644 KB	Output is correct
24	Correct	421 ms	89320 KB	Output is correct
25	Correct	404 ms	87132 KB	Output is correct
26	Correct	432 ms	88936 KB	Output is correct
27	Correct	411 ms	86692 KB	Output is correct
28	Correct	22 ms	32256 KB	Output is correct
29	Correct	22 ms	32108 KB	Output is correct
30	Correct	22 ms	32108 KB	Output is correct
31	Correct	21 ms	32108 KB	Output is correct
32	Correct	21 ms	32108 KB	Output is correct
33	Correct	23 ms	32236 KB	Output is correct
34	Correct	22 ms	32108 KB	Output is correct
35	Correct	22 ms	32236 KB	Output is correct
36	Correct	22 ms	32108 KB	Output is correct
37	Correct	38 ms	38380 KB	Output is correct
38	Correct	193 ms	80492 KB	Output is correct
39	Correct	194 ms	80748 KB	Output is correct
40	Correct	193 ms	80492 KB	Output is correct
41	Correct	186 ms	79724 KB	Output is correct
42	Correct	193 ms	79596 KB	Output is correct
43	Correct	184 ms	75628 KB	Output is correct
44	Correct	196 ms	80876 KB	Output is correct
45	Correct	198 ms	80620 KB	Output is correct
46	Correct	205 ms	83692 KB	Output is correct
47	Correct	198 ms	80772 KB	Output is correct
48	Correct	46 ms	38252 KB	Output is correct
49	Correct	304 ms	85488 KB	Output is correct
50	Correct	306 ms	85328 KB	Output is correct
51	Correct	307 ms	85328 KB	Output is correct
52	Correct	302 ms	85120 KB	Output is correct
53	Correct	304 ms	82428 KB	Output is correct
54	Correct	258 ms	70112 KB	Output is correct
55	Correct	310 ms	86352 KB	Output is correct
56	Correct	319 ms	85472 KB	Output is correct
57	Correct	431 ms	87932 KB	Output is correct
58	Correct	329 ms	86352 KB	Output is correct
59	Correct	109 ms	44652 KB	Output is correct
60	Correct	295 ms	84600 KB	Output is correct
61	Correct	294 ms	83040 KB	Output is correct
62	Correct	314 ms	86224 KB	Output is correct
63	Correct	434 ms	88656 KB	Output is correct
64	Correct	24 ms	32108 KB	Output is correct
65	Correct	22 ms	32108 KB	Output is correct
66	Correct	25 ms	32236 KB	Output is correct
67	Correct	22 ms	32364 KB	Output is correct
68	Correct	22 ms	32108 KB	Output is correct
69	Correct	23 ms	32364 KB	Output is correct
70	Correct	23 ms	32492 KB	Output is correct
71	Correct	22 ms	32492 KB	Output is correct
72	Correct	22 ms	32236 KB	Output is correct
73	Correct	22 ms	32492 KB	Output is correct
74	Correct	242 ms	94744 KB	Output is correct
75	Correct	202 ms	80620 KB	Output is correct
76	Correct	204 ms	80492 KB	Output is correct
77	Correct	209 ms	85012 KB	Output is correct
78	Correct	173 ms	85408 KB	Output is correct
79	Correct	137 ms	73964 KB	Output is correct
80	Correct	208 ms	85996 KB	Output is correct
81	Correct	273 ms	101868 KB	Output is correct
82	Correct	296 ms	106732 KB	Output is correct
83	Correct	312 ms	114924 KB	Output is correct
84	Correct	186 ms	83308 KB	Output is correct
85	Correct	295 ms	106732 KB	Output is correct
86	Correct	140 ms	54940 KB	Output is correct
87	Correct	312 ms	85456 KB	Output is correct
88	Correct	302 ms	85584 KB	Output is correct
89	Correct	461 ms	87304 KB	Output is correct
90	Correct	292 ms	92484 KB	Output is correct
91	Correct	352 ms	88592 KB	Output is correct
92	Correct	452 ms	89048 KB	Output is correct
93	Correct	426 ms	105684 KB	Output is correct
94	Correct	550 ms	111108 KB	Output is correct
95	Correct	449 ms	118636 KB	Output is correct
96	Correct	421 ms	88316 KB	Output is correct
97	Correct	510 ms	99244 KB	Output is correct

답안 #369375

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 7.0 / 7.0

Subtask #3 17.0 / 17.0

Subtask #4 20.0 / 20.0

Subtask #5 23.0 / 23.0

Subtask #6 27.0 / 27.0

Subtask #1
6.0 / 6.0

Subtask #2
7.0 / 7.0

Subtask #3
17.0 / 17.0

Subtask #4
20.0 / 20.0

Subtask #5
23.0 / 23.0

Subtask #6
27.0 / 27.0