Submission #525733

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
525733	2022-02-12T16:38:58 Z	koioi.org-koosaga	Mountains and Valleys (CCO20_day1problem3)	C++17	2 / 25	13 ms	13180 KB

Main

#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pi;
const int MAXN = 500005;

struct edge{
	int s, e, x;
};

int n, m;
vector<int> gph[MAXN];
int par[20][MAXN], dep[MAXN];

int lca(int x, int y){
	if(dep[x] > dep[y]) swap(x, y);
	int dx = dep[y] - dep[x];
	for(int i = 0; dx; i++){
		if(dx & 1) y = par[i][y];
		dx >>= 1;
	}
	for(int i = 19; i >= 0; i--){
		if(par[i][x] != par[i][y]){
			x = par[i][x];
			y = par[i][y];
		}
	}
	if(x != y) return par[0][x];
	return x;
}

void dfs(int x, int p = -1){
	for(auto &y : gph[x]){
		if(y == p) continue;
		par[0][y] = x;
		dep[y] = dep[x] + 1;
		dfs(y, x);
	}
}

bool vis[MAXN];

pi dfsl(int x, int p = -1){
	pi ret(0, x);
	for(auto &y : gph[x]){
		if(y == p || vis[y]) continue;
		auto ans = dfsl(y, x);
		ans.first++;
		ret = max(ret, ans);
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	vector<edge> qry;
	for(int i = 0; i < m; i++){
		int s, e, x; cin >> s >> e >> x;
		if(x == 1){
			gph[s].push_back(e);
			gph[e].push_back(s);
		}
		else{
			qry.push_back({s, e, x});
		}
	}
	dfs(0);
	for(int i = 1; i < 20; i++){
		for(int j = 0; j < n; j++){
			par[i][j] = par[i-1][par[i-1][j]];
		}
	}
	int ans = 2 * n - 2 - dfsl(dfsl(0).second).first;
	for(auto &x : qry){
		break;
		int l = lca(x.s, x.e);
		vector<int> v, w;
		for(int i = x.s; i != l; i = par[0][i]) v.push_back(i);
		for(int i = x.e; i != l; i = par[0][i]) w.push_back(i);
		reverse(all(w));
		v.push_back(l);
		for(auto &i : w) v.push_back(i);
		for(auto &i : v) vis[i] = 1;
		vector<int> val;
		for(auto &i : v){
			val.push_back(dfsl(i).first);
		}
		for(auto &i : v) vis[i] = 0;
		int maxPath = 0;
		for(int i = 0; i < sz(val); i++){
			for(int j = i + 1; j < sz(val); j++){
				maxPath = max(maxPath, sz(val) - 1 - j + i + val[i] + val[j] + x.x);
			}
		}
		ans = min(ans, 2 * n - 4 + 2 * x.x - maxPath);
	}
	cout << ans << endl;
}

Subtask #1
0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	12108 KB	Output is correct
2	Correct	7 ms	12108 KB	Output is correct
3	Correct	6 ms	12108 KB	Output is correct
4	Correct	6 ms	12108 KB	Output is correct
5	Correct	7 ms	12108 KB	Output is correct
6	Correct	6 ms	12108 KB	Output is correct
7	Correct	6 ms	12204 KB	Output is correct
8	Correct	9 ms	12212 KB	Output is correct
9	Correct	7 ms	12108 KB	Output is correct
10	Correct	9 ms	12108 KB	Output is correct
11	Incorrect	6 ms	12164 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #2
0.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	12108 KB	Output is correct
2	Correct	7 ms	12108 KB	Output is correct
3	Correct	6 ms	12108 KB	Output is correct
4	Correct	6 ms	12108 KB	Output is correct
5	Correct	7 ms	12108 KB	Output is correct
6	Correct	6 ms	12108 KB	Output is correct
7	Correct	6 ms	12204 KB	Output is correct
8	Correct	9 ms	12212 KB	Output is correct
9	Correct	7 ms	12108 KB	Output is correct
10	Correct	9 ms	12108 KB	Output is correct
11	Incorrect	6 ms	12164 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #3
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	13132 KB	Output is correct
2	Correct	10 ms	13172 KB	Output is correct
3	Correct	11 ms	13068 KB	Output is correct
4	Correct	9 ms	12936 KB	Output is correct
5	Correct	10 ms	12916 KB	Output is correct
6	Correct	10 ms	12892 KB	Output is correct
7	Correct	13 ms	13180 KB	Output is correct
8	Correct	10 ms	13004 KB	Output is correct
9	Correct	10 ms	13136 KB	Output is correct
10	Correct	9 ms	13016 KB	Output is correct
11	Correct	10 ms	13004 KB	Output is correct
12	Correct	10 ms	13008 KB	Output is correct
13	Correct	10 ms	13004 KB	Output is correct
14	Correct	11 ms	13004 KB	Output is correct

Subtask #4
0.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	12108 KB	Output is correct
2	Correct	7 ms	12108 KB	Output is correct
3	Correct	6 ms	12108 KB	Output is correct
4	Correct	6 ms	12108 KB	Output is correct
5	Correct	7 ms	12108 KB	Output is correct
6	Correct	6 ms	12108 KB	Output is correct
7	Correct	6 ms	12204 KB	Output is correct
8	Correct	9 ms	12212 KB	Output is correct
9	Correct	7 ms	12108 KB	Output is correct
10	Correct	9 ms	12108 KB	Output is correct
11	Incorrect	6 ms	12164 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	12108 KB	Output is correct
2	Correct	7 ms	12108 KB	Output is correct
3	Correct	6 ms	12108 KB	Output is correct
4	Correct	6 ms	12108 KB	Output is correct
5	Correct	7 ms	12108 KB	Output is correct
6	Correct	6 ms	12108 KB	Output is correct
7	Correct	6 ms	12204 KB	Output is correct
8	Correct	9 ms	12212 KB	Output is correct
9	Correct	7 ms	12108 KB	Output is correct
10	Correct	9 ms	12108 KB	Output is correct
11	Incorrect	6 ms	12164 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #6
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	12108 KB	Output is correct
2	Correct	7 ms	12108 KB	Output is correct
3	Correct	6 ms	12108 KB	Output is correct
4	Correct	6 ms	12108 KB	Output is correct
5	Correct	7 ms	12108 KB	Output is correct
6	Correct	6 ms	12108 KB	Output is correct
7	Correct	6 ms	12204 KB	Output is correct
8	Correct	9 ms	12212 KB	Output is correct
9	Correct	7 ms	12108 KB	Output is correct
10	Correct	9 ms	12108 KB	Output is correct
11	Incorrect	6 ms	12164 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #7
0.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	12108 KB	Output is correct
2	Correct	7 ms	12108 KB	Output is correct
3	Correct	6 ms	12108 KB	Output is correct
4	Correct	6 ms	12108 KB	Output is correct
5	Correct	7 ms	12108 KB	Output is correct
6	Correct	6 ms	12108 KB	Output is correct
7	Correct	6 ms	12204 KB	Output is correct
8	Correct	9 ms	12212 KB	Output is correct
9	Correct	7 ms	12108 KB	Output is correct
10	Correct	9 ms	12108 KB	Output is correct
11	Incorrect	6 ms	12164 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #8
0.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	12108 KB	Output is correct
2	Correct	7 ms	12108 KB	Output is correct
3	Correct	6 ms	12108 KB	Output is correct
4	Correct	6 ms	12108 KB	Output is correct
5	Correct	7 ms	12108 KB	Output is correct
6	Correct	6 ms	12108 KB	Output is correct
7	Correct	6 ms	12204 KB	Output is correct
8	Correct	9 ms	12212 KB	Output is correct
9	Correct	7 ms	12108 KB	Output is correct
10	Correct	9 ms	12108 KB	Output is correct
11	Incorrect	6 ms	12164 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Submission #525733

Compilation message