Submission #330241

#TimeUsernameProblemLanguageResultExecution timeMemory
330241cki86201Mountains and Valleys (CCO20_day1problem3)C++17
21 / 25
4309 ms205560 KiB
#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); 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);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...