oj.uz

Submission #274119

# Submission time Handle Problem Language Result Execution time Memory
274119 2020-08-19T08:35:29 Z 송준혁(#5100) Mountains and Valleys (CCO20_day1problem3) C++17
1 / 25
 7000 ms 13056 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, M, K, ans;
int U[2020202], V[2020202], W[2020202];
int dep[2020202], P[505050][22];
vector<int> adj[505050];

void dfs(int u, int p){
	P[u][0] = p;
	for (int i=1; i<=20; i++) P[u][i] = P[P[u][i-1]][i-1];
	for (int v : adj[u]){
		if (v == p) continue;
		dep[v] = dep[u]+1;
		dfs(v, u);
	}
}

int LCA(int u, int v){
	if (dep[u] > dep[v]) swap(u, v);
	for (int i=20; i>=0; i--) if (dep[u] <= dep[v]-(1<<i)) v = P[v][i];
	if (u == v) return u;
	for (int i=20; i>=0; i--) if (P[u][i] != P[v][i]) u=P[u][i], v = P[v][i];
	return P[u][0];
}

int dis(int u, int v){return dep[u]+dep[v]-2*dep[LCA(u, v)];}

int kp(int u, int k){
	for (int i=0; i<=20; i++) if (k & (1<<i)) u = P[u][i];
	return u;
}

bool isa(int u, int a){return (dep[u]>=dep[a]) && kp(u, dep[u]-dep[a]) == a;}

bool cross(int u, int v, int a, int b){
	int x=LCA(u, v), y=LCA(a, b);
	if (dep[x] < dep[y]) swap(x, y), swap(u, a), swap(v, b);
	return isa(a, x) || isa(b, x);
}

int main(){
	scanf("%d %d", &N, &M);
	for (int i=1; i<=M; i++){
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		if (w == 1) adj[u].pb(v), adj[v].pb(u);
		else U[++K]=u, V[K]=v, W[K]=w;
	}
	dfs(0, 0);
	int d=0, x;
	for (int i=1; i<N; i++) if (d < dis(0, i)) x=i, d=dis(0, i);
	for (int i=0; i<N; i++) if (i != x) d = max(d, dis(x, i));
	ans = 2*N-d-2;
	for (int i=1; i<=K; i++){
		for (int s=1; s<=N; s++) for (int e=1; e<=N; e++){
			if (!cross(s, U[i], V[i], e)) ans = min(ans, 2*N-4-dis(s, U[i])-dis(V[i], e)+W[i]);
		}
		for (int j=1; j<=K; j++){
			if (i == j) continue;
			for (int s=1; s<=N; s++){
				if (cross(s, U[i], V[i], U[j])) continue;
				for (int e=1; e<=N; e++){
					if (!cross(s, U[i], V[j], e) && !cross(V[i], U[j], V[j], e)){
						ans = min(ans, 2*N-6-dis(s, U[i])-dis(V[i], U[j])-dis(V[j], e)+W[i]+W[j]);
					}
				}
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |  scanf("%d %d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |   scanf("%d %d %d", &u, &v, &w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:32:35: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   32 | int dis(int u, int v){return dep[u]+dep[v]-2*dep[LCA(u, v)];}
      |                              ~~~~~^
Main.cpp:56:11: note: 'x' was declared here
   56 |  int d=0, x;
      |           ^

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 11 ms 12160 KB Output is correct
4 Correct 9 ms 12160 KB Output is correct
5 Correct 12 ms 12160 KB Output is correct
6 Correct 8 ms 12160 KB Output is correct
7 Correct 10 ms 12160 KB Output is correct
8 Correct 8 ms 12160 KB Output is correct
9 Correct 10 ms 12160 KB Output is correct
10 Correct 8 ms 12160 KB Output is correct
11 Correct 10 ms 12160 KB Output is correct
12 Correct 10 ms 12160 KB Output is correct
13 Correct 8 ms 12160 KB Output is correct
14 Correct 10 ms 12160 KB Output is correct
15 Correct 8 ms 12160 KB Output is correct

Subtask #2
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 11 ms 12160 KB Output is correct
4 Correct 9 ms 12160 KB Output is correct
5 Correct 12 ms 12160 KB Output is correct
6 Correct 8 ms 12160 KB Output is correct
7 Correct 10 ms 12160 KB Output is correct
8 Correct 8 ms 12160 KB Output is correct
9 Correct 10 ms 12160 KB Output is correct
10 Correct 8 ms 12160 KB Output is correct
11 Correct 10 ms 12160 KB Output is correct
12 Correct 10 ms 12160 KB Output is correct
13 Correct 8 ms 12160 KB Output is correct
14 Correct 10 ms 12160 KB Output is correct
15 Correct 8 ms 12160 KB Output is correct
16 Correct 8 ms 12160 KB Output is correct
17 Correct 10 ms 12160 KB Output is correct
18 Incorrect 10 ms 12160 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7061 ms 13056 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 11 ms 12160 KB Output is correct
4 Correct 9 ms 12160 KB Output is correct
5 Correct 12 ms 12160 KB Output is correct
6 Correct 8 ms 12160 KB Output is correct
7 Correct 10 ms 12160 KB Output is correct
8 Correct 8 ms 12160 KB Output is correct
9 Correct 10 ms 12160 KB Output is correct
10 Correct 8 ms 12160 KB Output is correct
11 Correct 10 ms 12160 KB Output is correct
12 Correct 10 ms 12160 KB Output is correct
13 Correct 8 ms 12160 KB Output is correct
14 Correct 10 ms 12160 KB Output is correct
15 Correct 8 ms 12160 KB Output is correct
16 Correct 8 ms 12160 KB Output is correct
17 Correct 10 ms 12160 KB Output is correct
18 Incorrect 10 ms 12160 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 11 ms 12160 KB Output is correct
4 Correct 9 ms 12160 KB Output is correct
5 Correct 12 ms 12160 KB Output is correct
6 Correct 8 ms 12160 KB Output is correct
7 Correct 10 ms 12160 KB Output is correct
8 Correct 8 ms 12160 KB Output is correct
9 Correct 10 ms 12160 KB Output is correct
10 Correct 8 ms 12160 KB Output is correct
11 Correct 10 ms 12160 KB Output is correct
12 Correct 10 ms 12160 KB Output is correct
13 Correct 8 ms 12160 KB Output is correct
14 Correct 10 ms 12160 KB Output is correct
15 Correct 8 ms 12160 KB Output is correct
16 Correct 8 ms 12160 KB Output is correct
17 Correct 10 ms 12160 KB Output is correct
18 Incorrect 10 ms 12160 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #6
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 11 ms 12160 KB Output is correct
4 Correct 9 ms 12160 KB Output is correct
5 Correct 12 ms 12160 KB Output is correct
6 Correct 8 ms 12160 KB Output is correct
7 Correct 10 ms 12160 KB Output is correct
8 Correct 8 ms 12160 KB Output is correct
9 Correct 10 ms 12160 KB Output is correct
10 Correct 8 ms 12160 KB Output is correct
11 Correct 10 ms 12160 KB Output is correct
12 Correct 10 ms 12160 KB Output is correct
13 Correct 8 ms 12160 KB Output is correct
14 Correct 10 ms 12160 KB Output is correct
15 Correct 8 ms 12160 KB Output is correct
16 Correct 8 ms 12160 KB Output is correct
17 Correct 10 ms 12160 KB Output is correct
18 Incorrect 10 ms 12160 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #7
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 11 ms 12160 KB Output is correct
4 Correct 9 ms 12160 KB Output is correct
5 Correct 12 ms 12160 KB Output is correct
6 Correct 8 ms 12160 KB Output is correct
7 Correct 10 ms 12160 KB Output is correct
8 Correct 8 ms 12160 KB Output is correct
9 Correct 10 ms 12160 KB Output is correct
10 Correct 8 ms 12160 KB Output is correct
11 Correct 10 ms 12160 KB Output is correct
12 Correct 10 ms 12160 KB Output is correct
13 Correct 8 ms 12160 KB Output is correct
14 Correct 10 ms 12160 KB Output is correct
15 Correct 8 ms 12160 KB Output is correct
16 Correct 8 ms 12160 KB Output is correct
17 Correct 10 ms 12160 KB Output is correct
18 Incorrect 10 ms 12160 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 11 ms 12160 KB Output is correct
4 Correct 9 ms 12160 KB Output is correct
5 Correct 12 ms 12160 KB Output is correct
6 Correct 8 ms 12160 KB Output is correct
7 Correct 10 ms 12160 KB Output is correct
8 Correct 8 ms 12160 KB Output is correct
9 Correct 10 ms 12160 KB Output is correct
10 Correct 8 ms 12160 KB Output is correct
11 Correct 10 ms 12160 KB Output is correct
12 Correct 10 ms 12160 KB Output is correct
13 Correct 8 ms 12160 KB Output is correct
14 Correct 10 ms 12160 KB Output is correct
15 Correct 8 ms 12160 KB Output is correct
16 Correct 8 ms 12160 KB Output is correct
17 Correct 10 ms 12160 KB Output is correct
18 Incorrect 10 ms 12160 KB Output isn't correct
19 Halted 0 ms 0 KB -