Submission #547913

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
547913	2022-04-12T03:00:00 Z	amunduzbaev	Mountains and Valleys (CCO20_day1problem3)	C++17	1 / 25	7000 ms	12876 KB

Main

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
//~ #define int long long
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), rr(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] = rr[u] = 0;
			for(auto x : edges[u]){
				if(used[x]) continue;
				dfs2(x);
				rr[u] = max(rr[u], rr[x]);
				rr[u] = max(rr[u], d[u] + d[x] + 1);
				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]]);
		}
		
		int tot = (cyc - 1) + c;
		int ed = 2 * (n - 1 + c);
		res = min(res, ed - tot - mx - 1);
		
		for(int i=0;i<cyc;i++){
			int sub = 0;
			res = min(res, ed - tot - rr[tt[i]]);
			for(int j=i+1;j<cyc;j++){
				sub++;
				res = min(res, ed - max(sub, tot - sub) - d[tt[i]] - d[tt[j]]);
			}
		}
	}
	
	cout<<res<<"\n";
}

/*

18 18
0 1 1
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 5
7 8 1
8 9 1
9 4 1
8 10 1
10 11 1
11 12 1
12 13 1
6 14 1
14 15 1
15 16 1
16 17 1

*/

Subtask #1
1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	11988 KB	Output is correct
2	Correct	7 ms	11988 KB	Output is correct
3	Correct	7 ms	11988 KB	Output is correct
4	Correct	7 ms	11988 KB	Output is correct
5	Correct	6 ms	12036 KB	Output is correct
6	Correct	7 ms	11988 KB	Output is correct
7	Correct	6 ms	11988 KB	Output is correct
8	Correct	6 ms	12060 KB	Output is correct
9	Correct	7 ms	11988 KB	Output is correct
10	Correct	7 ms	11988 KB	Output is correct
11	Correct	6 ms	11936 KB	Output is correct
12	Correct	6 ms	11988 KB	Output is correct
13	Correct	6 ms	11988 KB	Output is correct
14	Correct	7 ms	11988 KB	Output is correct
15	Correct	7 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	7 ms	11988 KB	Output is correct
3	Correct	7 ms	11988 KB	Output is correct
4	Correct	7 ms	11988 KB	Output is correct
5	Correct	6 ms	12036 KB	Output is correct
6	Correct	7 ms	11988 KB	Output is correct
7	Correct	6 ms	11988 KB	Output is correct
8	Correct	6 ms	12060 KB	Output is correct
9	Correct	7 ms	11988 KB	Output is correct
10	Correct	7 ms	11988 KB	Output is correct
11	Correct	6 ms	11936 KB	Output is correct
12	Correct	6 ms	11988 KB	Output is correct
13	Correct	6 ms	11988 KB	Output is correct
14	Correct	7 ms	11988 KB	Output is correct
15	Correct	7 ms	11988 KB	Output is correct
16	Correct	6 ms	11988 KB	Output is correct
17	Correct	7 ms	11988 KB	Output is correct
18	Correct	9 ms	11988 KB	Output is correct
19	Correct	7 ms	11988 KB	Output is correct
20	Correct	7 ms	11988 KB	Output is correct
21	Correct	7 ms	12060 KB	Output is correct
22	Correct	7 ms	12116 KB	Output is correct
23	Correct	7 ms	12060 KB	Output is correct
24	Correct	7 ms	12120 KB	Output is correct
25	Correct	8 ms	12004 KB	Output is correct
26	Correct	7 ms	11972 KB	Output is correct
27	Correct	7 ms	11984 KB	Output is correct
28	Correct	8 ms	11988 KB	Output is correct
29	Correct	8 ms	11988 KB	Output is correct
30	Correct	10 ms	11988 KB	Output is correct
31	Correct	8 ms	11988 KB	Output is correct
32	Incorrect	9 ms	11992 KB	Output isn't correct
33	Halted	0 ms	0 KB	-

Subtask #3
0.0 / 2.0

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

