답안 #679546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
679546	2023-01-08T13:17:20 Z	Dan4Life	자매 도시 (APIO20_swap)	C++17	6 / 100	478 ms	129524 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[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][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	40 ms	102028 KB	Output is correct
2	Correct	39 ms	102092 KB	Output is correct
3	Correct	45 ms	102012 KB	Output is correct
4	Correct	41 ms	102220 KB	Output is correct
5	Correct	46 ms	102220 KB	Output is correct
6	Correct	45 ms	102228 KB	Output is correct
7	Correct	40 ms	102312 KB	Output is correct
8	Correct	46 ms	102356 KB	Output is correct
9	Correct	91 ms	119048 KB	Output is correct
10	Correct	114 ms	123076 KB	Output is correct
11	Correct	112 ms	122828 KB	Output is correct
12	Correct	116 ms	123908 KB	Output is correct
13	Correct	105 ms	126280 KB	Output is correct
14	Correct	105 ms	119160 KB	Output is correct
15	Correct	230 ms	125036 KB	Output is correct
16	Correct	238 ms	124404 KB	Output is correct
17	Correct	249 ms	125716 KB	Output is correct
18	Correct	421 ms	128056 KB	Output is correct
19	Correct	124 ms	108704 KB	Output is correct
20	Correct	226 ms	126312 KB	Output is correct
21	Correct	219 ms	125700 KB	Output is correct
22	Correct	246 ms	127116 KB	Output is correct
23	Correct	414 ms	129524 KB	Output is correct

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	40 ms	102028 KB	Output is correct
2	Correct	39 ms	102092 KB	Output is correct
3	Incorrect	478 ms	128504 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	40 ms	102028 KB	Output is correct
2	Correct	39 ms	102092 KB	Output is correct
3	Correct	45 ms	102012 KB	Output is correct
4	Correct	41 ms	102220 KB	Output is correct
5	Correct	46 ms	102220 KB	Output is correct
6	Correct	45 ms	102228 KB	Output is correct
7	Correct	40 ms	102312 KB	Output is correct
8	Correct	46 ms	102356 KB	Output is correct
9	Correct	49 ms	102124 KB	Output is correct
10	Incorrect	45 ms	102280 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	49 ms	102124 KB	Output is correct
2	Correct	40 ms	102028 KB	Output is correct
3	Correct	39 ms	102092 KB	Output is correct
4	Correct	45 ms	102012 KB	Output is correct
5	Correct	41 ms	102220 KB	Output is correct
6	Correct	46 ms	102220 KB	Output is correct
7	Correct	45 ms	102228 KB	Output is correct
8	Correct	40 ms	102312 KB	Output is correct
9	Correct	46 ms	102356 KB	Output is correct
10	Correct	91 ms	119048 KB	Output is correct
11	Correct	114 ms	123076 KB	Output is correct
12	Correct	112 ms	122828 KB	Output is correct
13	Correct	116 ms	123908 KB	Output is correct
14	Correct	105 ms	126280 KB	Output is correct
15	Incorrect	45 ms	102280 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #5
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	40 ms	102028 KB	Output is correct
2	Correct	39 ms	102092 KB	Output is correct
3	Correct	45 ms	102012 KB	Output is correct
4	Correct	41 ms	102220 KB	Output is correct
5	Correct	46 ms	102220 KB	Output is correct
6	Correct	45 ms	102228 KB	Output is correct
7	Correct	40 ms	102312 KB	Output is correct
8	Correct	46 ms	102356 KB	Output is correct
9	Correct	91 ms	119048 KB	Output is correct
10	Correct	114 ms	123076 KB	Output is correct
11	Correct	112 ms	122828 KB	Output is correct
12	Correct	116 ms	123908 KB	Output is correct
13	Correct	105 ms	126280 KB	Output is correct
14	Correct	105 ms	119160 KB	Output is correct
15	Correct	230 ms	125036 KB	Output is correct
16	Correct	238 ms	124404 KB	Output is correct
17	Correct	249 ms	125716 KB	Output is correct
18	Correct	421 ms	128056 KB	Output is correct
19	Incorrect	478 ms	128504 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #6
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	49 ms	102124 KB	Output is correct
2	Correct	40 ms	102028 KB	Output is correct
3	Correct	39 ms	102092 KB	Output is correct
4	Correct	45 ms	102012 KB	Output is correct
5	Correct	41 ms	102220 KB	Output is correct
6	Correct	46 ms	102220 KB	Output is correct
7	Correct	45 ms	102228 KB	Output is correct
8	Correct	40 ms	102312 KB	Output is correct
9	Correct	46 ms	102356 KB	Output is correct
10	Correct	91 ms	119048 KB	Output is correct
11	Correct	114 ms	123076 KB	Output is correct
12	Correct	112 ms	122828 KB	Output is correct
13	Correct	116 ms	123908 KB	Output is correct
14	Correct	105 ms	126280 KB	Output is correct
15	Correct	105 ms	119160 KB	Output is correct
16	Correct	230 ms	125036 KB	Output is correct
17	Correct	238 ms	124404 KB	Output is correct
18	Correct	249 ms	125716 KB	Output is correct
19	Correct	421 ms	128056 KB	Output is correct
20	Incorrect	478 ms	128504 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

답안 #679546

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