oj.uz

Submission #594877

# Submission time Handle Problem Language Result Execution time Memory
594877 2022-07-13T05:54:01 Z penguinhacker Swapping Cities (APIO20_swap) C++17
0 / 100
 77 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], ans[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;
		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];
			adj[n2].push_back(u);
			adj[n2].push_back(v);
			ans[n2]=max(e[i][0], first[n2]);
			++n2;
		} else if (first[u]==-1) {
			first[u]=e[i][0];
			ans[u]=max(ans[u], first[u]);
		}
	}
	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;
	assert(n2==2*n-1);
	dfs(n2-1);
}

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) {
	//cout << "CALLED FUNCTION " << u << " " << v << endl;
	return -1;
	int uv=lca(u, v);
	return first[uv]^-1?ans[uv]:-1;
}

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:35:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   35 |    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 10 ms 17492 KB Output is correct
2 Correct 8 ms 17492 KB Output is correct
3 Correct 7 ms 17492 KB Output is correct
4 Correct 7 ms 17492 KB Output is correct
5 Correct 10 ms 17620 KB Output is correct
6 Correct 9 ms 17572 KB Output is correct
7 Correct 8 ms 17552 KB Output is correct
8 Correct 8 ms 17620 KB Output is correct
9 Runtime error 43 ms 11508 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 10 ms 17492 KB Output is correct
2 Correct 8 ms 17492 KB Output is correct
3 Runtime error 77 ms 15752 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 10 ms 17492 KB Output is correct
2 Correct 8 ms 17492 KB Output is correct
3 Correct 7 ms 17492 KB Output is correct
4 Correct 7 ms 17492 KB Output is correct
5 Correct 10 ms 17620 KB Output is correct
6 Correct 9 ms 17572 KB Output is correct
7 Correct 8 ms 17552 KB Output is correct
8 Correct 8 ms 17620 KB Output is correct
9 Incorrect 8 ms 17508 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 17508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 17508 KB Output isn't correct
2 Halted 0 ms 0 KB -