oj.uz

답안 #835299

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
835299 2023-08-23T12:03:52 Z Josia Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 4385 ms 285256 KB 
#include <bits/stdc++.h>

using namespace std;

#define int int64_t


struct seg {
    int n;
    vector<int> tree;
    vector<int> lazy;

    void push(int v) {
        tree[v*2] += lazy[v];
        tree[v*2+1] += lazy[v];

        lazy[v*2] += lazy[v];
        lazy[v*2+1] += lazy[v];

        lazy[v] = 0;
    }

    int query(int v, int rl, int rr, int ql, int qr) {
        if (ql > qr) {
            return 0;
        }
        if (ql == rl && qr == rr) return tree[v];

        push(v);

        int rm = (rl + rr) / 2;

        return max(query(v*2, rl, rm, ql, min(rm, qr)), query(v*2+1, rm+1, rr, max(rm+1, ql), qr));
    }

    void update(int v, int rl, int rr, int ql, int qr, int x) {
        if (ql > qr) {
            return;
        }
        if (ql == rl && qr == rr) {
            tree[v] += x;
            lazy[v] += x;
            return;
        }

        push(v);

        int rm = (rl + rr) / 2;

        update(v*2, rl, rm, ql, min(rm, qr), x);
        update(v*2+1, rm+1, rr, max(rm+1, ql), qr, x);

        tree[v] = max(tree[v*2], tree[v*2+1]);
    }

    void init(int _n, vector<int> a) {
        n = _n;
        tree.assign(n*4, 0);
        lazy.assign(n*4, 0);

        for (int i = 0; i<n; i++) {
            update(1, 0, n-1, i, i, a[i]);
        }
    }
};


vector<vector<int>> graph;
unordered_map<int, int> weight;

array<array<int, 100005>, 20> parent;
array<array<int, 100005>, 20> Size;
array<array<int, 100005>, 20> whichSubtree;
array<array<pair<int, int>, 100005>, 20> prepost;


vector<int> centroidLevel;

struct tree {
    int level;
    int currCol = 0;

    seg segtree;

    vector<int> order;
    vector<int> verticies;
    vector<int> children;
    int dfs(int v, int p, int forbidden, int d) {
        verticies.push_back(v);
        prepost[level][v].first = order.size();
        order.push_back(d);
        parent[level][v] = p;

        if (p!=-1) whichSubtree[level][v] = currCol;

        int s = 1;

        for (int i: graph[v]) {
            if (i == p || centroidLevel[i]!=-1) continue;
            s += dfs(i, v, forbidden, d+weight[i+v*100005]);
            if (p==-1) {
                children.push_back(i);
                currCol++;
            }
        }
        Size[level][v] = s;
        prepost[level][v].second = order.size()-1;
        return s;
    }


    bool isCentroid(int v, int p, int forbidden) {
        int s = 1;
        for (int i: graph[v]) {
            if (i == p || centroidLevel[i]!=-1) continue;
            if (Size[level][i] > (int)verticies.size()/2) return 0;
            s += Size[level][i];
        }
        return (int)verticies.size()-s <= (int)verticies.size()/2;
    }

    int findCentroid(int v, int p, int forbidden) {
        if (isCentroid(v, p, forbidden)) return v;

        int biggest=0;
        int indBiggest=-1;
        for (int i: graph[v]) {
            if (i == p || centroidLevel[i]!=-1) continue;
            if (Size[level][i] > biggest) {
                biggest = Size[level][i];
                indBiggest = i;
            }
        }

        assert(indBiggest!=-1);
        return findCentroid(indBiggest, v, forbidden);
    }



    bool isParent(int p, int v) {
        return (parent[level][v] == p);
    }


    set<pair<int, int>> bestInChild;


