답안 #679542

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
679542	2023-01-08T13:11:36 Z	Dan4Life	자매 도시 (APIO20_swap)	C++17	6 / 100	479 ms	82756 KB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back

const int maxn = (int)5e5+10;
const int lgn = 20;

int n, m, num;
bool good[maxn];
int jmp[lgn][maxn], goodd[lgn][maxn];
vector<int> adj[maxn];
struct Edge{ int u, v, w; };
int p[maxn], lev[maxn], wei[maxn], deg[maxn];

Edge edge[maxn];

int getPath(int x, int steps){
	for(int i = lgn-1; i >= 0; i--)
		if(steps&(1<<i) and x!=-1) x = jmp[i][x];
	return x; 
}

int lca(int a, int b){
	if(a==b) return a;
	if(jmp[0][a]==jmp[0][b]) return jmp[0][a];
	if(lev[a] < lev[b]) swap(a,b);
	a = getPath(a, lev[a]-lev[b]);
	for(int i = lgn-1; i >= 0; i--)
		if(jmp[i][a]!=-1 and jmp[i][a]!=jmp[i][b])
			a = jmp[i][a], b = jmp[i][b];
	return lca(a,b);
}

int findSet(int i){ return p[i]==i?i:p[i]=findSet(p[i]); }
bool isSameSet(int i, int j) { return findSet(i)==findSet(j); }

void unionSet(Edge &e){
	int i = e.u, j = e.v; wei[num] = e.w;
	int x = findSet(i), y = findSet(j);
	deg[x]++, deg[y]++;
	p[x]=p[y]=p[num]=num;
	if(x!=y) adj[num].pb(y);
	adj[num].pb(x);
	goodd[0][i] = good[num] |= good[x]|good[y]|(deg[x]>=3)|(deg[y]>=3)|(x==y);
	num++;
}

void dfs(int s, int p){
	if(p!=-1) lev[s] = lev[p]+1, jmp[0][s] = p;
	for(auto u : adj[s]) if(u!=p) dfs(u,s);
}

void init(int N, int M, vector<int> u, vector<int> v, vector<int> w) {
	n = N, m = M; num = n; memset(jmp,-1,sizeof(jmp));
	for(int i = 0; i <= n+m; i++) p[i] = i;
	for(int i = 0; i < m; i++) edge[i] = {u[i],v[i],w[i]};
	sort(edge,edge+m,[&](Edge &x, Edge &y){ return x.w<y.w; });
	for(int i = 0; i < m; i++) unionSet(edge[i]);
	dfs(num-1,-1);
	for(int i = 1; i < lgn; i++)
		for(int j = 0; j+(1<<i)-1 < num; j++)
			if(jmp[i-1][j]!=-1) jmp[i][j] = jmp[i-1][jmp[i-1][j]];
	for(int i = 1; i < lgn; i++)
		for(int j = 0; j+(1<<i)-1 < num; j++)
			goodd[i][j] = goodd[i-1][goodd[i-1][j]];
}

int getMinimumFuelCapacity(int x, int y) {
	int z = lca(x,y);
	for(int i = lgn-1; i >= 0; i--) 
		if(jmp[i][z]!=-1 and !goodd[i][z]) z = jmp[i][z];
	if(good[z]) return wei[z];
	if(jmp[0][z]!=-1) z=jmp[0][z];
	return good[z]?wei[z]:-1;
}

