oj.uz

Submission #594888

# Submission time Handle Problem Language Result Execution time Memory
594888 2022-07-13T06:18:30 Z penguinhacker Swapping Cities (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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -