oj.uz

Submission #594898

# Submission time Handle Problem Language Result Execution time Memory
594898 2022-07-13T06:33:37 Z penguinhacker Swapping Cities (APIO20_swap) C++17
6 / 100
 321 ms 39988 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], epa[2*mxN], epb[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<n; ++i)
		epa[i]=epb[i]=i;
	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];
			if (first[n2]==-1) {
				if (epa[u]!=e[i][1]&&epb[u]!=e[i][1]&&epa[v]!=e[i][2]&&epb[v]!=e[i][2])
					first[n2]=e[i][0];
				else {
					epa[n2]=epa[u]^epb[u]^e[i][1];
					epb[n2]=epa[v]^epb[v]^e[i][2];
				}
			}
			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:39:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   39 |    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 10 ms 19796 KB Output is correct
2 Correct 11 ms 19796 KB Output is correct
3 Correct 10 ms 19796 KB Output is correct
4 Correct 9 ms 19924 KB Output is correct
5 Correct 10 ms 20024 KB Output is correct
6 Correct 9 ms 19924 KB Output is correct
7 Correct 10 ms 19924 KB Output is correct
8 Correct 9 ms 20044 KB Output is correct
9 Correct 83 ms 28400 KB Output is correct
10 Correct 105 ms 31588 KB Output is correct
11 Correct 107 ms 31440 KB Output is correct
12 Correct 117 ms 32176 KB Output is correct
13 Correct 97 ms 34452 KB Output is correct
14 Correct 88 ms 29856 KB Output is correct
15 Correct 226 ms 35784 KB Output is correct
16 Correct 198 ms 35612 KB Output is correct
17 Correct 203 ms 36132 KB Output is correct
18 Correct 321 ms 38616 KB Output is correct
19 Correct 84 ms 26956 KB Output is correct
20 Correct 215 ms 36900 KB Output is correct
21 Correct 218 ms 36860 KB Output is correct
22 Correct 211 ms 37552 KB Output is correct
23 Correct 286 ms 39988 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19796 KB Output is correct
2 Correct 11 ms 19796 KB Output is correct
3 Incorrect 243 ms 36048 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19796 KB Output is correct
2 Correct 11 ms 19796 KB Output is correct
3 Correct 10 ms 19796 KB Output is correct
4 Correct 9 ms 19924 KB Output is correct
5 Correct 10 ms 20024 KB Output is correct
6 Correct 9 ms 19924 KB Output is correct
7 Correct 10 ms 19924 KB Output is correct
8 Correct 9 ms 20044 KB Output is correct
9 Correct 8 ms 19796 KB Output is correct
10 Correct 11 ms 19924 KB Output is correct
11 Incorrect 9 ms 19924 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19796 KB Output is correct
2 Correct 10 ms 19796 KB Output is correct
3 Correct 11 ms 19796 KB Output is correct
4 Correct 10 ms 19796 KB Output is correct
5 Correct 9 ms 19924 KB Output is correct
6 Correct 10 ms 20024 KB Output is correct
7 Correct 9 ms 19924 KB Output is correct
8 Correct 10 ms 19924 KB Output is correct
9 Correct 9 ms 20044 KB Output is correct
10 Correct 83 ms 28400 KB Output is correct
11 Correct 105 ms 31588 KB Output is correct
12 Correct 107 ms 31440 KB Output is correct
13 Correct 117 ms 32176 KB Output is correct
14 Correct 97 ms 34452 KB Output is correct
15 Correct 11 ms 19924 KB Output is correct
16 Incorrect 9 ms 19924 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19796 KB Output is correct
2 Correct 11 ms 19796 KB Output is correct
3 Correct 10 ms 19796 KB Output is correct
4 Correct 9 ms 19924 KB Output is correct
5 Correct 10 ms 20024 KB Output is correct
6 Correct 9 ms 19924 KB Output is correct
7 Correct 10 ms 19924 KB Output is correct
8 Correct 9 ms 20044 KB Output is correct
9 Correct 83 ms 28400 KB Output is correct
10 Correct 105 ms 31588 KB Output is correct
11 Correct 107 ms 31440 KB Output is correct
12 Correct 117 ms 32176 KB Output is correct
13 Correct 97 ms 34452 KB Output is correct
14 Correct 88 ms 29856 KB Output is correct
15 Correct 226 ms 35784 KB Output is correct
16 Correct 198 ms 35612 KB Output is correct
17 Correct 203 ms 36132 KB Output is correct
18 Correct 321 ms 38616 KB Output is correct
19 Incorrect 243 ms 36048 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19796 KB Output is correct
2 Correct 10 ms 19796 KB Output is correct
3 Correct 11 ms 19796 KB Output is correct
4 Correct 10 ms 19796 KB Output is correct
5 Correct 9 ms 19924 KB Output is correct
6 Correct 10 ms 20024 KB Output is correct
7 Correct 9 ms 19924 KB Output is correct
8 Correct 10 ms 19924 KB Output is correct
9 Correct 9 ms 20044 KB Output is correct
10 Correct 83 ms 28400 KB Output is correct
11 Correct 105 ms 31588 KB Output is correct
12 Correct 107 ms 31440 KB Output is correct
13 Correct 117 ms 32176 KB Output is correct
14 Correct 97 ms 34452 KB Output is correct
15 Correct 88 ms 29856 KB Output is correct
16 Correct 226 ms 35784 KB Output is correct
17 Correct 198 ms 35612 KB Output is correct
18 Correct 203 ms 36132 KB Output is correct
19 Correct 321 ms 38616 KB Output is correct
20 Incorrect 243 ms 36048 KB Output isn't correct
21 Halted 0 ms 0 KB -