제출 #547917

#제출 시각아이디문제언어결과실행 시간메모리
547917amunduzbaevMountains and Valleys (CCO20_day1problem3)C++17
1 / 25
7082 ms12880 KiB
#include "bits/stdc++.h" using namespace std; #define ar array const int N = 5e5 + 5; vector<int> edges[N]; signed main(){ ios::sync_with_stdio(0); cin.tie(0); int n, m; cin>>n>>m; vector<ar<int, 3>> e; int cnt = 0; for(int i=0;i<m;i++){ int a, b, c; cin>>a>>b>>c; a++, b++; if(c == 1){ edges[a].push_back(b); edges[b].push_back(a); cnt++; } else { e.push_back({a, b, c}); } } assert(cnt == n - 1); int res = 0; vector<int> d(n + 1); function<void(int, int)> dfs = [&](int u, int p){ for(auto x : edges[u]){ if(x == p) continue; d[x] = d[u] + 1; dfs(x, u); } }; int a = 1; d[a] = 0, dfs(a, a); for(int i=1;i<=n;i++){ if(d[i] > d[a]) a = i; } d[a] = 0, dfs(a, a); for(int i=1;i<=n;i++){ if(d[i] > d[a]) a = i; } res = 2 * n - 2 - d[a]; for(auto x : e){ int a = x[0], b = x[1], c = x[2]; vector<int> par(n + 1), used(n + 1), d(n + 1), rr(n + 1); function<void(int)> dfs = [&](int u){ for(auto x : edges[u]){ if(x == par[u]) continue; par[x] = u, dfs(x); } }; dfs(a); vector<int> tt; while(b){ used[b] = 1; tt.push_back(b); b = par[b]; } function<void(int)> dfs2 = [&](int u){ used[u] = 1; d[u] = rr[u] = 0; for(auto x : edges[u]){ if(used[x]) continue; dfs2(x); rr[u] = max(rr[u], rr[x]); if(d[u]) rr[u] = max(rr[u], d[u] + d[x] + 1); d[u] = max(d[u], d[x] + 1); } }; int mx = 0, cyc = tt.size(); for(auto x : tt){ dfs2(x); } for(int i=1;i<cyc;i++){ mx = max(mx, d[tt[i]] + d[tt[i-1]]); } int tot = (cyc - 1) + c; int ed = 2 * (n - 1 + c); res = min(res, ed - tot - mx - 1); for(int i=0;i<cyc;i++){ int sub = 0; res = min(res, ed - tot - rr[tt[i]]); for(int j=i+1;j<cyc;j++){ sub++; res = min(res, ed - max(sub, tot - sub) - d[tt[i]] - d[tt[j]]); } } } cout<<res<<"\n"; } /* 18 18 0 1 1 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 5 7 8 1 8 9 1 9 4 1 8 10 1 10 11 1 11 12 1 12 13 1 6 14 1 14 15 1 15 16 1 16 17 1 */
#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...