oj.uz

Submission #547667

# Submission time Handle Problem Language Result Execution time Memory
547667 2022-04-11T09:53:48 Z amunduzbaev Mountains and Valleys (CCO20_day1problem3) C++17
3 / 25
 1533 ms 13092 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
const int N = 5e5 + 5;
vector<int> edges[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	vector<ar<int, 3>> e;
	int cnt = 0;
	for(int i=0;i<m;i++){
		int a, b, c; cin>>a>>b>>c; a++, b++;
		if(c == 1){
			edges[a].push_back(b);
			edges[b].push_back(a);
			cnt++;
		} else {
			e.push_back({a, b, c});
		}
	}
	assert(cnt == n - 1);
	int res = 0;
	vector<int> d(n + 1);
	function<void(int, int)> dfs = [&](int u, int p){
		for(auto x : edges[u]){
			if(x == p) continue;
			d[x] = d[u] + 1;
			dfs(x, u);
		}
	};
	int a = 1; 
	d[a] = 0, dfs(a, a);
	for(int i=1;i<=n;i++){
		if(d[i] > d[a]) a = i;
	}
	
	d[a] = 0, dfs(a, a);
	for(int i=1;i<=n;i++){
		if(d[i] > d[a]) a = i;
	}
	
	res = 2 * n - 2 - d[a];
	for(auto x : e){
		int a = x[0], b = x[1], c = x[2];
		vector<int> par(n + 1), used(n + 1), d(n + 1);
		function<void(int)> dfs = [&](int u){
			for(auto x : edges[u]){
				if(x == par[u]) continue;
				par[x] = u, dfs(x);
			}
		}; dfs(a);
		
		vector<int> tt;
		while(b){ used[b] = 1;
			tt.push_back(b);
			b = par[b];
		}
		
		function<void(int)> dfs2 = [&](int u){
			used[u] = 1; d[u] = 0;
			for(auto x : edges[u]){
				if(used[x]) continue;
				dfs2(x);
				d[u] = max(d[u], d[x] + 1);
			}
		};
		
		int mx = 0, cyc = tt.size();
		for(auto x : tt){
			dfs2(x);
		}
		
		for(int i=1;i<cyc;i++){
			mx = max(mx, d[tt[i]] + d[tt[i-1]]);
		}
		//~ cout<<a<<" "<<b<<" "<<c<<" "<<mx<<" "<<cyc<<"\n";
		//~ cout<<c<<"\n";
		//~ for(auto x : tt) cout<<x<<" ";
		//~ cout<<"\n";
		res = min(res, 2 * n - 2 - mx - cyc + c);
	}
	
	cout<<res<<"\n";
}

Subtask #1
1.0 / 1.0

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

Subtask #2
0.0 / 2.0

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

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1422 ms 12992 KB Output is correct
2 Correct 1367 ms 13032 KB Output is correct
3 Correct 1436 ms 12816 KB Output is correct
4 Correct 1503 ms 12756 KB Output is correct
5 Correct 1409 ms 12676 KB Output is correct
6 Correct 635 ms 12516 KB Output is correct
7 Correct 1343 ms 13092 KB Output is correct
8 Correct 1389 ms 12820 KB Output is correct
9 Correct 1330 ms 12936 KB Output is correct
10 Correct 1512 ms 12736 KB Output is correct
11 Correct 1429 ms 12812 KB Output is correct
12 Correct 1405 ms 12756 KB Output is correct
13 Correct 1533 ms 12824 KB Output is correct
14 Correct 1510 ms 12812 KB Output is correct

Subtask #4
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 8 ms 11988 KB Output is correct
3 Correct 9 ms 11944 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 12064 KB Output is correct
7 Correct 8 ms 11988 KB Output is correct
8 Correct 7 ms 12064 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 7 ms 12064 KB Output is correct
11 Correct 7 ms 12064 KB Output is correct
12 Correct 7 ms 12068 KB Output is correct
13 Correct 7 ms 11988 KB Output is correct
14 Correct 7 ms 11988 KB Output is correct
15 Correct 6 ms 11988 KB Output is correct
16 Correct 7 ms 12064 KB Output is correct
17 Correct 7 ms 11988 KB Output is correct
18 Incorrect 8 ms 12068 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 7 ms 11988 KB Output is correct
2 Correct 8 ms 11988 KB Output is correct
3 Correct 9 ms 11944 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 12064 KB Output is correct
7 Correct 8 ms 11988 KB Output is correct
8 Correct 7 ms 12064 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 7 ms 12064 KB Output is correct
11 Correct 7 ms 12064 KB Output is correct
12 Correct 7 ms 12068 KB Output is correct
13 Correct 7 ms 11988 KB Output is correct
14 Correct 7 ms 11988 KB Output is correct
15 Correct 6 ms 11988 KB Output is correct
16 Correct 7 ms 12064 KB Output is correct
17 Correct 7 ms 11988 KB Output is correct
18 Incorrect 8 ms 12068 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 7 ms 11988 KB Output is correct
2 Correct 8 ms 11988 KB Output is correct
3 Correct 9 ms 11944 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 12064 KB Output is correct
7 Correct 8 ms 11988 KB Output is correct
8 Correct 7 ms 12064 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 7 ms 12064 KB Output is correct
11 Correct 7 ms 12064 KB Output is correct
12 Correct 7 ms 12068 KB Output is correct
13 Correct 7 ms 11988 KB Output is correct
14 Correct 7 ms 11988 KB Output is correct
15 Correct 6 ms 11988 KB Output is correct
16 Correct 7 ms 12064 KB Output is correct
17 Correct 7 ms 11988 KB Output is correct
18 Incorrect 8 ms 12068 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 7 ms 11988 KB Output is correct
2 Correct 8 ms 11988 KB Output is correct
3 Correct 9 ms 11944 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 12064 KB Output is correct
7 Correct 8 ms 11988 KB Output is correct
8 Correct 7 ms 12064 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 7 ms 12064 KB Output is correct
11 Correct 7 ms 12064 KB Output is correct
12 Correct 7 ms 12068 KB Output is correct
13 Correct 7 ms 11988 KB Output is correct
14 Correct 7 ms 11988 KB Output is correct
15 Correct 6 ms 11988 KB Output is correct
16 Correct 7 ms 12064 KB Output is correct
17 Correct 7 ms 11988 KB Output is correct
18 Incorrect 8 ms 12068 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 7 ms 11988 KB Output is correct
2 Correct 8 ms 11988 KB Output is correct
3 Correct 9 ms 11944 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 12064 KB Output is correct
7 Correct 8 ms 11988 KB Output is correct
8 Correct 7 ms 12064 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 7 ms 12064 KB Output is correct
11 Correct 7 ms 12064 KB Output is correct
12 Correct 7 ms 12068 KB Output is correct
13 Correct 7 ms 11988 KB Output is correct
14 Correct 7 ms 11988 KB Output is correct
15 Correct 6 ms 11988 KB Output is correct
16 Correct 7 ms 12064 KB Output is correct
17 Correct 7 ms 11988 KB Output is correct
18 Incorrect 8 ms 12068 KB Output isn't correct
19 Halted 0 ms 0 KB -