oj.uz

답안 #446283

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
446283 2021-07-21T13:06:47 Z qwerasdfzxcl Dynamic Diameter (CEOI19_diameter) C++14
100 / 100
 2977 ms 270928 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long

using namespace std;
struct Node{
    int x, y, w, nxt;
    Node(){}
    Node(int _x, int _y, int _w, int _nxt):x(_x), y(_y), w(_w), nxt(_nxt){}
};
Node combine(Node x, Node y){
    if (x.w>=y.w) return x;
    return y;
}
struct Seg{
    vector<Node> tree;
    vector<int> lazy;
    int sz;
    void make_tree(int n){
        sz = n;
        tree.resize(sz*4+4);
        lazy.resize(sz*4+4, 0);
    }
    void init(int i, int l, int r, vector<Node> &vec){
        if (l==r){
            tree[i] = vec[l];
            return;
        }
        int m = (l+r)>>1;
        init(i<<1, l, m, vec); init(i<<1|1, m+1, r, vec);
        tree[i] = combine(tree[i<<1], tree[i<<1|1]);
    }
    void propagate(int i, int l, int r){
        tree[i].w += lazy[i];
        if (l!=r){
            lazy[i<<1] += lazy[i];
            lazy[i<<1|1] += lazy[i];
        }
        lazy[i] = 0;
    }
    void update(int i, int l, int r, int s, int e, int val){
        propagate(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            lazy[i] += val; propagate(i, l, r); return;
        }
        int m = (l+r)>>1;
        update(i<<1, l, m, s, e, val); update(i<<1|1, m+1, r, s, e, val);
        tree[i] = combine(tree[i<<1], tree[i<<1|1]);
    }
    Node query(int i, int l, int r, int s, int e){
        if (s>e) return Node(0, 0, -9e18, 0);
        propagate(i, l, r);
        if (r<s || e<l) return Node(0, 0, -9e18, 0);
        if (s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        Node ret = query(i<<1, l, m, s, e);
        ret = combine(ret, query(i<<1|1, m+1, r, s, e));
        return ret;
    }
}tree[100100];
struct Edge{
    int s, e, x;
    Edge(){}
    Edge(int _s, int _e, int _x): s(_s), e(_e), x(_x){}
    int nxt(int val){
        if (s==val) return e;
        return s;
    }
}e[100100];
vector<int> adj[100100], g[100100];
int sz[100100];
bool cent_visited[100100];

void getsz(int s, int pa){
    sz[s] = 1;
    for (auto &v:adj[s]){
        int nxt = e[v].nxt(s);
        if (nxt==pa || cent_visited[nxt]) continue;
        getsz(nxt, s);
        sz[s] += sz[nxt];
    }
}

int getcent(int s, int pa, int mx){
    for (auto &v:adj[s]){
        int nxt = e[v].nxt(s);
        if (nxt==pa || cent_visited[nxt]) continue;
        if (sz[nxt]*2>mx) return getcent(nxt, s, mx);
    }
    return s;
}

int cnt;
vector<Node> vec;
unordered_map<int, pair<int, int>> mp[100100];
unordered_map<int, int> mp2[100100];
pair<int, int> ran[100100];

pair<int, int> dfs(int s, int pa, int val, int cent){
    pair<int, int> ret = {9e18, -9e18};
    for (auto &v:adj[s]){
        int nxt = e[v].nxt(s);
        if (nxt==pa || cent_visited[nxt]) continue;
        auto p = dfs(nxt, s, val+e[v].x, cent);
        ret.first = min(ret.first, p.first);
        ret.second = max(ret.second, p.second);

        mp[cent][v] = p;
        if (cent==s){
            ran[cnt] = p;
            cnt++;
        }
        else{
            mp2[cent][v] = cnt;
        }
    }
    if (ret.first==9e18){
        vec.emplace_back(0, 0, val, cnt);
        return make_pair((int)vec.size()-1, (int)vec.size()-1);
    }
    return ret;
}

int getcentree(int s){
    getsz(s, -1);
    if (sz[s]==1) return s;
    int cent = getcent(s, -1, sz[s]);
    cnt = 0;
    vec.clear();
    auto p = dfs(cent, -1, 0, cent);
    for (auto &N:vec) N.x = ran[N.nxt].first, N.y = ran[N.nxt].second;
    //for (auto &N:vec) printf("%lld %lld %lld %lld\n", N.x, N.y, N.w, N.nxt);
    //printf("%lld %lld\n", p.first, p.second);
    tree[cent].make_tree((int)vec.size());
    tree[cent].init(1, 0, p.second, vec);

    cent_visited[cent] = 1;
    for (auto &v:adj[cent]){
        int nxt = e[v].nxt(cent);
        if (cent_visited[nxt]) continue;
        int x = getcentree(nxt);
        g[cent].push_back(x);
    }
    return cent;
}

signed main(){
    int n, q, w;
    scanf("%lld %lld %lld", &n, &q, &w);
    for (int i=0;i<n-1;i++){
        scanf("%lld %lld %lld", &e[i].s, &e[i].e, &e[i].x);
        adj[e[i].s].push_back(i);
        adj[e[i].e].push_back(i);
    }

    int CENT = getcentree(1);
    /*for (int i=0;i<3;i++){
        Node tmp2 = tree[2].query(1, 0, 2, i, i);
        printf("%lld %lld %lld %lld\n", tmp2.x, tmp2.y, tmp2.w, tmp2.nxt);
    }*/

    int last = 0;
    while(q--){
        int x, y;
        scanf("%lld %lld", &x, &y);
        x = (x+last)%(n-1);
        y = (y+last)%w;
        int org = e[x].x;
        e[x].x = y;
        //printf("%lld %lld %lld\n", y, org, e[x].x);

        int pos = CENT;
        while(true){
            if (g[pos].empty()) break;
            assert(mp[pos].find(x)!=mp[pos].end());
            auto p = mp[pos][x];
            //printf("%lld %lld\n", p.first, p.second);
            tree[pos].update(1, 0, tree[pos].sz-1, p.first, p.second, y-org);
            if (mp2[pos].find(x)==mp2[pos].end()) break;
            pos = g[pos][mp2[pos][x]];
        }

        int ans = 0;
        pos = CENT;
        while(true){
            if (g[pos].empty()) break;
            auto tmp = tree[pos].query(1, 0, tree[pos].sz-1, 0, tree[pos].sz);
            //printf("%lld %lld %lld %lld\n", tmp.x, tmp.y, tmp.w, tmp.nxt);
            auto tmp2 = tree[pos].query(1, 0, tree[pos].sz-1, 0, tmp.x-1);
            //printf("%lld %lld %lld %lld\n", tmp2.x, tmp2.y, tmp2.w, tmp2.nxt);
            auto tmp3 = tree[pos].query(1, 0, tree[pos].sz-1, tmp.y+1, tree[pos].sz-1);
            //printf("%lld %lld %lld %lld\n", tmp3.x, tmp3.y, tmp3.w, tmp3.nxt);
            int val = max(tmp.w, tmp.w+max(tmp2.w, tmp3.w));
            ans = max(ans, val);
            pos = g[pos][tmp.nxt];
        }
        printf("%lld\n", ans);
        last = ans;
    }
    return 0;
}

Compilation message

diameter.cpp: In function 'int main()':
diameter.cpp:150:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |     scanf("%lld %lld %lld", &n, &q, &w);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:152:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |         scanf("%lld %lld %lld", &e[i].s, &e[i].e, &e[i].x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:166:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |         scanf("%lld %lld", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 21452 KB Output is correct
2 Correct 13 ms 21400 KB Output is correct
3 Correct 12 ms 21472 KB Output is correct
4 Correct 13 ms 21472 KB Output is correct
5 Correct 13 ms 21388 KB Output is correct
6 Correct 13 ms 21416 KB Output is correct
7 Correct 13 ms 21444 KB Output is correct
8 Correct 13 ms 21452 KB Output is correct
9 Correct 13 ms 21452 KB Output is correct
10 Correct 14 ms 21440 KB Output is correct
11 Correct 13 ms 21452 KB Output is correct
12 Correct 13 ms 21452 KB Output is correct
13 Correct 13 ms 21452 KB Output is correct
14 Correct 13 ms 21544 KB Output is correct
15 Correct 14 ms 21452 KB Output is correct
16 Correct 13 ms 21452 KB Output is correct
17 Correct 13 ms 21484 KB Output is correct
18 Correct 13 ms 21516 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 21452 KB Output is correct
2 Correct 13 ms 21400 KB Output is correct
3 Correct 12 ms 21472 KB Output is correct
4 Correct 13 ms 21472 KB Output is correct
5 Correct 13 ms 21388 KB Output is correct
6 Correct 13 ms 21416 KB Output is correct
7 Correct 13 ms 21444 KB Output is correct
8 Correct 13 ms 21452 KB Output is correct
9 Correct 13 ms 21452 KB Output is correct
10 Correct 14 ms 21440 KB Output is correct
11 Correct 13 ms 21452 KB Output is correct
12 Correct 13 ms 21452 KB Output is correct
13 Correct 13 ms 21452 KB Output is correct
14 Correct 13 ms 21544 KB Output is correct
15 Correct 14 ms 21452 KB Output is correct
16 Correct 13 ms 21452 KB Output is correct
17 Correct 13 ms 21484 KB Output is correct
18 Correct 13 ms 21516 KB Output is correct
19 Correct 28 ms 22476 KB Output is correct
20 Correct 28 ms 22608 KB Output is correct
21 Correct 31 ms 22764 KB Output is correct
22 Correct 25 ms 22600 KB Output is correct
23 Correct 50 ms 27588 KB Output is correct
24 Correct 64 ms 28688 KB Output is correct
25 Correct 73 ms 29600 KB Output is correct
26 Correct 58 ms 29016 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 21452 KB Output is correct
2 Correct 12 ms 21452 KB Output is correct
3 Correct 14 ms 21452 KB Output is correct
4 Correct 24 ms 21544 KB Output is correct
5 Correct 71 ms 21820 KB Output is correct
6 Correct 13 ms 21416 KB Output is correct
7 Correct 13 ms 21516 KB Output is correct
8 Correct 15 ms 21580 KB Output is correct
9 Correct 14 ms 21516 KB Output is correct
10 Correct 30 ms 21672 KB Output is correct
11 Correct 104 ms 22012 KB Output is correct
12 Correct 16 ms 23112 KB Output is correct
13 Correct 16 ms 23056 KB Output is correct
14 Correct 18 ms 23032 KB Output is correct
15 Correct 40 ms 23164 KB Output is correct
16 Correct 137 ms 23488 KB Output is correct
17 Correct 74 ms 52396 KB Output is correct
18 Correct 77 ms 52372 KB Output is correct
19 Correct 80 ms 52348 KB Output is correct
20 Correct 112 ms 52456 KB Output is correct
21 Correct 262 ms 53068 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 22944 KB Output is correct
2 Correct 36 ms 22964 KB Output is correct
3 Correct 119 ms 23168 KB Output is correct
4 Correct 223 ms 23416 KB Output is correct
5 Correct 65 ms 41280 KB Output is correct
6 Correct 101 ms 41396 KB Output is correct
7 Correct 284 ms 41628 KB Output is correct
8 Correct 509 ms 42016 KB Output is correct
9 Correct 308 ms 138584 KB Output is correct
10 Correct 373 ms 138744 KB Output is correct
11 Correct 664 ms 138860 KB Output is correct
12 Correct 1008 ms 139224 KB Output is correct
13 Correct 630 ms 270184 KB Output is correct
14 Correct 710 ms 270236 KB Output is correct
15 Correct 1060 ms 270408 KB Output is correct
16 Correct 1483 ms 270908 KB Output is correct
17 Correct 2506 ms 270928 KB Output is correct

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2268 ms 204612 KB Output is correct
2 Correct 2455 ms 209428 KB Output is correct
3 Correct 2410 ms 208452 KB Output is correct
4 Correct 2565 ms 213712 KB Output is correct
5 Correct 2381 ms 196492 KB Output is correct
6 Correct 2086 ms 138228 KB Output is correct
7 Correct 2916 ms 254392 KB Output is correct
8 Correct 2897 ms 254804 KB Output is correct
9 Correct 2909 ms 258812 KB Output is correct
10 Correct 2977 ms 259036 KB Output is correct
11 Correct 2895 ms 246276 KB Output is correct
12 Correct 2359 ms 157188 KB Output is correct
13 Correct 2242 ms 220844 KB Output is correct
14 Correct 2219 ms 220896 KB Output is correct
15 Correct 2334 ms 221048 KB Output is correct
16 Correct 2425 ms 220668 KB Output is correct
17 Correct 2314 ms 212484 KB Output is correct
18 Correct 1736 ms 142408 KB Output is correct
19 Correct 2263 ms 221100 KB Output is correct
20 Correct 2308 ms 220896 KB Output is correct
21 Correct 2497 ms 220992 KB Output is correct
22 Correct 2541 ms 220540 KB Output is correct
23 Correct 2324 ms 212356 KB Output is correct
24 Correct 1761 ms 142448 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 21452 KB Output is correct
2 Correct 13 ms 21400 KB Output is correct
3 Correct 12 ms 21472 KB Output is correct
4 Correct 13 ms 21472 KB Output is correct
5 Correct 13 ms 21388 KB Output is correct
6 Correct 13 ms 21416 KB Output is correct
7 Correct 13 ms 21444 KB Output is correct
8 Correct 13 ms 21452 KB Output is correct
9 Correct 13 ms 21452 KB Output is correct
10 Correct 14 ms 21440 KB Output is correct
11 Correct 13 ms 21452 KB Output is correct
12 Correct 13 ms 21452 KB Output is correct
13 Correct 13 ms 21452 KB Output is correct
14 Correct 13 ms 21544 KB Output is correct
15 Correct 14 ms 21452 KB Output is correct
16 Correct 13 ms 21452 KB Output is correct
17 Correct 13 ms 21484 KB Output is correct
18 Correct 13 ms 21516 KB Output is correct
19 Correct 28 ms 22476 KB Output is correct
20 Correct 28 ms 22608 KB Output is correct
21 Correct 31 ms 22764 KB Output is correct
22 Correct 25 ms 22600 KB Output is correct
23 Correct 50 ms 27588 KB Output is correct
24 Correct 64 ms 28688 KB Output is correct
25 Correct 73 ms 29600 KB Output is correct
26 Correct 58 ms 29016 KB Output is correct
27 Correct 13 ms 21452 KB Output is correct
28 Correct 12 ms 21452 KB Output is correct
29 Correct 14 ms 21452 KB Output is correct
30 Correct 24 ms 21544 KB Output is correct
31 Correct 71 ms 21820 KB Output is correct
32 Correct 13 ms 21416 KB Output is correct
33 Correct 13 ms 21516 KB Output is correct
34 Correct 15 ms 21580 KB Output is correct
35 Correct 14 ms 21516 KB Output is correct
36 Correct 30 ms 21672 KB Output is correct
37 Correct 104 ms 22012 KB Output is correct
38 Correct 16 ms 23112 KB Output is correct
39 Correct 16 ms 23056 KB Output is correct
40 Correct 18 ms 23032 KB Output is correct
41 Correct 40 ms 23164 KB Output is correct
42 Correct 137 ms 23488 KB Output is correct
43 Correct 74 ms 52396 KB Output is correct
44 Correct 77 ms 52372 KB Output is correct
45 Correct 80 ms 52348 KB Output is correct
46 Correct 112 ms 52456 KB Output is correct
47 Correct 262 ms 53068 KB Output is correct
48 Correct 18 ms 22944 KB Output is correct
49 Correct 36 ms 22964 KB Output is correct
50 Correct 119 ms 23168 KB Output is correct
51 Correct 223 ms 23416 KB Output is correct
52 Correct 65 ms 41280 KB Output is correct
53 Correct 101 ms 41396 KB Output is correct
54 Correct 284 ms 41628 KB Output is correct
55 Correct 509 ms 42016 KB Output is correct
56 Correct 308 ms 138584 KB Output is correct
57 Correct 373 ms 138744 KB Output is correct
58 Correct 664 ms 138860 KB Output is correct
59 Correct 1008 ms 139224 KB Output is correct
60 Correct 630 ms 270184 KB Output is correct
61 Correct 710 ms 270236 KB Output is correct
62 Correct 1060 ms 270408 KB Output is correct
63 Correct 1483 ms 270908 KB Output is correct
64 Correct 2506 ms 270928 KB Output is correct
65 Correct 2268 ms 204612 KB Output is correct
66 Correct 2455 ms 209428 KB Output is correct
67 Correct 2410 ms 208452 KB Output is correct
68 Correct 2565 ms 213712 KB Output is correct
69 Correct 2381 ms 196492 KB Output is correct
70 Correct 2086 ms 138228 KB Output is correct
71 Correct 2916 ms 254392 KB Output is correct
72 Correct 2897 ms 254804 KB Output is correct
73 Correct 2909 ms 258812 KB Output is correct
74 Correct 2977 ms 259036 KB Output is correct
75 Correct 2895 ms 246276 KB Output is correct
76 Correct 2359 ms 157188 KB Output is correct
77 Correct 2242 ms 220844 KB Output is correct
78 Correct 2219 ms 220896 KB Output is correct
79 Correct 2334 ms 221048 KB Output is correct
80 Correct 2425 ms 220668 KB Output is correct
81 Correct 2314 ms 212484 KB Output is correct
82 Correct 1736 ms 142408 KB Output is correct
83 Correct 2263 ms 221100 KB Output is correct
84 Correct 2308 ms 220896 KB Output is correct
85 Correct 2497 ms 220992 KB Output is correct
86 Correct 2541 ms 220540 KB Output is correct
87 Correct 2324 ms 212356 KB Output is correct
88 Correct 1761 ms 142448 KB Output is correct
89 Correct 2332 ms 211116 KB Output is correct
90 Correct 2710 ms 235772 KB Output is correct
91 Correct 2920 ms 257492 KB Output is correct
92 Correct 2907 ms 258468 KB Output is correct
93 Correct 2841 ms 255480 KB Output is correct
94 Correct 2659 ms 245500 KB Output is correct
95 Correct 2334 ms 220320 KB Output is correct
96 Correct 2211 ms 220408 KB Output is correct
97 Correct 2246 ms 220428 KB Output is correct
98 Correct 2222 ms 220348 KB Output is correct
99 Correct 2252 ms 220216 KB Output is correct
100 Correct 2218 ms 220152 KB Output is correct