Submission #525730

#	Time	Username	Problem	Language	Result	Execution time	Memory
525730		qwerasdfzxcl	Mountains and Valleys (CCO20_day1problem3)	C++14	25 / 25	6946 ms	366016 KiB

Main

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct Query{
    int x, y, z;
    Query(){}
    Query(int _x, int _y, int _z): x(_x), y(_y), z(_z) {}
};
vector<int> adj[500500];
vector<Query> E;
int n;

inline void _insert(pair<int, int> *arr, int sz, int x, int y){
    if (arr[sz-1].first>=x) return;
    arr[sz-1] = {x, y};
    for (int i=sz-2;i>=0;i--) if (arr[i].first < arr[i+1].first) swap(arr[i], arr[i+1]);
}

int dep[500500], par[500500], dp_D[500500], dp_far[500500], D[500500], deep[500500];
void dfs_dp1(int s, int pa = -1){
    //printf(" %d", s);
    par[s] = pa;

    pair<int, int> Drr[3], Frr[3];
    for (int i=0;i<3;i++) {Drr[i] = Frr[i] = {0, -1};}

    for (auto &v:adj[s]) if (v!=pa){
        dep[v] = dep[s]+1;
        dfs_dp1(v, s);

        dp_D[s] = max(dp_D[s], dp_D[v]);
        dp_far[s] = max(dp_far[s], dp_far[v]+1);

        _insert(Drr, 3, dp_D[v], v);
        _insert(Frr, 3, dp_far[v]+1, v);
    }


    dp_D[s] = max(dp_D[s], Frr[0].first + Frr[1].first);

    ///calc D, deep
    for (auto &v:adj[s]) if (v!=pa){
        if (v==Drr[0].second) D[v] = Drr[1].first;
        else D[v] = Drr[0].first;

        if (v==Frr[0].second){
            D[v] = max(D[v], Frr[1].first + Frr[2].first);
            deep[v] = Frr[1].first;
        }
        else if (v==Frr[1].second){
            D[v] = max(D[v], Frr[0].first + Frr[2].first);
            deep[v] = Frr[0].first;
        }
        else{
            D[v] = max(D[v], Frr[0].first + Frr[1].first);
            deep[v] = Frr[0].first;
        }
    }
}

pair<int, int> Dc[500500][4], Fc[500500][4];
int dp_parD[500500], dp_parF[500500];

void dfs_dp2(int s, int pa = -1){
    for (int i=0;i<4;i++) {Dc[s][i] = Fc[s][i] = {0, -1};}

    if (pa!=-1){
        _insert(Dc[s], 4, dp_parD[s], pa);
        _insert(Fc[s], 4, dp_parF[s]+1, pa);
    }

    for (auto &v:adj[s]) if (v!=pa){
        _insert(Dc[s], 4, dp_D[v], v);
        _insert(Fc[s], 4, dp_far[v]+1, v);
    }

    ///calc dp_par
    for (auto &v:adj[s]) if (v!=pa){
        if (v==Dc[s][0].second) dp_parD[v] = Dc[s][1].first;
        else dp_parD[v] = Dc[s][0].first;

        if (v==Fc[s][0].second){
            dp_parD[v] = max(dp_parD[v], Fc[s][1].first + Fc[s][2].first);
            dp_parF[v] = Fc[s][1].first;
        }
        else if (v==Fc[s][1].second){
            dp_parD[v] = max(dp_parD[v], Fc[s][0].first + Fc[s][2].first);
            dp_parF[v] = Fc[s][0].first;
        }
        else{
            dp_parD[v] = max(dp_parD[v], Fc[s][0].first + Fc[s][1].first);
            dp_parF[v] = Fc[s][0].first;
        }
    }

    for (auto &v:adj[s]) if (v!=pa) dfs_dp2(v, s);
}

struct Node{
    int ans, a, b;
    Node(){}
    Node(int _ans, int _a, int _b): ans(_ans), a(_a), b(_b) {}
    Node operator +(const Node &R) const{
        return Node(max(max(ans, R.ans), a+R.b), max(a, R.a), max(b, R.b));
    }
};
pair<int, int> sp1[500500][20];
Node sp2[500500][20];

void build(int n){
    for (int i=0;i<n;i++){
        sp1[i][0] = {D[i], par[i]};
        sp2[i][0] = Node(-1e9, deep[i]-(dep[i]-1), deep[i]+(dep[i]-1));
    }

    for (int j=1;j<20;j++){
        for (int i=0;i<n;i++) if (dep[i]>=(1<<j)){
            int tmp = sp1[i][j-1].second;

            sp1[i][j].first = max(sp1[i][j-1].first, sp1[tmp][j-1].first);
            sp1[i][j].second = sp1[tmp][j-1].second;
            sp2[i][j] = sp2[i][j-1] + sp2[tmp][j-1];
        }
    }
}

int prV, prW;
int get_lca(int v, int w){
    if (dep[v]<dep[w]) swap(v, w);

    if(dep[v]!=dep[w]){
        int dist = dep[v] - dep[w] - 1;
        for (int j=0;dist>0;j++) if (dist&(1<<j)){
            v = sp1[v][j].second;
            dist -= 1<<j;
        }
    }
    prV = v, prW = w;
    if (dep[v]!=dep[w]) v = sp1[v][0].second;

    if (v==w) return v;

    for (int j=19;j>=0;j--) if (sp1[v][j].second!=sp1[w][j].second){
        v = sp1[v][j].second;
        w = sp1[w][j].second;
    }
    prV = v, prW = w;
    return sp1[v][0].second;
}

