oj.uz

답안 #594881

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
594881 2022-07-13T06:06:24 Z penguinhacker 자매 도시 (APIO20_swap) C++17
0 / 100
 80 ms 17648 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 (first[v]==-1||first[u]!=-1&&first[u]<first[v])
			first[v]=first[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];
	}
	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) {
	int uv=lca(u, v);
	return first[uv]^-1?max(ew[uv], first[uv]):-1;
}

Compilation message

swap.cpp: In function 'void dfs(int)':
swap.cpp:19:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   19 |   if (first[v]==-1||first[u]!=-1&&first[u]<first[v])
      |                     ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 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 7 ms 17492 KB Output is correct
5 Correct 10 ms 17520 KB Output is correct
6 Correct 9 ms 17492 KB Output is correct
7 Correct 8 ms 17620 KB Output is correct
8 Correct 8 ms 17648 KB Output is correct
9 Runtime error 36 ms 11508 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 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 15708 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 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 7 ms 17492 KB Output is correct
5 Correct 10 ms 17520 KB Output is correct
6 Correct 9 ms 17492 KB Output is correct
7 Correct 8 ms 17620 KB Output is correct
8 Correct 8 ms 17648 KB Output is correct
9 Correct 9 ms 17492 KB Output is correct
10 Incorrect 8 ms 17612 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 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 7 ms 17492 KB Output is correct
5 Correct 7 ms 17492 KB Output is correct
6 Correct 10 ms 17520 KB Output is correct
7 Correct 9 ms 17492 KB Output is correct
8 Correct 8 ms 17620 KB Output is correct
9 Correct 8 ms 17648 KB Output is correct
10 Runtime error 36 ms 11508 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 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 7 ms 17492 KB Output is correct
5 Correct 10 ms 17520 KB Output is correct
6 Correct 9 ms 17492 KB Output is correct
7 Correct 8 ms 17620 KB Output is correct
8 Correct 8 ms 17648 KB Output is correct
9 Runtime error 36 ms 11508 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 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 7 ms 17492 KB Output is correct
5 Correct 7 ms 17492 KB Output is correct
6 Correct 10 ms 17520 KB Output is correct
7 Correct 9 ms 17492 KB Output is correct
8 Correct 8 ms 17620 KB Output is correct
9 Correct 8 ms 17648 KB Output is correct
10 Runtime error 36 ms 11508 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -