QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#817152#4408. 燃烧的呐球hhoppitree100 ✓7078ms871336kbC++1710.8kb2024-12-16 20:39:562024-12-16 20:39:56

Judging History

你现在查看的是最新测评结果

  • [2024-12-16 20:39:56]
  • 评测
  • 测评结果:100
  • 用时:7078ms
  • 内存:871336kb
  • [2024-12-16 20:39:56]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5, M = 1e5 + 5;

bool ST;

int n, m, fa[N], siz[N], dfn[N];
vector<int> G[N];

void preDfs(int x) {
    dfn[x] = ++dfn[0];
    for (auto v : G[x]) preDfs(v);
}

int ox[M], oy[M], wh[M];
vector<int> pnt[M];

int _fa[M];

int find(int x) {
    return (_fa[x] == x ? x : _fa[x] = find(_fa[x]));
}

struct B_Info {
    int val, pos;

    B_Info(int _val = 1e9, int _pos = 0) {
        val = _val, pos = _pos;
    }

    bool operator < (const B_Info y) const {
        return (val != y.val ? val < y.val : pos < y.pos);
    }

    B_Info operator + (int x) {
        return B_Info(val + x, pos);
    }
} mn[N];

struct Info {
    B_Info mn, sec;

    Info() {
        mn = sec = B_Info();
    }

    B_Info get(int x) {
        return (x != mn.pos ? mn : sec);
    }

    void operator += (B_Info y) {
        if (y.pos == mn.pos) {
            mn = min(mn, y);
        } else if (y < mn) {
            sec = mn, mn = y;
        } else {
            sec = min(sec, y);
        }
    }

    Info operator + (B_Info y) {
        Info z = *this;
        z += y;
        return z;
    }

    void operator += (Info y) {
        *this += y.mn;
        *this += y.sec;
    }

    Info operator + (Info y) {
        Info z = *this;
        z += y;
        return z;
    }
};

namespace Solver1 {
    vector<int> qr[N];
    vector<B_Info> md[N];

    Info dfs(int x) {
        Info now;
        for (auto v : md[x]) now += v;
        for (auto v : G[x]) {
            now += dfs(v);
        }
        for (auto v : qr[x]) {
            mn[wh[v]] = min(mn[wh[v]], now.get(wh[v]) + siz[ox[v]] + siz[oy[v]]);
        }
        return now;
    }

    void main() {
        for (int i = 1; i <= n; ++i) {
            qr[i].clear();
            md[i].clear();
        }
        for (int i = 1; i <= m; ++i) {
            qr[oy[i]].push_back(i);
            md[oy[i]].push_back(B_Info(siz[ox[i]] - siz[oy[i]], wh[i]));
        }
        dfs(1);
    }
}

namespace Solver2 {
    vector<int> qr[N];
    vector<B_Info> md[N];

    void dfs(int x, Info now) {
        for (auto v : md[x]) now += v;
        for (auto v : qr[x]) {
            mn[wh[v]] = min(mn[wh[v]], now.get(wh[v]) + (siz[ox[v]] - siz[oy[v]]));
        }
        for (auto v : G[x]) {
            dfs(v, now);
        }
    }

    void main() {
        for (int i = 1; i <= n; ++i) {
            qr[i].clear();
            md[i].clear();
        }
        for (int i = 1; i <= m; ++i) {
            qr[oy[i]].push_back(i);
            md[oy[i]].push_back(B_Info(siz[ox[i]] + siz[oy[i]], wh[i]));
        }
        dfs(1, Info());
    }
}

struct SegmentTree {
    struct Node {
        int l, r;
        Info dt;
    } p[M * 40];

    int tot;

    int newNode() {
        ++tot;
        p[tot].l = p[tot].r = 0;
        p[tot].dt = Info();
        return tot;
    }

    void modify(int &k, int l, int r, int x, B_Info y) {
        if (!k) k = newNode();
        p[k].dt += y;
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (x <= mid) modify(p[k].l, l, mid, x, y);
        else modify(p[k].r, mid + 1, r, x, y);
    }

