oj.uz

Submission #594887

# Submission time Handle Problem Language Result Execution time Memory
594887 2022-07-13T06:17:22 Z penguinhacker Swapping Cities (APIO20_swap) C++17
0 / 100
 80 ms 17620 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

#define ar array

const int mxN=1e5, mxM=2e5;
int n, m, p[mxN], anc[2*mxN][18], first[2*mxN], n2, d[2*mxN], ew[2*mxN];
ar<int, 3> e[mxM];
vector<int> adj[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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17492 KB Output is correct
2 Correct 7 ms 17492 KB Output is correct
3 Correct 9 ms 17492 KB Output is correct
4 Correct 7 ms 17464 KB Output is correct
5 Correct 8 ms 17620 KB Output is correct
6 Correct 8 ms 17504 KB Output is correct
7 Correct 8 ms 17620 KB Output is correct
8 Correct 9 ms 17552 KB Output is correct
9 Runtime error 50 ms 11556 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17492 KB Output is correct
2 Correct 7 ms 17492 KB Output is correct
3 Runtime error 80 ms 15684 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17492 KB Output is correct
2 Correct 7 ms 17492 KB Output is correct
3 Correct 9 ms 17492 KB Output is correct
4 Correct 7 ms 17464 KB Output is correct
5 Correct 8 ms 17620 KB Output is correct
6 Correct 8 ms 17504 KB Output is correct
7 Correct 8 ms 17620 KB Output is correct
8 Correct 9 ms 17552 KB Output is correct
9 Correct 9 ms 17492 KB Output is correct
10 Incorrect 7 ms 17620 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 17492 KB Output is correct
2 Correct 7 ms 17492 KB Output is correct
3 Correct 7 ms 17492 KB Output is correct
4 Correct 9 ms 17492 KB Output is correct
5 Correct 7 ms 17464 KB Output is correct
6 Correct 8 ms 17620 KB Output is correct
7 Correct 8 ms 17504 KB Output is correct
8 Correct 8 ms 17620 KB Output is correct
9 Correct 9 ms 17552 KB Output is correct
10 Runtime error 50 ms 11556 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17492 KB Output is correct
2 Correct 7 ms 17492 KB Output is correct
3 Correct 9 ms 17492 KB Output is correct
4 Correct 7 ms 17464 KB Output is correct
5 Correct 8 ms 17620 KB Output is correct
6 Correct 8 ms 17504 KB Output is correct
7 Correct 8 ms 17620 KB Output is correct
8 Correct 9 ms 17552 KB Output is correct
9 Runtime error 50 ms 11556 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17492 KB Output is correct
2 Correct 7 ms 17492 KB Output is correct
3 Correct 7 ms 17492 KB Output is correct
4 Correct 9 ms 17492 KB Output is correct
5 Correct 7 ms 17464 KB Output is correct
6 Correct 8 ms 17620 KB Output is correct
7 Correct 8 ms 17504 KB Output is correct
8 Correct 8 ms 17620 KB Output is correct
9 Correct 9 ms 17552 KB Output is correct
10 Runtime error 50 ms 11556 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -