oj.uz

Submission #525855

# Submission time Handle Problem Language Result Execution time Memory
525855 2022-02-13T03:54:17 Z koioi.org-koosaga Mountains and Valleys (CCO20_day1problem3) C++17
3 / 25
 755 ms 25332 KB 
#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;
}

vector<int> ord;
int din[MAXN], dout[MAXN], piv;
int f[MAXN], far[MAXN], diam[MAXN];
vector<pi> fars[MAXN];

bool in(int u, int v){
	return din[u] <= din[v] && dout[v] <= dout[u];
}

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

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]];
		}
	}
	{
		for(int i = 0; i < n; i++){
			if(dep[i] >= 2){
				vis[i] = 1;
				vis[par[1][i]] = 1;
				f[i] = dfsl(dfsl(par[0][i]).second).first;
				vis[i] = 0;
				vis[par[1][i]] = 0;
			}
		}
		for(auto &i : ord){
			for(auto &j : gph[i]){
				if(j == par[0][i]) continue;
				far[i] = max(far[i], far[j] + 1);
				diam[i] = max({diam[i], diam[j], far[j] + 1});
				fars[i].emplace_back(far[j], j);
			}
			sort(all(fars[i]));
			reverse(all(fars[i]));
			if(sz(fars[i]) >= 2) diam[i] = max(diam[i], (int)fars[i][0].first + (int)fars[i][1].first + 2);
		}
	}
	int ans = 2 * n - 2 - diam[0];
	for(auto &x : qry){
		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;
		vector<int> ndiam;
		int maxPath = -1e9;
		for(int i = x.s; dep[i] >= dep[l] + 2; i = par[0][i]) maxPath = max(maxPath, f[i] - 3 + sz(v));
		for(int i = x.e; dep[i] >= dep[l] + 2; i = par[0][i]) maxPath = max(maxPath, f[i] - 3 + sz(v));
		if(l != x.s){
			maxPath = max(maxPath, diam[x.s] - 3 + sz(v));
		}
		if(l != x.e){
			maxPath = max(maxPath, diam[x.e] - 3 + sz(v));
		}
		{
			int new_diam = 0;
			int cnt = 1;
			for(auto &[d, v] : fars[l]){
				if(in(v, x.s) || in(v, x.e)) continue;
				new_diam += d + 1;
				cnt += 1;
				if(cnt == 2) break;
			}
			maxPath = max(maxPath, new_diam - 3 + sz(v));
		}
		for(auto &i : v){
			vis[i] = 0;
			val.push_back(dfsl(i).first);
			vis[i] = 1;
		}
		for(auto &i : v) vis[i] = 0;
		int pmax = -1e9;
		for(int i = 0; i < sz(val); i++){
			maxPath = max(maxPath, sz(val) - 1 - i + val[i] + pmax);
			pmax = max(pmax, i + val[i]);
		}
		ans = min(ans, 2 * n - 4 + x.x - maxPath);
	}
	cout << ans << endl;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23900 KB Output is correct
2 Correct 11 ms 23884 KB Output is correct
3 Correct 12 ms 23884 KB Output is correct
4 Correct 12 ms 23884 KB Output is correct
5 Correct 12 ms 23984 KB Output is correct
6 Correct 11 ms 23988 KB Output is correct
7 Correct 12 ms 23948 KB Output is correct
8 Correct 13 ms 23960 KB Output is correct
9 Correct 11 ms 23972 KB Output is correct
10 Correct 11 ms 23884 KB Output is correct
11 Correct 12 ms 23984 KB Output is correct
12 Correct 11 ms 23884 KB Output is correct
13 Correct 10 ms 23908 KB Output is correct
14 Correct 12 ms 23884 KB Output is correct
15 Correct 14 ms 24004 KB Output is correct

Subtask #2
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23900 KB Output is correct
2 Correct 11 ms 23884 KB Output is correct
3 Correct 12 ms 23884 KB Output is correct
4 Correct 12 ms 23884 KB Output is correct
5 Correct 12 ms 23984 KB Output is correct
6 Correct 11 ms 23988 KB Output is correct
7 Correct 12 ms 23948 KB Output is correct
8 Correct 13 ms 23960 KB Output is correct
9 Correct 11 ms 23972 KB Output is correct
10 Correct 11 ms 23884 KB Output is correct
11 Correct 12 ms 23984 KB Output is correct
12 Correct 11 ms 23884 KB Output is correct
13 Correct 10 ms 23908 KB Output is correct
14 Correct 12 ms 23884 KB Output is correct
15 Correct 14 ms 24004 KB Output is correct
16 Correct 13 ms 23884 KB Output is correct
17 Correct 12 ms 23896 KB Output is correct
18 Incorrect 13 ms 23884 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 664 ms 25332 KB Output is correct
2 Correct 654 ms 25316 KB Output is correct
3 Correct 641 ms 25136 KB Output is correct
4 Correct 604 ms 25128 KB Output is correct
5 Correct 581 ms 25056 KB Output is correct
6 Correct 368 ms 24876 KB Output is correct
7 Correct 691 ms 25308 KB Output is correct
8 Correct 755 ms 25220 KB Output is correct
9 Correct 706 ms 25260 KB Output is correct
10 Correct 651 ms 25228 KB Output is correct
11 Correct 678 ms 25172 KB Output is correct
12 Correct 655 ms 25104 KB Output is correct
13 Correct 610 ms 25164 KB Output is correct
14 Correct 673 ms 25180 KB Output is correct