    int merge(int l, int r, int x, int y) {
        if (!x || !y) return x + y;
        p[x].dt = p[x].dt + p[y].dt;
        if (l == r) return x;
        int mid = (l + r) >> 1;
        p[x].l = merge(l, mid, p[x].l, p[y].l);
        p[x].r = merge(mid + 1, r, p[x].r, p[y].r);
        return x;
    }

    Info query(int k, int l, int r, int x, int y) {
        if (!k) return Info();
        if (l >= x && r <= y) return p[k].dt;
        int mid = (l + r) >> 1;
        if (y <= mid) return query(p[k].l, l, mid, x, y);
        if (x > mid) return query(p[k].r, mid + 1, r, x, y);
        return query(p[k].l, l, mid, x, y) + query(p[k].r, mid + 1, r, x, y);
    }

    void Init() {
        tot = 0;
    }
};

namespace Solver3 {
    vector<int> qr[N];
    vector< pair<B_Info, int> > md[N];
    SegmentTree seg;

    int dfs(int x) {
        int now = 0;
        for (auto [v, w] : md[x]) {
            seg.modify(now, 1, n, w, v);
        }
        for (auto v : G[x]) {
            now = seg.merge(1, n, now, dfs(v));
        }
        for (auto v : qr[x]) {
            mn[wh[v]] = min(mn[wh[v]], seg.query(now, 1, n, dfn[ox[v]], dfn[ox[v]] + siz[ox[v]] - 1).get(wh[v]) + siz[ox[v]] + siz[oy[v]]);
        }
        return now;
    }

    void main() {
        for (int i = 1; i <= n; ++i) {
            qr[i].clear();
            md[i].clear();
        }
        for (int i = 1; i <= m; ++i) {
            qr[oy[i]].push_back(i);
            md[oy[i]].push_back({B_Info(-siz[ox[i]] - siz[oy[i]], wh[i]), dfn[ox[i]]});
        }
        seg.Init();
        dfs(1);
    }
}

struct PersistentSegmentTree {
    struct Node {
        int l, r;
        Info dt;
    } p[M * 40];

    int tot;

    int newNode() {
        ++tot;
        p[tot].l = p[tot].r = 0;
        p[tot].dt = Info();
        return tot;
    }

    int clone(int x) {
        int z = newNode();
        p[z] = p[x];
        return z;
    }

    void modify(int &k, int l, int r, int x, B_Info y) {
        k = clone(k);
        p[k].dt += y;
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (x <= mid) modify(p[k].l, l, mid, x, y);
        else modify(p[k].r, mid + 1, r, x, y);
    }

    Info query(int k, int l, int r, int x, int y) {
        if (!k) return Info();
        if (l >= x && r <= y) return p[k].dt;
        int mid = (l + r) >> 1;
        if (y <= mid) return query(p[k].l, l, mid, x, y);
        if (x > mid) return query(p[k].r, mid + 1, r, x, y);
        return query(p[k].l, l, mid, x, y) + query(p[k].r, mid + 1, r, x, y);
    }

    void Init() {
        tot = 0;
    }
};

namespace Solver4 {
    vector<int> qr[N];
    vector< pair<B_Info, int> > md[N];
    PersistentSegmentTree seg;

    void dfs(int x, int now) {
        for (auto [v, w] : md[x]) {
            seg.modify(now, 1, n, w, v);
        }
        for (auto v : qr[x]) {
            mn[wh[v]] = min(mn[wh[v]], seg.query(now, 1, n, dfn[ox[v]], dfn[ox[v]] + siz[ox[v]] - 1).get(wh[v]) + (siz[ox[v]] - siz[oy[v]]));
        }
        for (auto v : G[x]) {
            dfs(v, now);
        }
    }

    void main() {
        for (int i = 1; i <= n; ++i) {
            qr[i].clear();
            md[i].clear();
        }
        for (int i = 1; i <= m; ++i) {
            qr[oy[i]].push_back(i);
            md[oy[i]].push_back({B_Info(-siz[ox[i]] + siz[oy[i]], wh[i]), dfn[ox[i]]});
        }
        seg.Init();
        dfs(1, 0);
    }
}

struct PersistentSegmentTree2 {
    struct Node {
        int l, r;
        Info dt;
    } p[M * 40];

    int tot;

