Submission #330257

#	Time	Username	Problem	Language	Result	Execution time	Memory
330257		cki86201	Mountains and Valleys (CCO20_day1problem3)	C++17	25 / 25	4391 ms	201944 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define Fi first
#define Se second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)
typedef tuple<int, int, int> t3;

const int ADD = 1<<19, INF = 1e9;
struct node {
	int pv, mv, cv, val;
	void init(int x, int d, int d2) {
		pv = d + x, mv = d - x, cv = d2;
		val = -INF;
	}
	node operator+(const node &R) const {
		node res;
		res.pv = max(pv, R.pv);
		res.mv = max(mv, R.mv);
		res.cv = max(cv, R.cv);
		res.val = max({val, R.val, pv + R.mv});
		return res;
	}
} T[1<<20];
void init(int x, int d, int d2) {
	T[ADD+x].init(x, d, d2);
	for(int r=(ADD+x)/2;r;r>>=1) {
		T[r] = T[r*2] + T[r*2+1];
	}
}
int lvt[100], rvt[100];
node read(int l, int r) {
	if(l > r) {
		node res; res.init(0, -INF, -INF);
		return res;
	}
	l += ADD, r += ADD;
	int lt = 0, rt = 0;
	while(l <= r) {
		if(l & 1) lvt[lt++] = l++;
		if(!(r & 1)) rvt[rt++] = r--;
		l >>= 1, r >>= 1;
	}
	while(rt) lvt[lt++] = rvt[--rt];
	node res = T[lvt[0]];
	for(int i=1;i<lt;i++) res = res + T[lvt[i]];
	return res;
}

int N, M;
vector <int> E[500050];
vector <t3> AE;

int dis[500050], pre[500050];
int far(int x) {
	memset(dis, -1, sizeof dis);
	vector <int> q;
	auto ins_q = [&](int x, int d, int p) { if(dis[x] == -1) q.pb(x), dis[x] = d, pre[x] = p; };
	ins_q(x, 0, -1);
	rep(i, szz(q)) {
		int t = q[i];
		for(int e : E[t]) ins_q(e, dis[t] + 1, t);
	}
	return q.back();
}

int fd[500050], dep[500050], up[500050][20], mxd[500050], dv[500050];
vector <pii> chd[500050], dvl[500050];

int get_l(vector <pii> &h, int d, int e = -1) {
	int res = 0, rc = 0;
	for(auto &[l, y] : h) if(y != e) {
		++rc;
		res += l;
		if(rc == d) return res;
	}
	return res;
}

int DL[500050][2];

void pdfs(int x) {
	for(int e : E[x]) if(fd[e] == -1) {
		fd[e] = fd[x];
		dep[e] = dep[x] + 1;
		up[e][0] = x;
		for(int i=1;i<20;i++) up[e][i] = up[ up[e][i-1] ][i-1];
		pdfs(e);
		mxd[x] = max(mxd[x], mxd[e] + 1);
		dv[x] = max(dv[x], dv[e]);
		chd[x].pb({mxd[e]+1, e});
		dvl[x].pb({dv[e], e});
	}
	sort(all(chd[x]), greater<>());
	sort(all(dvl[x]), greater<>());
	dv[x] = max(dv[x], get_l(chd[x], 2, -1));
}

int get_lca(int x, int y) {
	if(dep[x] < dep[y]) swap(x, y);
	rep(i, 20) if(1<<i & (dep[x] - dep[y])) x = up[x][i];
	for(int i=19;i>=0;i--) if(up[x][i] != up[y][i]) x = up[x][i], y = up[y][i];
	return x == y ? x : up[x][0];
}
int climb(int x, int d) {
	rep(i, 20) if(1<<i & d) x = up[x][i];
	return x;
}

void qdfs(int x, int u = 0, int h = 0, int fa = -1) {
	DL[x][1] = max(dv[x], h);
	for(int e : E[x]) if(fd[e] == fd[x] && e != fa) {
		int du = 0, dh = max({h, get_l(dvl[x], 1, e), get_l(chd[x], 2, e)});
		if(fa != -1) du = max(u, get_l(chd[x], 1, e)) + 1;
		DL[e][0] = max(du, mxd[e]);
		qdfs(e, du, dh, x);
	}
}

int main() {
	scanf("%d%d", &N, &M);
	rep(i, M) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z); ++x; ++y;
		if(z == 1) {
			E[x].pb(y);
			E[y].pb(x);
		}
		else AE.pb({x, y, z});
	}
	int l = far(1);
	int r = far(l);
	int ans = 2 * (N - 1) - dis[r], lend = dis[r];
	vector <int> Dia;
	for(int t=r;t!=-1;t=pre[t]) Dia.pb(t);
	reverse(all(Dia));
	memset(fd, -1, sizeof fd);
	rep(i, szz(Dia)) fd[Dia[i]] = i;
	for(int e : Dia) pdfs(e);
	for(int e : Dia) DL[e][0] = -INF, qdfs(e);
	int m = szz(Dia);
	rep(i, m) init(i, mxd[Dia[i]], dv[Dia[i]]);
	for(auto [x, y, d] : AE) {
		if(fd[x] > fd[y]) swap(x, y);
		if(fd[x] == fd[y]) {
			int lca = get_lca(x, y);
			int c = dep[x] + dep[y] - 2 * dep[lca];
			ans = min(ans, 2 * N - 2 + d - c - lend);
		}
		else {
			int fx = fd[x], fy = fd[y], rx = Dia[fx], ry = Dia[fy];
			node n1 = read(0, fx-1), n2 = read(fx+1, fy-1), n3 = read(fy+1, m-1);
			int max_d2 = max({DL[x][1], DL[y][1], n1.pv, n2.cv, n3.mv+(m-1)});
			int cx = (dep[x] ? climb(x, dep[x]-1) : -1);
			int cy = (dep[y] ? climb(y, dep[y]-1) : -1);
			max_d2 = max({max_d2, fx + get_l(chd[rx], 1, cx), m-1-fy + get_l(chd[ry], 1, cy)});
			int c = fy - fx + dep[x] + dep[y];
			ans = min(ans, 2 * N - 2 + d - c - max_d2);

			int max_d1 = max(DL[x][0] + max(fy, m-1-fy) + dep[y], DL[y][0] + max(fx, m-1-fx) + dep[x]);
			max_d1 = max(max_d1, fx + dep[x] + (m-1-fy) + dep[y]);
			max_d1 = max(max_d1, fx + dep[x] + n2.mv + fy + dep[y]);
			max_d1 = max(max_d1, dep[x] + n2.pv - fx + (m-1-fy) + dep[y]);
			max_d1 = max(max_d1, n2.val + fy - fx + dep[x] + dep[y]);
			ans = min(ans, 2 * N - 4 + d - max_d1);
		}
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  127 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  130 |   scanf("%d%d%d", &x, &y, &z); ++x; ++y;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• 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: 4 / 4