int calc1(int x, int y, int w){
    int lca = get_lca(x, y);
    int ret = 0;

    if (x!=lca) ret = max(ret, dp_D[x]);
    if (y!=lca) ret = max(ret, dp_D[y]);

    int rdist = dep[x] + dep[y] - dep[lca]*2;

    int dist = dep[x] - dep[lca] - 1;
    for (int j=0;dist>0;j++) if (dist&(1<<j)){
        ret = max(ret, sp1[x][j].first);
        x = sp1[x][j].second;
        dist -= 1<<j;
    }

    dist = dep[y] - dep[lca] - 1;
    for (int j=0;dist>0;j++) if (dist&(1<<j)){
        ret = max(ret, sp1[y][j].first);
        y = sp1[y][j].second;
        dist -= 1<<j;
    }

    int S = 0, cnt = 0;
    for (int i=0;i<4;i++) if (Dc[lca][i].second!=x && Dc[lca][i].second!=y) ret = max(ret, Dc[lca][i].first);
    for (int i=0;i<4;i++) if (Fc[lca][i].second!=x && Fc[lca][i].second!=y){
        S += Fc[lca][i].first;
        cnt++;
        if (cnt==2) break;
    }
    ret = max(ret, S);

    return (n-1+w)*2 - ret - rdist - w;
}

int calc2(int x, int y, int w){
    int lca = get_lca(x, y);
    int ret = -1e9, rdist = dep[x] + dep[y] - dep[lca]*2;

    int val = -1;
    for (int i=0;i<4;i++) if (Fc[lca][i].second!=prV && Fc[lca][i].second!=prW) {val = Fc[lca][i].first; break;}
    assert(val!=-1);

    ///left chain
    int tx = x, ty = y;
    Node cur(-1e9, dp_far[tx] - dep[tx], dp_far[tx] + dep[tx]);
    Node Top(-1e9, val - dep[lca], val + dep[lca]);

    int dist = dep[tx] - dep[lca] - 1;
    for (int j=0;dist>0;j++) if (dist&(1<<j)){
        cur = cur + sp2[tx][j];
        tx = sp1[tx][j].second;
        dist -= 1<<j;
    }

    if (tx!=lca) cur = cur + Top;
    ret = max(ret, cur.ans);

    ///right chain
    cur = Node(-1e9, dp_far[ty] - dep[ty], dp_far[ty] + dep[ty]);
    dist = dep[ty] - dep[lca] - 1;
    for (int j=0;dist>0;j++) if (dist&(1<<j)){
        cur = cur + sp2[ty][j];
        ty = sp1[ty][j].second;
        dist -= 1<<j;
    }

    if (ty!=lca) cur = cur + Top;
    ret = max(ret, cur.ans);

    ///left and right
    if (x==lca || y==lca) return (n-2+w) * 2 - (rdist+w+ret);

    int L = dp_far[x] - dep[x], R = dp_far[y] - dep[y];
    tx = x, ty = y;

    dist = dep[tx] - dep[lca] - 1;
    for (int j=0;dist>0;j++) if (dist&(1<<j)){
        L = max(L, sp2[tx][j].a);
        tx = sp1[tx][j].second;
        dist -= 1<<j;
    }

    dist = dep[ty] - dep[lca] - 1;
    for (int j=0;dist>0;j++) if (dist&(1<<j)){
        R = max(R, sp2[ty][j].a);
        ty = sp1[ty][j].second;
        dist -= 1<<j;
    }

    ret = max(ret, L+R + dep[lca]*2);

    return (n-2+w) * 2 - (rdist+w+ret);
}

void Debug(){
    printf("dep: ");
    for (int i=0;i<n;i++) printf("%d ", dep[i]);
    printf("\npar: ");
    for (int i=0;i<n;i++) printf("%d ", par[i]);
    printf("\ndp_D: ");
    for (int i=0;i<n;i++) printf("%d ", dp_D[i]);
    printf("\ndp_far: ");
    for (int i=0;i<n;i++) printf("%d ", dp_far[i]);
    printf("\nD: ");
    for (int i=0;i<n;i++) printf("%d ", D[i]);
    printf("\ndeep: ");
    for (int i=0;i<n;i++) printf("%d ", deep[i]);
    printf("\ndp_parD: ");
    for (int i=0;i<n;i++) printf("%d ", dp_parD[i]);
    printf("\ndp_parF: ");
    for (int i=0;i<n;i++) printf("%d ", dp_parF[i]);
    printf("\n");
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int m;
    cin >> n >> m;
    for (int i=1;i<=m;i++){
        int x, y, z;
        cin >> x >> y >> z;
        if (z!=1) {E.emplace_back(x, y, z); continue;}

        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    dfs_dp1(0);
    dfs_dp2(0);

    //if (n>80000) exit(0);

    //Debug();

    build(n);

    //if (n>80000) exit(0);

    int ans = (n-1)*2 - dp_D[0];

    for (auto &e:E){
        ans = min(ans, calc1(e.x, e.y, e.z));
        ans = min(ans, calc2(e.x, e.y, e.z));
    }

    printf("%d\n", ans);
    return 0;
}

• 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