    int newNode() {
        ++tot;
        p[tot].l = p[tot].r = 0;
        p[tot].dt = Info();
        return tot;
    }

    int clone(int x) {
        int z = newNode();
        p[z] = p[x];
        return z;
    }

    void modify(int &k, int l, int r, int x, int y, B_Info v) {
        if (l > y || r < x) return;
        k = clone(k);
        if (l >= x && r <= y) {
            p[k].dt += v;
            return;
        }
        int mid = (l + r) >> 1;
        modify(p[k].l, l, mid, x, y, v);
        modify(p[k].r, mid + 1, r, x, y, v);
    }

    Info query(int k, int l, int r, int x) {
        if (!k) return Info();
        if (l == r) return p[k].dt;
        int mid = (l + r) >> 1;
        if (x <= mid) {
            return query(p[k].l, l, mid, x) + p[k].dt;
        }
        return query(p[k].r, mid + 1, r, x) + p[k].dt;
    }

    void Init() {
        tot = 0;
    }
};

namespace Solver5 {
    vector<int> qr[N];
    vector< pair<B_Info, pair<int, int> > > md[N];
    PersistentSegmentTree2 seg;

    void dfs(int x, int now) {
        for (auto [v, w] : md[x]) {
            seg.modify(now, 1, n, w.first, w.second, v);
        }
        for (auto v : qr[x]) {
            mn[wh[v]] = min(mn[wh[v]], seg.query(now, 1, n, dfn[ox[v]]).get(wh[v]) + (-siz[ox[v]] - siz[oy[v]]));
        }
        for (auto v : G[x]) {
            dfs(v, now);
        }
    }

    void main() {
        for (int i = 1; i <= n; ++i) {
            qr[i].clear();
            md[i].clear();
        }
        for (int i = 1; i <= m; ++i) {
            qr[oy[i]].push_back(i);
            md[oy[i]].push_back({B_Info(siz[ox[i]] + siz[oy[i]], wh[i]), {dfn[ox[i]], dfn[ox[i]] + siz[ox[i]] - 1}});
        }
        seg.Init();
        dfs(1, 0);
    }
}

void NN() {
    Info now;
    for (int i = 1; i <= m; ++i) {
        now += B_Info(siz[ox[i]] + siz[oy[i]], wh[i]);
    }
    for (int i = 1; i <= m; ++i) {
        mn[wh[i]] = min(mn[wh[i]], now.get(wh[i]) + siz[ox[i]] + siz[oy[i]]);
    }
}

void NA() {
    Solver1::main();
}

void ND() {
    Solver2::main();
}

void AN() {
    for (int i = 1; i <= m; ++i) swap(ox[i], oy[i]);
    NA();
    for (int i = 1; i <= m; ++i) swap(ox[i], oy[i]);
}

void AA() {
    Solver3::main();
}

void AD() {
    Solver4::main();
}

void DN() {
    for (int i = 1; i <= m; ++i) swap(ox[i], oy[i]);
    ND();
    for (int i = 1; i <= m; ++i) swap(ox[i], oy[i]);
}

void DA() {
    for (int i = 1; i <= m; ++i) swap(ox[i], oy[i]);
    AD();
    for (int i = 1; i <= m; ++i) swap(ox[i], oy[i]);
}

void DD() {
    Solver5::main();
}

bool ED;

signed main() {
    cerr << abs(&ED - &ST) / 1024.0 / 1024.0 << "MB" << endl;
    scanf("%d%d", &n, &m);
    for (int i = 2; i <= n; ++i) {
        scanf("%d", &fa[i]);
    }
    for (int i = n; i >= 1; --i) {
        ++siz[i];
        if (i != 1) {
            siz[fa[i]] += siz[i];
            G[fa[i]].push_back(i);
        }
    }
    preDfs(1);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &ox[i], &oy[i]);
        wh[i] = i;
        pnt[i].push_back(i);
    }
    long long res = 0;
    while (count(wh + 1, wh + m + 1, wh[1]) != m) {
        for (int i = 1; i <= m; ++i) mn[i] = B_Info();
        NN(), NA(), ND(), AN(), AA(), AD(), DN(), DA(), DD();
        map< pair<int, int>, int> E;
        for (int i = 1; i <= m; ++i) {
            if (pnt[i].empty()) continue;
            _fa[i] = i;
            int x = i, y = mn[i].pos;
            if (x > y) swap(x, y);
            E[{x, y}] = mn[i].val;
        }
        for (auto [x, y] : E) {
            auto [a, b] = x;
            a = find(a), b = find(b);
            if (a == b) continue;
            res += y;
            if (pnt[a].size() < pnt[b].size()) swap(a, b);
            for (auto v : pnt[b]) {
                pnt[a].push_back(v), wh[v] = a;
            }
            pnt[b].clear(), _fa[b] = a;
        }
    }
    printf("%lld\n", res);
    return 0;
}

