Submission #525734

#	Time	Username	Problem	Language	Result	Execution time	Memory
525734		koioi.org-koosaga	Mountains and Valleys (CCO20_day1problem3)	C++17	11 / 25	7084 ms	13256 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;
}

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 diam = dfsl(dfsl(0).second).first;
	int ans = 2 * n - 2 - diam;
	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(auto &i : v){
			vis[i] = 0;
			val.push_back(dfsl(i).first);
			int ndiam = dfsl(dfsl(i).second).first;
			maxPath = max(maxPath, ndiam - 3 + sz(v));
			vis[i] = 1;
		}
		for(auto &i : v) vis[i] = 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]);
			}
		}
		ans = min(ans, 2 * n - 4 + x.x - maxPath);
	}
	cout << ans << endl;
}

• Subtask 1: 1 / 1
• Subtask 2: 2 / 2
• Subtask 3: 0 / 2
• Subtask 4: 6 / 6
• Subtask 5: 2 / 2
• Subtask 6: 0 / 3
• Subtask 7: 0 / 5
• Subtask 8: 0 / 4