oj.uz

답안 #594888

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
594888 2022-07-13T06:18:30 Z penguinhacker 자매 도시 (APIO20_swap) C++17
6 / 100
 279 ms 38392 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

#define ar array

const int mxN=1e5, mxM=2e5;
int n, m, p[2*mxN], anc[2*mxN][18], first[2*mxN], n2, d[2*mxN], ew[2*mxN];
ar<int, 3> e[mxM];
vector<int> adj[2*mxN];

int find(int i) {
	return i^p[i]?p[i]=find(p[i]):i;
}

void dfs(int u) {
	for (int v : adj[u]) {
		d[v]=d[u]+1;
		if (ew[u]!=-1&&(ew[v]==-1||ew[u]<ew[v]))
			ew[v]=ew[u];
		dfs(v);
	}
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n=N, m=M, n2=n;
	for (int i=0; i<m; ++i)
		e[i]={W[i], U[i], V[i]};
	sort(e, e+m);
	iota(p, p+2*n, 0);
	memset(anc, -1, sizeof(anc));
	memset(first, -1, sizeof(first));
	for (int i=0; i<m; ++i) {
		int u=find(e[i][1]), v=find(e[i][2]);
		if (u!=v) {
			p[u]=p[v]=anc[u][0]=anc[v][0]=n2;
			first[n2]=first[v]==-1||first[u]!=-1&&first[u]<first[v]?first[u]:first[v];
			ew[n2]=e[i][0];
			adj[n2].push_back(u);
			adj[n2].push_back(v);
			++n2;
		} else if (first[u]==-1)
			first[u]=e[i][0];
	}
	assert(n2==2*n-1);
	for (int j=1; j<18; ++j)
		for (int i=0; i<n2; ++i)
			anc[i][j]=anc[i][j-1]^-1?anc[anc[i][j-1]][j-1]:-1;
	for (int i=n; i<n2; ++i) {
		ew[i]=first[i]^-1?max(ew[i], first[i]):-1;
		//cout << i << " " << ew[i] << endl;
	}
	dfs(n2-1);
	//for (int i=n; i<n2; ++i)
	//	cout << i << " " << ew[i] << endl;
}

int lca(int u, int v) {
	if (d[u]>d[v])
		swap(u, v);
	for (int i=17; ~i; --i)
		if (d[v]-(1<<i)>=d[u])
			v=anc[v][i];
	if (u==v)
		return u;
	for (int i=17; ~i; --i)
		if (anc[u][i]!=anc[v][i])
			u=anc[u][i], v=anc[v][i];
	return anc[u][0];
}

int getMinimumFuelCapacity(int u, int v) {
	return ew[lca(u, v)];
}

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:37:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   37 |    first[n2]=first[v]==-1||first[u]!=-1&&first[u]<first[v]?first[u]:first[v];
      |                            ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 19796 KB Output is correct
2 Correct 9 ms 19796 KB Output is correct
3 Correct 9 ms 19796 KB Output is correct
4 Correct 9 ms 19924 KB Output is correct
5 Correct 10 ms 19948 KB Output is correct
6 Correct 9 ms 19924 KB Output is correct
7 Correct 9 ms 19920 KB Output is correct
8 Correct 11 ms 19992 KB Output is correct
9 Correct 81 ms 26548 KB Output is correct
10 Correct 112 ms 30080 KB Output is correct
11 Correct 101 ms 29900 KB Output is correct
12 Correct 108 ms 30484 KB Output is correct
13 Correct 103 ms 32960 KB Output is correct
14 Correct 101 ms 28652 KB Output is correct
15 Correct 229 ms 34324 KB Output is correct
16 Correct 216 ms 34056 KB Output is correct
17 Correct 261 ms 34680 KB Output is correct
18 Correct 266 ms 36956 KB Output is correct
19 Correct 85 ms 26780 KB Output is correct
20 Correct 228 ms 35308 KB Output is correct
21 Correct 192 ms 35440 KB Output is correct
22 Correct 212 ms 36028 KB Output is correct
23 Correct 279 ms 38392 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 19796 KB Output is correct
2 Correct 9 ms 19796 KB Output is correct
3 Incorrect 259 ms 34212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 19796 KB Output is correct
2 Correct 9 ms 19796 KB Output is correct
3 Correct 9 ms 19796 KB Output is correct
4 Correct 9 ms 19924 KB Output is correct
5 Correct 10 ms 19948 KB Output is correct
6 Correct 9 ms 19924 KB Output is correct
7 Correct 9 ms 19920 KB Output is correct
8 Correct 11 ms 19992 KB Output is correct
9 Correct 9 ms 19808 KB Output is correct
10 Incorrect 10 ms 19896 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 19808 KB Output is correct
2 Correct 8 ms 19796 KB Output is correct
3 Correct 9 ms 19796 KB Output is correct
4 Correct 9 ms 19796 KB Output is correct
5 Correct 9 ms 19924 KB Output is correct
6 Correct 10 ms 19948 KB Output is correct
7 Correct 9 ms 19924 KB Output is correct
8 Correct 9 ms 19920 KB Output is correct
9 Correct 11 ms 19992 KB Output is correct
10 Correct 81 ms 26548 KB Output is correct
11 Correct 112 ms 30080 KB Output is correct
12 Correct 101 ms 29900 KB Output is correct
13 Correct 108 ms 30484 KB Output is correct
14 Correct 103 ms 32960 KB Output is correct
15 Incorrect 10 ms 19896 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 19796 KB Output is correct
2 Correct 9 ms 19796 KB Output is correct
3 Correct 9 ms 19796 KB Output is correct
4 Correct 9 ms 19924 KB Output is correct
5 Correct 10 ms 19948 KB Output is correct
6 Correct 9 ms 19924 KB Output is correct
7 Correct 9 ms 19920 KB Output is correct
8 Correct 11 ms 19992 KB Output is correct
9 Correct 81 ms 26548 KB Output is correct
10 Correct 112 ms 30080 KB Output is correct
11 Correct 101 ms 29900 KB Output is correct
12 Correct 108 ms 30484 KB Output is correct
13 Correct 103 ms 32960 KB Output is correct
14 Correct 101 ms 28652 KB Output is correct
15 Correct 229 ms 34324 KB Output is correct
16 Correct 216 ms 34056 KB Output is correct
17 Correct 261 ms 34680 KB Output is correct
18 Correct 266 ms 36956 KB Output is correct
19 Incorrect 259 ms 34212 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 19808 KB Output is correct
2 Correct 8 ms 19796 KB Output is correct
3 Correct 9 ms 19796 KB Output is correct
4 Correct 9 ms 19796 KB Output is correct
5 Correct 9 ms 19924 KB Output is correct
6 Correct 10 ms 19948 KB Output is correct
7 Correct 9 ms 19924 KB Output is correct
8 Correct 9 ms 19920 KB Output is correct
9 Correct 11 ms 19992 KB Output is correct
10 Correct 81 ms 26548 KB Output is correct
11 Correct 112 ms 30080 KB Output is correct
12 Correct 101 ms 29900 KB Output is correct
13 Correct 108 ms 30484 KB Output is correct
14 Correct 103 ms 32960 KB Output is correct
15 Correct 101 ms 28652 KB Output is correct
16 Correct 229 ms 34324 KB Output is correct
17 Correct 216 ms 34056 KB Output is correct
18 Correct 261 ms 34680 KB Output is correct
19 Correct 266 ms 36956 KB Output is correct
20 Incorrect 259 ms 34212 KB Output isn't correct
21 Halted 0 ms 0 KB -