oj.uz

Submission #525860

# Submission time Handle Problem Language Result Execution time Memory
525860 2022-02-13T04:03:53 Z koioi.org-koosaga Mountains and Valleys (CCO20_day1problem3) C++17
0 / 25
 550 ms 25956 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[20][MAXN], far[MAXN], diam[MAXN], pfar[MAXN];
vector<pi> fars[MAXN];

int fPathMax(int x, int v){
	int ans = -1e9;
	for(int i = 0; v; i++){
		if(v & 1){
			ans = max(ans, f[i][x]);
			x = par[i][x];
		}
		v >>= 1;
	}
	return ans;
}

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

void dfs(int x, int p = -1){
	ord.push_back(x);
	din[x] = ++piv;
	for(auto &y : gph[x]){
		if(y == p) continue;
		par[0][y] = x;
		dep[y] = dep[x] + 1;
		dfs(y, 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;
				// n^2
				f[0][i] = dfsl(dfsl(par[0][i]).second).first;
				vis[i] = 0;
				vis[par[1][i]] = 0;
			}
		}
		for(int i = 1; i < 20; i++){
			for(int j = 0; j < n; j++){
				f[i][j] = max(f[i-1][j], f[i-1][par[i-1][j]]);
			}
		}
		reverse(all(ord));
		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);
		}
		reverse(all(ord));
		for(auto &i : ord){
			if(i == 0) continue;
			for(auto &j : fars[par[0][i]]){
				if(j.second == i) continue;
				pfar[i] = j.first + 1;
				break;
			}
			fars[i].emplace_back(pfar[i], par[0][i]);
			sort(all(fars[i]));
			reverse(all(fars[i]));
		}
	}
	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;
		if(dep[x.s] >= dep[l] + 2){
			maxPath = max(maxPath, fPathMax(x.s, dep[x.s] - dep[l] + 1) - 3 + sz(v));
		}
		if(dep[x.e] >= dep[l] + 2){
			maxPath = max(maxPath, fPathMax(x.s, dep[x.e] - dep[l] + 1) - 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)) && v != par[0][l]) 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
0.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24140 KB Output is correct
2 Correct 11 ms 24140 KB Output is correct
3 Correct 13 ms 24132 KB Output is correct
4 Correct 11 ms 24140 KB Output is correct
5 Incorrect 12 ms 24128 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24140 KB Output is correct
2 Correct 11 ms 24140 KB Output is correct
3 Correct 13 ms 24132 KB Output is correct
4 Correct 11 ms 24140 KB Output is correct
5 Incorrect 12 ms 24128 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 25868 KB Output is correct
2 Correct 545 ms 25956 KB Output is correct
3 Correct 550 ms 25796 KB Output is correct
4 Correct 541 ms 25752 KB Output is correct
5 Correct 523 ms 25684 KB Output is correct
6 Correct 377 ms 25668 KB Output is correct
7 Incorrect 549 ms 25932 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24140 KB Output is correct
2 Correct 11 ms 24140 KB Output is correct
3 Correct 13 ms 24132 KB Output is correct
4 Correct 11 ms 24140 KB Output is correct
5 Incorrect 12 ms 24128 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24140 KB Output is correct
2 Correct 11 ms 24140 KB Output is correct
3 Correct 13 ms 24132 KB Output is correct
4 Correct 11 ms 24140 KB Output is correct
5 Incorrect 12 ms 24128 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24140 KB Output is correct
2 Correct 11 ms 24140 KB Output is correct
3 Correct 13 ms 24132 KB Output is correct
4 Correct 11 ms 24140 KB Output is correct
5 Incorrect 12 ms 24128 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24140 KB Output is correct
2 Correct 11 ms 24140 KB Output is correct
3 Correct 13 ms 24132 KB Output is correct
4 Correct 11 ms 24140 KB Output is correct
5 Incorrect 12 ms 24128 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #8
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24140 KB Output is correct
2 Correct 11 ms 24140 KB Output is correct
3 Correct 13 ms 24132 KB Output is correct
4 Correct 11 ms 24140 KB Output is correct
5 Incorrect 12 ms 24128 KB Output isn't correct
6 Halted 0 ms 0 KB -