Submission #525857

#	Time	Username	Problem	Language	Result	Execution time	Memory
525857		koioi.org-koosaga	Mountains and Valleys (CCO20_day1problem3)	C++17	3 / 25	760 ms	25420 KiB

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;
}

vector<int> ord;
int din[MAXN], dout[MAXN], piv;
int f[MAXN], far[MAXN], diam[MAXN], pfar[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){
	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;
				f[i] = dfsl(dfsl(par[0][i]).second).first;
				vis[i] = 0;
				vis[par[1][i]] = 0;
			}
		}
		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;
			int cnt = 0;
			for(auto &j : fars[par[0][i]]){
				if(j.second == i) continue;
				cnt++;
				pfar[i] += j.first + 1;
				if(cnt == 2) 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;
		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 / 1
• Subtask 2: 0 / 2
• Subtask 3: 2 / 2
• Subtask 4: 0 / 6
• Subtask 5: 0 / 2
• Subtask 6: 0 / 3
• Subtask 7: 0 / 5
• Subtask 8: 0 / 4