/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
*/

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	51156 KB	Output is correct
2	Correct	21 ms	51180 KB	Output is correct
3	Correct	27 ms	51232 KB	Output is correct
4	Correct	23 ms	51344 KB	Output is correct
5	Correct	25 ms	51404 KB	Output is correct
6	Correct	22 ms	51336 KB	Output is correct
7	Correct	25 ms	51432 KB	Output is correct
8	Correct	24 ms	51484 KB	Output is correct
9	Correct	81 ms	68488 KB	Output is correct
10	Correct	87 ms	72520 KB	Output is correct
11	Correct	91 ms	72176 KB	Output is correct
12	Correct	121 ms	73400 KB	Output is correct
13	Correct	87 ms	75800 KB	Output is correct
14	Correct	85 ms	68656 KB	Output is correct
15	Correct	222 ms	74468 KB	Output is correct
16	Correct	237 ms	73880 KB	Output is correct
17	Correct	224 ms	75316 KB	Output is correct
18	Correct	384 ms	77620 KB	Output is correct
19	Correct	101 ms	59684 KB	Output is correct
20	Correct	207 ms	79612 KB	Output is correct
21	Correct	226 ms	78900 KB	Output is correct
22	Correct	228 ms	80548 KB	Output is correct
23	Correct	430 ms	82756 KB	Output is correct

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	51156 KB	Output is correct
2	Correct	21 ms	51180 KB	Output is correct
3	Incorrect	479 ms	77988 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	51156 KB	Output is correct
2	Correct	21 ms	51180 KB	Output is correct
3	Correct	27 ms	51232 KB	Output is correct
4	Correct	23 ms	51344 KB	Output is correct
5	Correct	25 ms	51404 KB	Output is correct
6	Correct	22 ms	51336 KB	Output is correct
7	Correct	25 ms	51432 KB	Output is correct
8	Correct	24 ms	51484 KB	Output is correct
9	Correct	21 ms	51156 KB	Output is correct
10	Incorrect	21 ms	51428 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	51156 KB	Output is correct
2	Correct	20 ms	51156 KB	Output is correct
3	Correct	21 ms	51180 KB	Output is correct
4	Correct	27 ms	51232 KB	Output is correct
5	Correct	23 ms	51344 KB	Output is correct
6	Correct	25 ms	51404 KB	Output is correct
7	Correct	22 ms	51336 KB	Output is correct
8	Correct	25 ms	51432 KB	Output is correct
9	Correct	24 ms	51484 KB	Output is correct
10	Correct	81 ms	68488 KB	Output is correct
11	Correct	87 ms	72520 KB	Output is correct
12	Correct	91 ms	72176 KB	Output is correct
13	Correct	121 ms	73400 KB	Output is correct
14	Correct	87 ms	75800 KB	Output is correct
15	Incorrect	21 ms	51428 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #5
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	51156 KB	Output is correct
2	Correct	21 ms	51180 KB	Output is correct
3	Correct	27 ms	51232 KB	Output is correct
4	Correct	23 ms	51344 KB	Output is correct
5	Correct	25 ms	51404 KB	Output is correct
6	Correct	22 ms	51336 KB	Output is correct
7	Correct	25 ms	51432 KB	Output is correct
8	Correct	24 ms	51484 KB	Output is correct
9	Correct	81 ms	68488 KB	Output is correct
10	Correct	87 ms	72520 KB	Output is correct
11	Correct	91 ms	72176 KB	Output is correct
12	Correct	121 ms	73400 KB	Output is correct
13	Correct	87 ms	75800 KB	Output is correct
14	Correct	85 ms	68656 KB	Output is correct
15	Correct	222 ms	74468 KB	Output is correct
16	Correct	237 ms	73880 KB	Output is correct
17	Correct	224 ms	75316 KB	Output is correct
18	Correct	384 ms	77620 KB	Output is correct
19	Incorrect	479 ms	77988 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #6
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	51156 KB	Output is correct
2	Correct	20 ms	51156 KB	Output is correct
3	Correct	21 ms	51180 KB	Output is correct
4	Correct	27 ms	51232 KB	Output is correct
5	Correct	23 ms	51344 KB	Output is correct
6	Correct	25 ms	51404 KB	Output is correct
7	Correct	22 ms	51336 KB	Output is correct
8	Correct	25 ms	51432 KB	Output is correct
9	Correct	24 ms	51484 KB	Output is correct
10	Correct	81 ms	68488 KB	Output is correct
11	Correct	87 ms	72520 KB	Output is correct
12	Correct	91 ms	72176 KB	Output is correct
13	Correct	121 ms	73400 KB	Output is correct
14	Correct	87 ms	75800 KB	Output is correct
15	Correct	85 ms	68656 KB	Output is correct
16	Correct	222 ms	74468 KB	Output is correct
17	Correct	237 ms	73880 KB	Output is correct
18	Correct	224 ms	75316 KB	Output is correct
19	Correct	384 ms	77620 KB	Output is correct
20	Incorrect	479 ms	77988 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

답안 #679542

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 0 / 7.0

Subtask #3 0 / 17.0

Subtask #4 0 / 20.0

Subtask #5 0 / 23.0

Subtask #6 0 / 27.0

Subtask #1
6.0 / 6.0

Subtask #2
0 / 7.0

Subtask #3
0 / 17.0

Subtask #4
0 / 20.0

Subtask #5
0 / 23.0

Subtask #6
0 / 27.0