    void updateEdge(int u, int v, int x) {
        // if (verticies.count(u)==0 || verticies.count(v)==0) return;
        if (!isParent(u, v)) swap(u, v);

        int child = whichSubtree[level][v];

        pair<int, int> rangeChild = prepost[level][children[child]];
        bestInChild.erase({segtree.query(1, 0, segtree.n-1, rangeChild.first, rangeChild.second), child});

        pair<int, int> rangeUpdate = prepost[level][v];
        segtree.update(1, 0, segtree.n-1, rangeUpdate.first, rangeUpdate.second, x);

        bestInChild.insert({segtree.query(1, 0, segtree.n-1, rangeChild.first, rangeChild.second), child});
    }

    int getDiam() {
        if (bestInChild.empty()) return 0;
        if (bestInChild.size()==1) return (*bestInChild.rbegin()).first;
        return (*bestInChild.rbegin()).first + (*next(bestInChild.rbegin())).first;
    }

    pair<int, vector<int>> init(int v, int _level, int forbidden) {
        level = _level;
        currCol = 0;
        order.clear();

        dfs(v, -1, forbidden, 0);

        int centroid = findCentroid(v, -1, forbidden);

        currCol = 0;
        order.clear();
        verticies.clear();
        children.clear();
        dfs(centroid, -1, forbidden, 0);

        // for (int i: order) cerr << i << " ";
        // cerr << "\n";

        segtree.init(order.size(), order);

        for (int i = 0; i<(int)children.size(); i++) {
            auto range = prepost[level][children[i]];
            bestInChild.insert({segtree.query(1, 0, segtree.n-1, range.first, range.second), i});
        }

        return {centroid, children};
    }
};




int N, Q, W;




vector<tree> trees;
vector<vector<int>> inTrees;

set<pair<int, int>> allDiams;   // len, treeInd

void makeTrees() {
    queue<array<int, 3>> q;     // centroid, level, parent;

    q.push({0, 0, -1});

    while (q.size()) {
        tree x;
        auto newComps = x.init(q.front()[0], q.front()[1], q.front()[2]);

        centroidLevel[newComps.first] = q.front()[1];

        for (int i: newComps.second) {
            q.push({i, q.front()[1]+1, newComps.first});
        }
        q.pop();

        for (int i: x.verticies) inTrees[i].push_back(trees.size());
        allDiams.insert({x.getDiam(), trees.size()});

        trees.push_back(x);
    }
}

void updateEdge(int u, int v, int x) {

    int p1 = 0;
    int p2 = 0;

    while (p1<(int)inTrees[u].size() && p2<(int)inTrees[v].size()) {
        if (inTrees[u][p1] == inTrees[v][p2]) {
            allDiams.erase({trees[inTrees[u][p1]].getDiam(), inTrees[u][p1]});
            trees[inTrees[u][p1]].updateEdge(u, v, x);
            allDiams.insert({trees[inTrees[u][p1]].getDiam(), inTrees[u][p1]});
            p1++;
            p2++;
            continue;
        }
        if (inTrees[u][p1] < inTrees[v][p2]) {
            p1++;
            continue;
        }
        p2++;
    }

}


int queryBest() {
    return (*allDiams.rbegin()).first;
}


signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin >> N >> Q >> W;

    graph.resize(N);
    inTrees.resize(N);
    centroidLevel.assign(N, -1);

    vector<array<int,3>> edges(N-1);

    for (int i = 0; i<N-1; i++) {
        int a, b, c; cin >> a >> b >> c; a--; b--;
        edges[i] = {a, b, c};
        graph[a].push_back(b);
        graph[b].push_back(a);

        weight[a+b*100005] = c;
        weight[b+a*100005] = c;
    }

    makeTrees();

    // for (auto i: edges) {
    //     updateEdge(i[0], i[1], i[2]);
    // }

    int last = 0;
    for (int i = 0; i<Q; i++) {
        int _d, _e; cin >> _d >> _e;

        int d = (_d+last)%(N-1);
        int e = (_e+last)%(W);

        int diff = e-edges[d][2];

        updateEdge(edges[d][0], edges[d][1], diff);

        edges[d][2] = e;

        last = queryBest();
        cout << last << "\n";
    }


    return 0;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 19 ms 2064 KB Output is correct
