답안 #679547

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

swap

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

const int maxn = (int)1e6+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[i]++, deg[j]++;
	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[i]>=3)|(deg[j]>=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][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	41 ms	102052 KB	Output is correct
2	Correct	41 ms	102068 KB	Output is correct
3	Correct	41 ms	102032 KB	Output is correct
4	Correct	43 ms	102192 KB	Output is correct
5	Correct	44 ms	102212 KB	Output is correct
6	Correct	47 ms	102228 KB	Output is correct
7	Correct	47 ms	102340 KB	Output is correct
8	Correct	41 ms	102300 KB	Output is correct
9	Correct	95 ms	119052 KB	Output is correct
10	Correct	111 ms	122984 KB	Output is correct
11	Correct	108 ms	122672 KB	Output is correct
12	Correct	111 ms	123960 KB	Output is correct
13	Correct	99 ms	126352 KB	Output is correct
14	Correct	100 ms	119172 KB	Output is correct
15	Correct	214 ms	125056 KB	Output is correct
16	Correct	225 ms	124436 KB	Output is correct
17	Correct	220 ms	125748 KB	Output is correct
18	Correct	408 ms	128052 KB	Output is correct
19	Correct	114 ms	108748 KB	Output is correct
20	Correct	213 ms	126316 KB	Output is correct
21	Correct	223 ms	125664 KB	Output is correct
22	Correct	236 ms	127084 KB	Output is correct
23	Correct	418 ms	129456 KB	Output is correct

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	102052 KB	Output is correct
2	Correct	41 ms	102068 KB	Output is correct
3	Incorrect	515 ms	129868 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	102052 KB	Output is correct
2	Correct	41 ms	102068 KB	Output is correct
3	Correct	41 ms	102032 KB	Output is correct
4	Correct	43 ms	102192 KB	Output is correct
5	Correct	44 ms	102212 KB	Output is correct
6	Correct	47 ms	102228 KB	Output is correct
7	Correct	47 ms	102340 KB	Output is correct
8	Correct	41 ms	102300 KB	Output is correct
9	Correct	44 ms	102092 KB	Output is correct
10	Incorrect	43 ms	102244 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	44 ms	102092 KB	Output is correct
2	Correct	41 ms	102052 KB	Output is correct
3	Correct	41 ms	102068 KB	Output is correct
4	Correct	41 ms	102032 KB	Output is correct
5	Correct	43 ms	102192 KB	Output is correct
6	Correct	44 ms	102212 KB	Output is correct
7	Correct	47 ms	102228 KB	Output is correct
8	Correct	47 ms	102340 KB	Output is correct
9	Correct	41 ms	102300 KB	Output is correct
10	Correct	95 ms	119052 KB	Output is correct
11	Correct	111 ms	122984 KB	Output is correct
12	Correct	108 ms	122672 KB	Output is correct
13	Correct	111 ms	123960 KB	Output is correct
14	Correct	99 ms	126352 KB	Output is correct
15	Incorrect	43 ms	102244 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #5
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	102052 KB	Output is correct
2	Correct	41 ms	102068 KB	Output is correct
3	Correct	41 ms	102032 KB	Output is correct
4	Correct	43 ms	102192 KB	Output is correct
5	Correct	44 ms	102212 KB	Output is correct
6	Correct	47 ms	102228 KB	Output is correct
7	Correct	47 ms	102340 KB	Output is correct
8	Correct	41 ms	102300 KB	Output is correct
9	Correct	95 ms	119052 KB	Output is correct
10	Correct	111 ms	122984 KB	Output is correct
11	Correct	108 ms	122672 KB	Output is correct
12	Correct	111 ms	123960 KB	Output is correct
13	Correct	99 ms	126352 KB	Output is correct
14	Correct	100 ms	119172 KB	Output is correct
15	Correct	214 ms	125056 KB	Output is correct
16	Correct	225 ms	124436 KB	Output is correct
17	Correct	220 ms	125748 KB	Output is correct
18	Correct	408 ms	128052 KB	Output is correct
19	Incorrect	515 ms	129868 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #6
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	44 ms	102092 KB	Output is correct
2	Correct	41 ms	102052 KB	Output is correct
3	Correct	41 ms	102068 KB	Output is correct
4	Correct	41 ms	102032 KB	Output is correct
5	Correct	43 ms	102192 KB	Output is correct
6	Correct	44 ms	102212 KB	Output is correct
7	Correct	47 ms	102228 KB	Output is correct
8	Correct	47 ms	102340 KB	Output is correct
9	Correct	41 ms	102300 KB	Output is correct
10	Correct	95 ms	119052 KB	Output is correct
11	Correct	111 ms	122984 KB	Output is correct
12	Correct	108 ms	122672 KB	Output is correct
13	Correct	111 ms	123960 KB	Output is correct
14	Correct	99 ms	126352 KB	Output is correct
15	Correct	100 ms	119172 KB	Output is correct
16	Correct	214 ms	125056 KB	Output is correct
17	Correct	225 ms	124436 KB	Output is correct
18	Correct	220 ms	125748 KB	Output is correct
19	Correct	408 ms	128052 KB	Output is correct
20	Incorrect	515 ms	129868 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

답안 #679547

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