| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 525868 | koioi.org-koosaga | Mountains and Valleys (CCO20_day1problem3) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
vector<int> ord;
int din[MAXN], dout[MAXN], piv;
int f[20][MAXN], far[MAXN], diam[MAXN], pfar[MAXN];
vector<pi> fars[MAXN];
vector<pi> subDiams[MAXN];
int fPathMax(int x, int v){
int ans = -1e9;
for(int i = 0; v; i++){
if(v & 1){
ans = max(ans, f[i][x]);
x = par[i][x];
}
v >>= 1;
}
return ans;
}
bool in(int u, int v){
return din[u] <= din[v] && dout[v] <= dout[u];
}
void dfs(int x, int p = -1){
ord.push_back(x);
din[x] = ++piv;
for(auto &y : gph[x]){
if(y == p) continue;
par[0][y] = x;
dep[y] = dep[x] + 1;
dfs(y, x);
}
dout[x] = piv;
}
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]];
}
}
{
// TODO: n^2
for(int i = 0; i < n; i++){
if(dep[i] >= 2){
vis[i] = 1;
vis[par[1][i]] = 1;
auto x = dfsl(par[0][i]);
g[i] = x.first;
f[0][i] = dfsl(x.second).first;
vis[i] = 0;
vis[par[1][i]] = 0;
}
}
// TODO: n^2
for(int i = 0; i < n; i++){
vis[i] = 1;
for(auto &j : gph[i]){
subDiams[i].emplace_back(dfsl(dfsl(j).second).first, j);
}
sort(all(subDiams[i]));
reverse(all(subDiams[i]));
vis[i] = 0;
}
for(int i = 1; i < 20; i++){
for(int j = 0; j < n; j++){
f[i][j] = max(f[i-1][j], f[i-1][par[i-1][j]]);
}
}
reverse(all(ord));
for(auto &i : ord){
for(auto &j : gph[i]){
if(j == par[0][i]) continue;
far[i] = max(far[i], far[j] + 1);
diam[i] = max({diam[i], diam[j], far[j] + 1});
fars[i].emplace_back(far[j], j);
}
sort(all(fars[i]));
reverse(all(fars[i]));
if(sz(fars[i]) >= 2) diam[i] = max(diam[i], (int)fars[i][0].first + (int)fars[i][1].first + 2);
}
reverse(all(ord));
for(auto &i : ord){
if(i == 0) continue;
for(auto &j : fars[par[0][i]]){
if(j.second == i) continue;
pfar[i] = j.first + 1;
break;
}
fars[i].emplace_back(pfar[i], par[0][i]);
sort(all(fars[i]));
reverse(all(fars[i]));
}
}
int ans = 2 * n - 2 - diam[0];
for(auto &x : qry){
int l = lca(x.s, x.e);
int plen = dep[x.s] + dep[x.e] - 2 * dep[l] + 1;
int maxPath = -1e9;
if(dep[x.s] >= dep[l] + 2){
maxPath = max(maxPath, fPathMax(x.s, dep[x.s] - dep[l] - 1) - 3 + plen);
}
if(dep[x.e] >= dep[l] + 2){
maxPath = max(maxPath, fPathMax(x.e, dep[x.e] - dep[l] - 1) - 3 + plen);
}
if(l != x.s){
maxPath = max(maxPath, diam[x.s] - 3 + sz(v));
}
if(l != x.e){
maxPath = max(maxPath, diam[x.e] - 3 + sz(v));
}
{
int new_diam = 0;
int cnt = 0;
// passes through l
for(auto &[d, v] : fars[l]){
if((in(v, x.s) || in(v, x.e)) && v != par[0][l]) continue;
new_diam += d + 1;
cnt += 1;
if(cnt == 2) break;
}
for(auto &[d, v] : subDiams[l]){
if((in(v, x.s) || in(v, x.e)) && v != par[0][l]) continue;
new_diam = max(new_diam, (int)d);
break;
}
maxPath = max(maxPath, new_diam - 3 + sz(v));
}
// TODO: qn.
vector<int> valup, valdown;
if(v.s != l) valup.push_back(far[v.s]);
if(v.e != l) valdown.push_back(far[v.e]);
for(int i = x.s; dep[i] >= dep[l] + 2; i = par[0][i]) valup.push_back(g[i]);
for(int i = x.e; dep[i] >= dep[l] + 2; i = par[0][i]) valdown.push_back(g[i]);
{
int dist = 0;
for(auto &[d, v] : fars[l]){
if((in(v, x.s) || in(v, x.e)) && v != par[0][l]) continue;
dist = max(dist, d + 1);
break;
}
valup.push_back(dist);
}
{
reverse(all(valdown));
for(auto &i : valup) val.push_back(i);
for(auto &i : valdown) val.push_back(i);
}
int pmax = -1e9;
for(int i = 0; i < sz(val); i++){
maxPath = max(maxPath, sz(val) - 1 - i + val[i] + pmax);
pmax = max(pmax, i + val[i]);
}
ans = min(ans, 2 * n - 4 + x.x - maxPath);
}
cout << ans << endl;
}