20 Correct 20 ms 2132 KB Output is correct
21 Correct 24 ms 2260 KB Output is correct
22 Correct 25 ms 2516 KB Output is correct
23 Correct 38 ms 8524 KB Output is correct
24 Correct 50 ms 9932 KB Output is correct
25 Correct 55 ms 10796 KB Output is correct
26 Correct 54 ms 12108 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 11 ms 468 KB Output is correct
5 Correct 51 ms 744 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 16 ms 852 KB Output is correct
11 Correct 76 ms 1228 KB Output is correct
12 Correct 8 ms 5068 KB Output is correct
13 Correct 9 ms 5068 KB Output is correct
14 Correct 10 ms 5068 KB Output is correct
15 Correct 36 ms 5088 KB Output is correct
16 Correct 125 ms 5068 KB Output is correct
17 Correct 216 ms 87048 KB Output is correct
18 Correct 261 ms 86872 KB Output is correct
19 Correct 218 ms 86880 KB Output is correct
20 Correct 260 ms 87144 KB Output is correct
21 Correct 470 ms 87540 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2132 KB Output is correct
2 Correct 28 ms 2260 KB Output is correct
3 Correct 124 ms 2476 KB Output is correct
4 Correct 250 ms 2660 KB Output is correct
5 Correct 45 ms 22100 KB Output is correct
6 Correct 91 ms 22100 KB Output is correct
7 Correct 257 ms 21964 KB Output is correct
8 Correct 538 ms 22096 KB Output is correct
9 Correct 269 ms 118140 KB Output is correct
10 Correct 331 ms 118140 KB Output is correct
11 Correct 683 ms 118392 KB Output is correct
12 Correct 1116 ms 118788 KB Output is correct
13 Correct 644 ms 247136 KB Output is correct
14 Correct 714 ms 247268 KB Output is correct
15 Correct 1156 ms 247512 KB Output is correct
16 Correct 1695 ms 247712 KB Output is correct
17 Correct 3205 ms 247796 KB Output is correct

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2878 ms 218476 KB Output is correct
2 Correct 2943 ms 223236 KB Output is correct
3 Correct 2949 ms 219684 KB Output is correct
4 Correct 2946 ms 224252 KB Output is correct
5 Correct 2958 ms 215316 KB Output is correct
6 Correct 2429 ms 183844 KB Output is correct
7 Correct 3656 ms 260704 KB Output is correct
8 Correct 3736 ms 260576 KB Output is correct
9 Correct 3703 ms 260728 KB Output is correct
10 Correct 3646 ms 260128 KB Output is correct
11 Correct 3670 ms 252460 KB Output is correct
12 Correct 3187 ms 207168 KB Output is correct
13 Correct 3998 ms 281236 KB Output is correct
14 Correct 3736 ms 281148 KB Output is correct
15 Correct 4181 ms 281176 KB Output is correct
16 Correct 4178 ms 280416 KB Output is correct
17 Correct 3904 ms 274388 KB Output is correct
18 Correct 3157 ms 218368 KB Output is correct
19 Correct 3935 ms 285184 KB Output is correct
20 Correct 3914 ms 285244 KB Output is correct
21 Correct 4000 ms 285256 KB Output is correct
22 Correct 3864 ms 284360 KB Output is correct
23 Correct 4013 ms 274308 KB Output is correct
24 Correct 3372 ms 218352 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 19 ms 2064 KB Output is correct
20 Correct 20 ms 2132 KB Output is correct
21 Correct 24 ms 2260 KB Output is correct
22 Correct 25 ms 2516 KB Output is correct
23 Correct 38 ms 8524 KB Output is correct
24 Correct 50 ms 9932 KB Output is correct
25 Correct 55 ms 10796 KB Output is correct
26 Correct 54 ms 12108 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 11 ms 468 KB Output is correct
31 Correct 51 ms 744 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 724 KB Output is correct
34 Correct 1 ms 852 KB Output is correct
35 Correct 3 ms 724 KB Output is correct
36 Correct 16 ms 852 KB Output is correct
37 Correct 76 ms 1228 KB Output is correct
38 Correct 8 ms 5068 KB Output is correct
39 Correct 9 ms 5068 KB Output is correct
40 Correct 10 ms 5068 KB Output is correct
41 Correct 36 ms 5088 KB Output is correct
42 Correct 125 ms 5068 KB Output is correct
43 Correct 216 ms 87048 KB Output is correct
44 Correct 261 ms 86872 KB Output is correct
45 Correct 218 ms 86880 KB Output is correct
46 Correct 260 ms 87144 KB Output is correct
47 Correct 470 ms 87540 KB Output is correct
48 Correct 6 ms 2132 KB Output is correct
49 Correct 28 ms 2260 KB Output is correct
50 Correct 124 ms 2476 KB Output is correct
51 Correct 250 ms 2660 KB Output is correct
52 Correct 45 ms 22100 KB Output is correct
53 Correct 91 ms 22100 KB Output is correct
54 Correct 257 ms 21964 KB Output is correct
55 Correct 538 ms 22096 KB Output is correct
56 Correct 269 ms 118140 KB Output is correct
57 Correct 331 ms 118140 KB Output is correct
58 Correct 683 ms 118392 KB Output is correct
59 Correct 1116 ms 118788 KB Output is correct
60 Correct 644 ms 247136 KB Output is correct
61 Correct 714 ms 247268 KB Output is correct
62 Correct 1156 ms 247512 KB Output is correct
63 Correct 1695 ms 247712 KB Output is correct
64 Correct 3205 ms 247796 KB Output is correct
65 Correct 2878 ms 218476 KB Output is correct
66 Correct 2943 ms 223236 KB Output is correct
67 Correct 2949 ms 219684 KB Output is correct
68 Correct 2946 ms 224252 KB Output is correct
69 Correct 2958 ms 215316 KB Output is correct
70 Correct 2429 ms 183844 KB Output is correct
71 Correct 3656 ms 260704 KB Output is correct
72 Correct 3736 ms 260576 KB Output is correct
73 Correct 3703 ms 260728 KB Output is correct
74 Correct 3646 ms 260128 KB Output is correct
75 Correct 3670 ms 252460 KB Output is correct
76 Correct 3187 ms 207168 KB Output is correct
77 Correct 3998 ms 281236 KB Output is correct
78 Correct 3736 ms 281148 KB Output is correct
79 Correct 4181 ms 281176 KB Output is correct
80 Correct 4178 ms 280416 KB Output is correct
81 Correct 3904 ms 274388 KB Output is correct
82 Correct 3157 ms 218368 KB Output is correct
83 Correct 3935 ms 285184 KB Output is correct
84 Correct 3914 ms 285244 KB Output is correct
85 Correct 4000 ms 285256 KB Output is correct
86 Correct 3864 ms 284360 KB Output is correct
87 Correct 4013 ms 274308 KB Output is correct
88 Correct 3372 ms 218352 KB Output is correct
89 Correct 3130 ms 224476 KB Output is correct
90 Correct 3513 ms 241956 KB Output is correct
91 Correct 3972 ms 258580 KB Output is correct
92 Correct 4385 ms 262748 KB Output is correct
93 Correct 4048 ms 271308 KB Output is correct
94 Correct 3986 ms 273148 KB Output is correct
95 Correct 3786 ms 280796 KB Output is correct
96 Correct 3845 ms 278912 KB Output is correct
97 Correct 3748 ms 280504 KB Output is correct
98 Correct 3827 ms 284320 KB Output is correct
99 Correct 3873 ms 280116 KB Output is correct
100 Correct 3848 ms 280040 KB Output is correct