Subtask #4
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23900 KB Output is correct
2 Correct 11 ms 23884 KB Output is correct
3 Correct 12 ms 23884 KB Output is correct
4 Correct 12 ms 23884 KB Output is correct
5 Correct 12 ms 23984 KB Output is correct
6 Correct 11 ms 23988 KB Output is correct
7 Correct 12 ms 23948 KB Output is correct
8 Correct 13 ms 23960 KB Output is correct
9 Correct 11 ms 23972 KB Output is correct
10 Correct 11 ms 23884 KB Output is correct
11 Correct 12 ms 23984 KB Output is correct
12 Correct 11 ms 23884 KB Output is correct
13 Correct 10 ms 23908 KB Output is correct
14 Correct 12 ms 23884 KB Output is correct
15 Correct 14 ms 24004 KB Output is correct
16 Correct 13 ms 23884 KB Output is correct
17 Correct 12 ms 23896 KB Output is correct
18 Incorrect 13 ms 23884 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 12 ms 23900 KB Output is correct
2 Correct 11 ms 23884 KB Output is correct
3 Correct 12 ms 23884 KB Output is correct
4 Correct 12 ms 23884 KB Output is correct
5 Correct 12 ms 23984 KB Output is correct
6 Correct 11 ms 23988 KB Output is correct
7 Correct 12 ms 23948 KB Output is correct
8 Correct 13 ms 23960 KB Output is correct
9 Correct 11 ms 23972 KB Output is correct
10 Correct 11 ms 23884 KB Output is correct
11 Correct 12 ms 23984 KB Output is correct
12 Correct 11 ms 23884 KB Output is correct
13 Correct 10 ms 23908 KB Output is correct
14 Correct 12 ms 23884 KB Output is correct
15 Correct 14 ms 24004 KB Output is correct
16 Correct 13 ms 23884 KB Output is correct
17 Correct 12 ms 23896 KB Output is correct
18 Incorrect 13 ms 23884 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 12 ms 23900 KB Output is correct
2 Correct 11 ms 23884 KB Output is correct
3 Correct 12 ms 23884 KB Output is correct
4 Correct 12 ms 23884 KB Output is correct
5 Correct 12 ms 23984 KB Output is correct
6 Correct 11 ms 23988 KB Output is correct
7 Correct 12 ms 23948 KB Output is correct
8 Correct 13 ms 23960 KB Output is correct
9 Correct 11 ms 23972 KB Output is correct
10 Correct 11 ms 23884 KB Output is correct
11 Correct 12 ms 23984 KB Output is correct
12 Correct 11 ms 23884 KB Output is correct
13 Correct 10 ms 23908 KB Output is correct
14 Correct 12 ms 23884 KB Output is correct
15 Correct 14 ms 24004 KB Output is correct
16 Correct 13 ms 23884 KB Output is correct
17 Correct 12 ms 23896 KB Output is correct
18 Incorrect 13 ms 23884 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 12 ms 23900 KB Output is correct
2 Correct 11 ms 23884 KB Output is correct
3 Correct 12 ms 23884 KB Output is correct
4 Correct 12 ms 23884 KB Output is correct
5 Correct 12 ms 23984 KB Output is correct
6 Correct 11 ms 23988 KB Output is correct
7 Correct 12 ms 23948 KB Output is correct
8 Correct 13 ms 23960 KB Output is correct
9 Correct 11 ms 23972 KB Output is correct
10 Correct 11 ms 23884 KB Output is correct
11 Correct 12 ms 23984 KB Output is correct
12 Correct 11 ms 23884 KB Output is correct
13 Correct 10 ms 23908 KB Output is correct
14 Correct 12 ms 23884 KB Output is correct
15 Correct 14 ms 24004 KB Output is correct
16 Correct 13 ms 23884 KB Output is correct
17 Correct 12 ms 23896 KB Output is correct
18 Incorrect 13 ms 23884 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 12 ms 23900 KB Output is correct
2 Correct 11 ms 23884 KB Output is correct
3 Correct 12 ms 23884 KB Output is correct
4 Correct 12 ms 23884 KB Output is correct
5 Correct 12 ms 23984 KB Output is correct
6 Correct 11 ms 23988 KB Output is correct
7 Correct 12 ms 23948 KB Output is correct
8 Correct 13 ms 23960 KB Output is correct
9 Correct 11 ms 23972 KB Output is correct
10 Correct 11 ms 23884 KB Output is correct
11 Correct 12 ms 23984 KB Output is correct
12 Correct 11 ms 23884 KB Output is correct
13 Correct 10 ms 23908 KB Output is correct
14 Correct 12 ms 23884 KB Output is correct
15 Correct 14 ms 24004 KB Output is correct
16 Correct 13 ms 23884 KB Output is correct
17 Correct 12 ms 23896 KB Output is correct
18 Incorrect 13 ms 23884 KB Output isn't correct
19 Halted 0 ms 0 KB -