Subtask #4
0.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	11988 KB	Output is correct
2	Correct	7 ms	11988 KB	Output is correct
3	Correct	7 ms	11988 KB	Output is correct
4	Correct	7 ms	11988 KB	Output is correct
5	Correct	6 ms	12036 KB	Output is correct
6	Correct	7 ms	11988 KB	Output is correct
7	Correct	6 ms	11988 KB	Output is correct
8	Correct	6 ms	12060 KB	Output is correct
9	Correct	7 ms	11988 KB	Output is correct
10	Correct	7 ms	11988 KB	Output is correct
11	Correct	6 ms	11936 KB	Output is correct
12	Correct	6 ms	11988 KB	Output is correct
13	Correct	6 ms	11988 KB	Output is correct
14	Correct	7 ms	11988 KB	Output is correct
15	Correct	7 ms	11988 KB	Output is correct
16	Correct	6 ms	11988 KB	Output is correct
17	Correct	7 ms	11988 KB	Output is correct
18	Correct	9 ms	11988 KB	Output is correct
19	Correct	7 ms	11988 KB	Output is correct
20	Correct	7 ms	11988 KB	Output is correct
21	Correct	7 ms	12060 KB	Output is correct
22	Correct	7 ms	12116 KB	Output is correct
23	Correct	7 ms	12060 KB	Output is correct
24	Correct	7 ms	12120 KB	Output is correct
25	Correct	8 ms	12004 KB	Output is correct
26	Correct	7 ms	11972 KB	Output is correct
27	Correct	7 ms	11984 KB	Output is correct
28	Correct	8 ms	11988 KB	Output is correct
29	Correct	8 ms	11988 KB	Output is correct
30	Correct	10 ms	11988 KB	Output is correct
31	Correct	8 ms	11988 KB	Output is correct
32	Incorrect	9 ms	11992 KB	Output isn't correct
33	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	7 ms	11988 KB	Output is correct
3	Correct	7 ms	11988 KB	Output is correct
4	Correct	7 ms	11988 KB	Output is correct
5	Correct	6 ms	12036 KB	Output is correct
6	Correct	7 ms	11988 KB	Output is correct
7	Correct	6 ms	11988 KB	Output is correct
8	Correct	6 ms	12060 KB	Output is correct
9	Correct	7 ms	11988 KB	Output is correct
10	Correct	7 ms	11988 KB	Output is correct
11	Correct	6 ms	11936 KB	Output is correct
12	Correct	6 ms	11988 KB	Output is correct
13	Correct	6 ms	11988 KB	Output is correct
14	Correct	7 ms	11988 KB	Output is correct
15	Correct	7 ms	11988 KB	Output is correct
16	Correct	6 ms	11988 KB	Output is correct
17	Correct	7 ms	11988 KB	Output is correct
18	Correct	9 ms	11988 KB	Output is correct
19	Correct	7 ms	11988 KB	Output is correct
20	Correct	7 ms	11988 KB	Output is correct
21	Correct	7 ms	12060 KB	Output is correct
22	Correct	7 ms	12116 KB	Output is correct
23	Correct	7 ms	12060 KB	Output is correct
24	Correct	7 ms	12120 KB	Output is correct
25	Correct	8 ms	12004 KB	Output is correct
26	Correct	7 ms	11972 KB	Output is correct
27	Correct	7 ms	11984 KB	Output is correct
28	Correct	8 ms	11988 KB	Output is correct
29	Correct	8 ms	11988 KB	Output is correct
30	Correct	10 ms	11988 KB	Output is correct
31	Correct	8 ms	11988 KB	Output is correct
32	Incorrect	9 ms	11992 KB	Output isn't correct
33	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	7 ms	11988 KB	Output is correct
3	Correct	7 ms	11988 KB	Output is correct
4	Correct	7 ms	11988 KB	Output is correct
5	Correct	6 ms	12036 KB	Output is correct
6	Correct	7 ms	11988 KB	Output is correct
7	Correct	6 ms	11988 KB	Output is correct
8	Correct	6 ms	12060 KB	Output is correct
9	Correct	7 ms	11988 KB	Output is correct
10	Correct	7 ms	11988 KB	Output is correct
11	Correct	6 ms	11936 KB	Output is correct
12	Correct	6 ms	11988 KB	Output is correct
13	Correct	6 ms	11988 KB	Output is correct
14	Correct	7 ms	11988 KB	Output is correct
15	Correct	7 ms	11988 KB	Output is correct
16	Correct	6 ms	11988 KB	Output is correct
17	Correct	7 ms	11988 KB	Output is correct
18	Correct	9 ms	11988 KB	Output is correct
19	Correct	7 ms	11988 KB	Output is correct
20	Correct	7 ms	11988 KB	Output is correct
21	Correct	7 ms	12060 KB	Output is correct
22	Correct	7 ms	12116 KB	Output is correct
23	Correct	7 ms	12060 KB	Output is correct
24	Correct	7 ms	12120 KB	Output is correct
25	Correct	8 ms	12004 KB	Output is correct
26	Correct	7 ms	11972 KB	Output is correct
27	Correct	7 ms	11984 KB	Output is correct
28	Correct	8 ms	11988 KB	Output is correct
29	Correct	8 ms	11988 KB	Output is correct
30	Correct	10 ms	11988 KB	Output is correct
31	Correct	8 ms	11988 KB	Output is correct
32	Incorrect	9 ms	11992 KB	Output isn't correct
33	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	7 ms	11988 KB	Output is correct
3	Correct	7 ms	11988 KB	Output is correct
4	Correct	7 ms	11988 KB	Output is correct
5	Correct	6 ms	12036 KB	Output is correct
6	Correct	7 ms	11988 KB	Output is correct
7	Correct	6 ms	11988 KB	Output is correct
8	Correct	6 ms	12060 KB	Output is correct
9	Correct	7 ms	11988 KB	Output is correct
10	Correct	7 ms	11988 KB	Output is correct
11	Correct	6 ms	11936 KB	Output is correct
12	Correct	6 ms	11988 KB	Output is correct
13	Correct	6 ms	11988 KB	Output is correct
14	Correct	7 ms	11988 KB	Output is correct
15	Correct	7 ms	11988 KB	Output is correct
16	Correct	6 ms	11988 KB	Output is correct
17	Correct	7 ms	11988 KB	Output is correct
18	Correct	9 ms	11988 KB	Output is correct
19	Correct	7 ms	11988 KB	Output is correct
20	Correct	7 ms	11988 KB	Output is correct
21	Correct	7 ms	12060 KB	Output is correct
22	Correct	7 ms	12116 KB	Output is correct
23	Correct	7 ms	12060 KB	Output is correct
24	Correct	7 ms	12120 KB	Output is correct
25	Correct	8 ms	12004 KB	Output is correct
26	Correct	7 ms	11972 KB	Output is correct
27	Correct	7 ms	11984 KB	Output is correct
28	Correct	8 ms	11988 KB	Output is correct
29	Correct	8 ms	11988 KB	Output is correct
30	Correct	10 ms	11988 KB	Output is correct
31	Correct	8 ms	11988 KB	Output is correct
32	Incorrect	9 ms	11992 KB	Output isn't correct
33	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	7 ms	11988 KB	Output is correct
3	Correct	7 ms	11988 KB	Output is correct
4	Correct	7 ms	11988 KB	Output is correct
5	Correct	6 ms	12036 KB	Output is correct
6	Correct	7 ms	11988 KB	Output is correct
7	Correct	6 ms	11988 KB	Output is correct
8	Correct	6 ms	12060 KB	Output is correct
9	Correct	7 ms	11988 KB	Output is correct
10	Correct	7 ms	11988 KB	Output is correct
11	Correct	6 ms	11936 KB	Output is correct
12	Correct	6 ms	11988 KB	Output is correct
13	Correct	6 ms	11988 KB	Output is correct
14	Correct	7 ms	11988 KB	Output is correct
15	Correct	7 ms	11988 KB	Output is correct
16	Correct	6 ms	11988 KB	Output is correct
17	Correct	7 ms	11988 KB	Output is correct
18	Correct	9 ms	11988 KB	Output is correct
19	Correct	7 ms	11988 KB	Output is correct
20	Correct	7 ms	11988 KB	Output is correct
21	Correct	7 ms	12060 KB	Output is correct
22	Correct	7 ms	12116 KB	Output is correct
23	Correct	7 ms	12060 KB	Output is correct
24	Correct	7 ms	12120 KB	Output is correct
25	Correct	8 ms	12004 KB	Output is correct
26	Correct	7 ms	11972 KB	Output is correct
27	Correct	7 ms	11984 KB	Output is correct
28	Correct	8 ms	11988 KB	Output is correct
29	Correct	8 ms	11988 KB	Output is correct
30	Correct	10 ms	11988 KB	Output is correct
31	Correct	8 ms	11988 KB	Output is correct
32	Incorrect	9 ms	11992 KB	Output isn't correct
33	Halted	0 ms	0 KB	-

Submission #547913

Compilation message