oj.uz

Submission #525856

# Submission time Handle Problem Language Result Execution time Memory
525856 2022-02-13T03:55:02 Z koioi.org-koosaga Mountains and Valleys (CCO20_day1problem3) C++17
3 / 25
 731 ms 25312 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 = 0;
			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 13 ms 23876 KB Output is correct
2 Correct 12 ms 23984 KB Output is correct
3 Correct 10 ms 23884 KB Output is correct
4 Correct 12 ms 23884 KB Output is correct
5 Correct 14 ms 24004 KB Output is correct
6 Correct 12 ms 23964 KB Output is correct
7 Correct 11 ms 23884 KB Output is correct
8 Correct 11 ms 23900 KB Output is correct
9 Correct 11 ms 23884 KB Output is correct
10 Correct 12 ms 23884 KB Output is correct
11 Correct 11 ms 23884 KB Output is correct
12 Correct 11 ms 23992 KB Output is correct
13 Correct 11 ms 23924 KB Output is correct
14 Correct 11 ms 23984 KB Output is correct
15 Correct 11 ms 23884 KB Output is correct

Subtask #2
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23876 KB Output is correct
2 Correct 12 ms 23984 KB Output is correct
3 Correct 10 ms 23884 KB Output is correct
4 Correct 12 ms 23884 KB Output is correct
5 Correct 14 ms 24004 KB Output is correct
6 Correct 12 ms 23964 KB Output is correct
7 Correct 11 ms 23884 KB Output is correct
8 Correct 11 ms 23900 KB Output is correct
9 Correct 11 ms 23884 KB Output is correct
10 Correct 12 ms 23884 KB Output is correct
11 Correct 11 ms 23884 KB Output is correct
12 Correct 11 ms 23992 KB Output is correct
13 Correct 11 ms 23924 KB Output is correct
14 Correct 11 ms 23984 KB Output is correct
15 Correct 11 ms 23884 KB Output is correct
16 Correct 13 ms 23940 KB Output is correct
17 Correct 11 ms 23884 KB Output is correct
18 Incorrect 12 ms 23892 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 641 ms 25252 KB Output is correct
2 Correct 637 ms 25312 KB Output is correct
3 Correct 619 ms 25136 KB Output is correct
4 Correct 588 ms 25116 KB Output is correct
5 Correct 604 ms 25072 KB Output is correct
6 Correct 376 ms 24900 KB Output is correct
7 Correct 628 ms 25288 KB Output is correct
8 Correct 731 ms 25116 KB Output is correct
9 Correct 660 ms 25264 KB Output is correct
10 Correct 592 ms 25128 KB Output is correct
11 Correct 594 ms 25300 KB Output is correct
12 Correct 601 ms 25108 KB Output is correct
13 Correct 689 ms 25176 KB Output is correct
14 Correct 600 ms 25176 KB Output is correct

Subtask #4
0.0 / 6.0

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