Submission #267068

#	Time	Username	Problem	Language	Result	Execution time	Memory
267068		ChrisT	Mountains and Valleys (CCO20_day1problem3)	C++17	21 / 25	7066 ms	185788 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using ll = long long;
#define all(x) (x).begin(),(x).end()
const int MN = 5e5+4, MOD = 998244353, BASE = 31;
vector<int> adj[MN];
struct Edge {
	int a,b,w;
};
int sum, diam, ret, n, subREE[MN], down[MN], down2[MN], pp[MN], which[MN], up[MN], cc, comp[MN], sz[MN], depth[MN], subDiam[MN], wotDown[MN][2], wotDiam[MN], valDown[MN][3], valDiam[MN][2], case1[MN], case2[MN], case3[MN], upDiam[MN]; bool done[MN]; ll iters;
void dfs (int cur, int par = -1) {
	down[cur] = down2[cur] = 0;
	for (int i : adj[cur]) if (i != par) {
		dfs(i,cur); ++sum;
		int d = down[i] + 1;
		if (d > down[cur]) {
			down2[cur] = down[cur];
			down[cur] = d;
		} else down2[cur] = max(down2[cur],d);
	}
	diam = max(diam,down[cur] + down2[cur]);
}
void dfs3 (int cur, int par = -1) {
	pp[cur] = par;
	if (~par) up[cur] = max(up[par],cur == wotDown[par][0] ? valDown[par][1] : valDown[par][0]) + 1;
	else up[cur] = 0;
	for (int i : adj[cur]) if (i != par) {
		dfs3(i,cur);
	}
}
int solve (int rt) {
	sum = 0; diam = 0;
	dfs(rt);
	return sum * 2 - diam;
}
int getsz (int cur, int par = -1) {
	sz[cur] = 1;
	for (int i : adj[cur]) if (i != par && !done[i]) {
		sz[cur] += getsz(i,cur);
	}
	return sz[cur];
}
int getcent (int cur, int tot, int par = -1) {
	for (int i : adj[cur])
		if (i != par && !done[i] && sz[i] > (tot>>1))
			return getcent(i,tot,cur);
	return cur;
}
void godown (int cur, int par) {
	depth[cur] = depth[par] + 1;
	valDown[cur][0]=valDown[cur][1]=valDown[cur][2]=valDiam[cur][0]=valDiam[cur][1]=0; comp[cur] = cc;
	for (int i : adj[cur]) if (i != par) {
		int d,dia,who;
		if (!done[i]) {
			godown(i,cur);
			dia = subDiam[i]; d = valDown[i][0] + 1; who = i;
		} else {
			if (pp[i] == cur) {
				dia = subREE[i]; d = down[i] + 1;
			} else {
				d = up[cur]; dia = upDiam[cur];
			}
			who = -1;
		}
		if (d > valDown[cur][0]) {
			valDown[cur][2] = valDown[cur][1];
			valDown[cur][1] = valDown[cur][0];
			valDown[cur][0] = d;
			wotDown[cur][1] = wotDown[cur][0];
			wotDown[cur][0] = who;
		} else if (d > valDown[cur][1]) {
			valDown[cur][2] = valDown[cur][1];
			valDown[cur][1] = d;
			wotDown[cur][1] = who;
		} else valDown[cur][2] = max(valDown[cur][2],d);
		if (dia > valDiam[cur][0]) {
			valDiam[cur][1] = valDiam[cur][0];
			valDiam[cur][0] = dia;
			wotDiam[cur] = who;
		} else valDiam[cur][1] = max(valDiam[cur][1],dia);
	}
	subDiam[cur] = max(valDiam[cur][0],valDown[cur][0] + valDown[cur][1]);
}
void goup (int cur, int par = -1, int push = 0, int push2 = 0) {
	case1[cur] = max(push,subDiam[cur]); case2[cur] = max(push2,valDown[cur][0]);
	for (int i : adj[cur]) if (i != par && !done[i]) {
		bool go = i == wotDown[cur][0];
		int direct = valDown[cur][go] + valDown[cur][1 + (go || i == wotDown[cur][1])];
		int indirect = valDiam[cur][i == wotDiam[cur]];
		int togo = valDown[cur][go];
		case3[i] = max(case3[cur],togo+depth[cur]);
		goup(i,cur,max({push,indirect,direct}),max(push2,togo) + 1);
	}
}
void prep (int cur, int par = -1, int push = 0) {
	upDiam[cur] = push; subREE[cur] = subDiam[cur];
	push = max(push,up[cur]);
	for (int i : adj[cur]) if (i != par) {
		bool go = i == wotDown[cur][0];
		int direct = valDown[cur][go] + valDown[cur][1 + (go || i == wotDown[cur][1])];
		int indirect = valDiam[cur][i == wotDiam[cur]];
		int whoops = valDown[cur][go] + up[cur];
		prep(i,cur,max({push,whoops,direct,indirect}));
	}
	
}
void solve (int cur, vector<Edge> &queries) {
	int cent = getcent(cur,getsz(cur));
	cc = 0; vector<pii> diams, downs;
	depth[cent] = 0; done[cent] = 1; case2[cent] = 0;
	for (int i : adj[cent]) {
		if (!done[i]) {
			godown(i,cent); case3[i] = 0;
			goup(i,cent,0); diams.emplace_back(subDiam[i],cc); downs.emplace_back(valDown[i][0] + 1, cc);
			++cc;
		} else {
			if (pp[i] == cent) {
				diams.emplace_back(subREE[i],-1); downs.emplace_back(down[i] + 1, -1);
			} else {
				downs.emplace_back(up[cent], -1); diams.emplace_back(upDiam[cent],-1);
			}
		}
	}
	sort(diams.rbegin(),diams.rend()); sort(downs.rbegin(),downs.rend());
	vector<vector<Edge>> togo(cc);
	for (Edge q : queries) {
		if (q.a == cent || q.b == cent) {
			if (q.a == cent) swap(q.a,q.b);
			int direct = 0, cnt = 0, best = 0;
			for (pii p : downs) if (p.second != comp[q.a]) {
				++cnt; direct += p.first;
				if (cnt == 2) break;
				best = p.first;
			}
			int indirect = 0;
			for (pii p : diams) if (p.second != comp[q.a]) {
				indirect = p.first;
				break;
			}
			int len = max({direct,indirect,case1[q.a]});
			int cyc = q.w + depth[q.a];
			cnt = n - 1 - depth[q.a];
			ret = min(ret,cnt * 2 + cyc - len);
			int yeet = q.w + max({case2[q.a]+case2[q.b],depth[q.a]+best+case2[q.b],case2[q.a]+best+depth[q.b]});
			ret = min(ret,(n - 2 + q.w) * 2 - yeet);
		}
		else if (comp[q.a] == comp[q.b]) togo[comp[q.a]].push_back(q);
		else {
			int direct = 0, cnt = 0, best = 0;
			for (pii p : downs) if (p.second != comp[q.a] && p.second != comp[q.b]) {
				++cnt; direct += p.first;
				if (cnt == 2) break;
				best = p.first;
			}
			int indirect = 0;
			for (pii p : diams) if (p.second != comp[q.a] && p.second != comp[q.b]) {
				indirect = p.first;
				break;
			}
			int len = max({direct,indirect,case1[q.a],case1[q.b]});
			int cyc = q.w + depth[q.a] + depth[q.b];
			cnt = n - 1 - depth[q.a] - depth[q.b];
			ret = min(ret,cnt * 2 + cyc - len);
			int yeet = q.w + max({case2[q.a]+case2[q.b],depth[q.a]+best+case2[q.b],case2[q.a]+best+depth[q.b],case3[q.a]+valDown[q.a][0]+depth[q.b],case3[q.b]+valDown[q.b][0]+depth[q.a]});
			ret = min(ret,(n - 2 + q.w) * 2 - yeet);
		}
	}
	int oh = 0;
	for (int i : adj[cent]) if (!done[i]) {
		solve(i,togo[oh]);
		++oh;
	}
}
int main () {
	int m;
	scanf ("%d %d",&n,&m);
	vector<Edge> extra;
	while (m--) {
		int a,b,w;
		scanf ("%d %d %d",&a,&b,&w); ++a; ++b;
		if (w>1) extra.push_back({a,b,w});
		else adj[a].push_back(b), adj[b].push_back(a);
	}
	ret = solve(1);
	godown(1,0); dfs3(1); goup(1);
	prep(1); solve(1,extra);
	printf ("%d\n",ret);
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:177:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  177 |  scanf ("%d %d",&n,&m);
      |  ~~~~~~^~~~~~~~~~~~~~~
Main.cpp:181:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  181 |   scanf ("%d %d %d",&a,&b,&w); ++a; ++b;
      |   ~~~~~~^~~~~~~~~~~~~~~~~~~~~

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