Details

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 68ms
memory: 557948kb

Test #2:

score: 10
Accepted
time: 47ms
memory: 558544kb

Test #3:

score: 10
Accepted
time: 62ms
memory: 557776kb

Test #4:

score: 10
Accepted
time: 48ms
memory: 557352kb

Test #5:

score: 10
Accepted
time: 68ms
memory: 557704kb

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 10
Accepted
time: 3869ms
memory: 598868kb

Test #7:

score: 10
Accepted
time: 1880ms
memory: 596556kb

Test #8:

score: 10
Accepted
time: 979ms
memory: 590228kb

Test #9:

score: 10
Accepted
time: 1087ms
memory: 594652kb

Test #10:

score: 10
Accepted
time: 1471ms
memory: 594396kb

Subtask #3:

score: 10
Accepted

Dependency #2:

100%
Accepted

Test #11:

score: 10
Accepted
time: 5337ms
memory: 615504kb

Test #12:

score: 10
Accepted
time: 3052ms
memory: 613396kb

Test #13:

score: 10
Accepted
time: 1706ms
memory: 607548kb

Test #14:

score: 10
Accepted
time: 1875ms
memory: 611856kb

Test #15:

score: 10
Accepted
time: 2460ms
memory: 611296kb

Subtask #4:

score: 20
Accepted

Test #16:

score: 20
Accepted
time: 370ms
memory: 577904kb

Test #17:

score: 20
Accepted
time: 410ms
memory: 577588kb

Test #18:

score: 20
Accepted
time: 328ms
memory: 579220kb

Test #19:

score: 20
Accepted
time: 352ms
memory: 578084kb

Test #20:

score: 20
Accepted
time: 337ms
memory: 576824kb

Subtask #5:

score: 10
Accepted

Test #21:

score: 10
Accepted
time: 6803ms
memory: 871336kb

Test #22:

score: 10
Accepted
time: 6773ms
memory: 871280kb

Test #23:

score: 10
Accepted
time: 6886ms
memory: 871188kb

Test #24:

score: 10
Accepted
time: 6866ms
memory: 871156kb

Test #25:

score: 10
Accepted
time: 7078ms
memory: 871184kb

Subtask #6:

score: 10
Accepted

Test #26:

score: 10
Accepted
time: 1489ms
memory: 625868kb

Test #27:

score: 10
Accepted
time: 1516ms
memory: 625580kb

Test #28:

score: 10
Accepted
time: 1486ms
memory: 625576kb

Test #29:

score: 10
Accepted
time: 1449ms
memory: 625692kb

Test #30:

score: 10
Accepted
time: 1480ms
memory: 625444kb

Subtask #7:

score: 30
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Test #31:

score: 30
Accepted
time: 6699ms
memory: 641940kb

Test #32:

score: 30
Accepted
time: 3781ms
memory: 639828kb

Test #33:

score: 30
Accepted
time: 2392ms
memory: 634192kb

Test #34:

score: 30
Accepted
time: 2605ms
memory: 638660kb

Test #35:

score: 30
Accepted
time: 3183ms
memory: 637740kb

Test #36:

score: 30
Accepted
time: 6871ms
memory: 641772kb

Test #37:

score: 30
Accepted
time: 3883ms
memory: 639780kb

Test #38:

score: 30
Accepted
time: 2494ms
memory: 634020kb

Test #39:

score: 30
Accepted
time: 2659ms
memory: 638628kb

Test #40:

score: 30
Accepted
time: 3143ms
memory: 637764kb