oj.uz

답안 #658697

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
658697 2022-11-14T12:25:16 Z mychecksedad Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 2741 ms 300528 KB 
/* Author : Mychecksdead */
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD1 (1000000000+7)
#define MOD (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;



int n, q, sz[N], timer, tin[N], tout[N], num;
ll w, last = 0;
vector<int> g[N];
pair<int, ll> edges[N];
vector<bool> vis;
vector<vector<ll>> lazy, seg;
vector<array<ll, 5>> upd[N];
multiset<ll> answers, depths[N];

ll get_ans(){
    auto it = answers.end(); --it;
    return *it;
}
ll f(multiset<ll> &a){
    if(a.empty()) return 0;
    if(a.size() == 1) return *a.begin();
    auto it = a.end(); --it;
    ll x = *it; --it; x+=*it;
    return x;
}
void pre(int v, int p){
    sz[v] = 1;
    num++;
    for(int e: g[v]){
        int u = edges[e].first;
        if(u == p || vis[u]) continue;
        pre(u, v);
        sz[v] += sz[u];
    }
}

void pre2(int v, int p){
    if(g[v].size() == 1){
        tin[v] = timer;
        tout[v] = timer++;
        return;
    }
    tin[v] = MOD, tout[v] = 0;
    for(int e: g[v]){
        int u = edges[e].first;
        if(u == p || vis[u]) continue;
        pre2(u, v);
        tin[v] = min(tin[v], tin[u]);
        tout[v] = max(tout[v], tout[u]);
    }
}

int find_centroid(int v, int p){
    for(int e: g[v]){
        int u = edges[e].first;
        if(u==p || vis[u]) continue;
        if(sz[u] > num/2) return find_centroid(u, v);
    }
    return v;
}
void push(int k, int s){
    lazy[s][k<<1] += lazy[s][k];
    lazy[s][k<<1|1] += lazy[s][k];
    seg[s][k<<1] += lazy[s][k];
    seg[s][k<<1|1] += lazy[s][k];
    lazy[s][k] = 0;
}


void update(int l, int r, int ql, int qr, int k, int s, ll val, int centro){
    if(ql > r || qr < l) return;
    if(ql <= l && r <= qr){
        if(k==1){
            depths[centro].erase(depths[centro].find(seg[s][k]));
        }

        seg[s][k] += val;
        lazy[s][k] += val;

        if(k==1){
            depths[centro].insert(seg[s][k]);
        }

        return;
    }
    push(k, s);
    int m = (l+r)>>1;
    update(l, m, ql, qr, k<<1, s, val, centro);
    update(m+1, r, ql, qr, k<<1|1, s, val, centro);

    if(k==1){
        depths[centro].erase(depths[centro].find(seg[s][k]));
    }

    seg[s][k] = max(seg[s][k<<1], seg[s][k<<1|1]);

    if(k==1){
        depths[centro].insert(seg[s][k]);
    }
}

void dfs(int v, int p, int centro){
    for(int e: g[v]){
        int u = edges[e].first;
        if(u == p || vis[u]) continue;

        upd[e].pb({seg.size() - 1, tin[u], tout[u], timer, centro});
        upd[e^1].pb({seg.size() - 1, tin[u], tout[u], timer, centro});

        update(1, timer, tin[u], tout[u], 1, seg.size() - 1, edges[e].second, centro);

        dfs(u, v, centro);
    }
}

void find(int v){
    num = 0;
    pre(v, 0);
    
    if(num == 1){
        vis[v] = 1;
        return;
    }

    v = find_centroid(v, 0);

    for(int e: g[v]){
        int u = edges[e].first;
        if(vis[u]) continue;

        timer = 1;

        pre2(u, v);

        seg.pb({});
        lazy.pb({});
        seg.back().resize(4 * timer);
        lazy.back().resize(4 * timer);
        depths[v].insert(0);

        upd[e].pb({seg.size() - 1, 1, timer, timer, v});
        upd[e^1].pb({seg.size() - 1, 1, timer, timer, v});

        update(1, timer, 1, timer, 1, seg.size() - 1, edges[e].second, v);

        dfs(u, v, v);
    }
    answers.insert(f(depths[v]));
    vis[v] = 1;

    for(int e: g[v]){
        int u = edges[e].first;
        if(!vis[u]) find(u);
    }
}

void solve(){
    cin >> n >> q >> w;
    for(int i = 0; i < n - 1; ++i){
        int u, v; ll e; cin >> u >> v >> e;
        g[v].pb(i*2);
        g[u].pb(i*2+1);
        edges[2*i] = {u, e};
        edges[2*i+1] = {v, e};
    }
    vis.resize(n+1);
    find(1);
    for(;q--;){
        int d; ll e; cin >> d >> e;
        d = (d + last) % (n-1);
        e = (e + last) % w;
        ll delta = e - edges[2*d].second;
        edges[2*d].second = e;
        edges[2*d+1].second = e;
        for(auto up: upd[d*2]){
            answers.erase(answers.find(f(depths[up[4]])));
            update(1, up[3], up[1], up[2], 1, up[0], delta, up[4]);
            answers.insert(f(depths[up[4]]));
        }
        last = get_ans();
        cout << last << '\n';
    }
}





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
    }
    return 0;
 
}

Compilation message

diameter.cpp: In function 'void dfs(int, int, int)':
diameter.cpp:120:31: warning: narrowing conversion of '(seg.std::vector<std::vector<long long int> >::size() - 1)' from 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
  120 |         upd[e].pb({seg.size() - 1, tin[u], tout[u], timer, centro});
      |                    ~~~~~~~~~~~^~~
diameter.cpp:121:33: warning: narrowing conversion of '(seg.std::vector<std::vector<long long int> >::size() - 1)' from 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
  121 |         upd[e^1].pb({seg.size() - 1, tin[u], tout[u], timer, centro});
      |                      ~~~~~~~~~~~^~~
diameter.cpp: In function 'void find(int)':
diameter.cpp:154:31: warning: narrowing conversion of '(seg.std::vector<std::vector<long long int> >::size() - 1)' from 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
  154 |         upd[e].pb({seg.size() - 1, 1, timer, timer, v});
      |                    ~~~~~~~~~~~^~~
diameter.cpp:155:33: warning: narrowing conversion of '(seg.std::vector<std::vector<long long int> >::size() - 1)' from 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
  155 |         upd[e^1].pb({seg.size() - 1, 1, timer, timer, v});
      |                      ~~~~~~~~~~~^~~
diameter.cpp: In function 'int main()':
diameter.cpp:204:16: warning: unused variable 'aa' [-Wunused-variable]
  204 |     int T = 1, aa;
      |                ^~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 94284 KB Output is correct
2 Correct 49 ms 94184 KB Output is correct
3 Correct 47 ms 94212 KB Output is correct
4 Correct 50 ms 94284 KB Output is correct
5 Correct 44 ms 94412 KB Output is correct
6 Correct 47 ms 94284 KB Output is correct
7 Correct 42 ms 94328 KB Output is correct
8 Correct 42 ms 94212 KB Output is correct
9 Correct 42 ms 94268 KB Output is correct
10 Correct 47 ms 94284 KB Output is correct
11 Correct 44 ms 94324 KB Output is correct
12 Correct 43 ms 94208 KB Output is correct
13 Correct 43 ms 94356 KB Output is correct
14 Correct 43 ms 94408 KB Output is correct
15 Correct 43 ms 94280 KB Output is correct
16 Correct 44 ms 94284 KB Output is correct
17 Correct 46 ms 94340 KB Output is correct
18 Correct 48 ms 94272 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 94284 KB Output is correct
2 Correct 49 ms 94184 KB Output is correct
3 Correct 47 ms 94212 KB Output is correct
4 Correct 50 ms 94284 KB Output is correct
5 Correct 44 ms 94412 KB Output is correct
6 Correct 47 ms 94284 KB Output is correct
7 Correct 42 ms 94328 KB Output is correct
8 Correct 42 ms 94212 KB Output is correct
9 Correct 42 ms 94268 KB Output is correct
10 Correct 47 ms 94284 KB Output is correct
11 Correct 44 ms 94324 KB Output is correct
12 Correct 43 ms 94208 KB Output is correct
13 Correct 43 ms 94356 KB Output is correct
14 Correct 43 ms 94408 KB Output is correct
15 Correct 43 ms 94280 KB Output is correct
16 Correct 44 ms 94284 KB Output is correct
17 Correct 46 ms 94340 KB Output is correct
18 Correct 48 ms 94272 KB Output is correct
19 Correct 56 ms 95436 KB Output is correct
20 Correct 56 ms 95400 KB Output is correct
21 Correct 60 ms 95444 KB Output is correct
22 Correct 53 ms 95692 KB Output is correct
23 Correct 75 ms 99916 KB Output is correct
24 Correct 83 ms 101340 KB Output is correct
25 Correct 91 ms 102492 KB Output is correct
26 Correct 78 ms 102512 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 94180 KB Output is correct
2 Correct 47 ms 94180 KB Output is correct
3 Correct 43 ms 94308 KB Output is correct
4 Correct 57 ms 94524 KB Output is correct
5 Correct 85 ms 95420 KB Output is correct
6 Correct 48 ms 94288 KB Output is correct
7 Correct 50 ms 94480 KB Output is correct
8 Correct 43 ms 94468 KB Output is correct
9 Correct 44 ms 94416 KB Output is correct
10 Correct 58 ms 94684 KB Output is correct
11 Correct 88 ms 95816 KB Output is correct
12 Correct 48 ms 96380 KB Output is correct
13 Correct 51 ms 96464 KB Output is correct
14 Correct 49 ms 96424 KB Output is correct
15 Correct 62 ms 96712 KB Output is correct
16 Correct 105 ms 97916 KB Output is correct
17 Correct 199 ms 137700 KB Output is correct
18 Correct 196 ms 137780 KB Output is correct
19 Correct 181 ms 137700 KB Output is correct
20 Correct 220 ms 138152 KB Output is correct
21 Correct 400 ms 139148 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 95484 KB Output is correct
2 Correct 66 ms 95632 KB Output is correct
3 Correct 139 ms 96160 KB Output is correct
4 Correct 239 ms 96900 KB Output is correct
5 Correct 109 ms 113092 KB Output is correct
6 Correct 125 ms 113396 KB Output is correct
7 Correct 283 ms 113976 KB Output is correct
8 Correct 459 ms 114664 KB Output is correct
9 Correct 338 ms 195024 KB Output is correct
10 Correct 427 ms 195024 KB Output is correct
11 Correct 660 ms 195716 KB Output is correct
12 Correct 983 ms 196448 KB Output is correct
13 Correct 765 ms 299184 KB Output is correct
14 Correct 794 ms 299512 KB Output is correct
15 Correct 1148 ms 300040 KB Output is correct
16 Correct 1487 ms 300364 KB Output is correct
17 Correct 2413 ms 300528 KB Output is correct

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2011 ms 270072 KB Output is correct
2 Correct 2045 ms 274660 KB Output is correct
3 Correct 2037 ms 274084 KB Output is correct
4 Correct 2090 ms 273468 KB Output is correct
5 Correct 2091 ms 264864 KB Output is correct
6 Correct 1621 ms 209196 KB Output is correct
7 Correct 2653 ms 287984 KB Output is correct
8 Correct 2631 ms 287908 KB Output is correct
9 Correct 2672 ms 287888 KB Output is correct
10 Correct 2581 ms 287188 KB Output is correct
11 Correct 2503 ms 276828 KB Output is correct
12 Correct 1921 ms 214408 KB Output is correct
13 Correct 1875 ms 264076 KB Output is correct
14 Correct 1906 ms 264104 KB Output is correct
15 Correct 1899 ms 264268 KB Output is correct
16 Correct 1880 ms 263920 KB Output is correct
17 Correct 1799 ms 257040 KB Output is correct
18 Correct 1304 ms 206232 KB Output is correct
19 Correct 1846 ms 264396 KB Output is correct
20 Correct 1882 ms 264164 KB Output is correct
21 Correct 1922 ms 264420 KB Output is correct
22 Correct 1934 ms 264088 KB Output is correct
23 Correct 1826 ms 257196 KB Output is correct
24 Correct 1313 ms 206384 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 94284 KB Output is correct
2 Correct 49 ms 94184 KB Output is correct
3 Correct 47 ms 94212 KB Output is correct
4 Correct 50 ms 94284 KB Output is correct
5 Correct 44 ms 94412 KB Output is correct
6 Correct 47 ms 94284 KB Output is correct
7 Correct 42 ms 94328 KB Output is correct
8 Correct 42 ms 94212 KB Output is correct
9 Correct 42 ms 94268 KB Output is correct
10 Correct 47 ms 94284 KB Output is correct
11 Correct 44 ms 94324 KB Output is correct
12 Correct 43 ms 94208 KB Output is correct
13 Correct 43 ms 94356 KB Output is correct
14 Correct 43 ms 94408 KB Output is correct
15 Correct 43 ms 94280 KB Output is correct
16 Correct 44 ms 94284 KB Output is correct
17 Correct 46 ms 94340 KB Output is correct
18 Correct 48 ms 94272 KB Output is correct
19 Correct 56 ms 95436 KB Output is correct
20 Correct 56 ms 95400 KB Output is correct
21 Correct 60 ms 95444 KB Output is correct
22 Correct 53 ms 95692 KB Output is correct
23 Correct 75 ms 99916 KB Output is correct
24 Correct 83 ms 101340 KB Output is correct
25 Correct 91 ms 102492 KB Output is correct
26 Correct 78 ms 102512 KB Output is correct
27 Correct 47 ms 94180 KB Output is correct
28 Correct 47 ms 94180 KB Output is correct
29 Correct 43 ms 94308 KB Output is correct
30 Correct 57 ms 94524 KB Output is correct
31 Correct 85 ms 95420 KB Output is correct
32 Correct 48 ms 94288 KB Output is correct
33 Correct 50 ms 94480 KB Output is correct
34 Correct 43 ms 94468 KB Output is correct
35 Correct 44 ms 94416 KB Output is correct
36 Correct 58 ms 94684 KB Output is correct
37 Correct 88 ms 95816 KB Output is correct
38 Correct 48 ms 96380 KB Output is correct
39 Correct 51 ms 96464 KB Output is correct
40 Correct 49 ms 96424 KB Output is correct
41 Correct 62 ms 96712 KB Output is correct
42 Correct 105 ms 97916 KB Output is correct
43 Correct 199 ms 137700 KB Output is correct
44 Correct 196 ms 137780 KB Output is correct
45 Correct 181 ms 137700 KB Output is correct
46 Correct 220 ms 138152 KB Output is correct
47 Correct 400 ms 139148 KB Output is correct
48 Correct 54 ms 95484 KB Output is correct
49 Correct 66 ms 95632 KB Output is correct
50 Correct 139 ms 96160 KB Output is correct
51 Correct 239 ms 96900 KB Output is correct
52 Correct 109 ms 113092 KB Output is correct
53 Correct 125 ms 113396 KB Output is correct
54 Correct 283 ms 113976 KB Output is correct
55 Correct 459 ms 114664 KB Output is correct
56 Correct 338 ms 195024 KB Output is correct
57 Correct 427 ms 195024 KB Output is correct
58 Correct 660 ms 195716 KB Output is correct
59 Correct 983 ms 196448 KB Output is correct
60 Correct 765 ms 299184 KB Output is correct
61 Correct 794 ms 299512 KB Output is correct
62 Correct 1148 ms 300040 KB Output is correct
63 Correct 1487 ms 300364 KB Output is correct
64 Correct 2413 ms 300528 KB Output is correct
65 Correct 2011 ms 270072 KB Output is correct
66 Correct 2045 ms 274660 KB Output is correct
67 Correct 2037 ms 274084 KB Output is correct
68 Correct 2090 ms 273468 KB Output is correct
69 Correct 2091 ms 264864 KB Output is correct
70 Correct 1621 ms 209196 KB Output is correct
71 Correct 2653 ms 287984 KB Output is correct
72 Correct 2631 ms 287908 KB Output is correct
73 Correct 2672 ms 287888 KB Output is correct
74 Correct 2581 ms 287188 KB Output is correct
75 Correct 2503 ms 276828 KB Output is correct
76 Correct 1921 ms 214408 KB Output is correct
77 Correct 1875 ms 264076 KB Output is correct
78 Correct 1906 ms 264104 KB Output is correct
79 Correct 1899 ms 264268 KB Output is correct
80 Correct 1880 ms 263920 KB Output is correct
81 Correct 1799 ms 257040 KB Output is correct
82 Correct 1304 ms 206232 KB Output is correct
83 Correct 1846 ms 264396 KB Output is correct
84 Correct 1882 ms 264164 KB Output is correct
85 Correct 1922 ms 264420 KB Output is correct
86 Correct 1934 ms 264088 KB Output is correct
87 Correct 1826 ms 257196 KB Output is correct
88 Correct 1313 ms 206384 KB Output is correct
89 Correct 2085 ms 271228 KB Output is correct
90 Correct 2326 ms 282112 KB Output is correct
91 Correct 2741 ms 288208 KB Output is correct
92 Correct 2612 ms 287644 KB Output is correct
93 Correct 2676 ms 283904 KB Output is correct
94 Correct 2468 ms 278684 KB Output is correct
95 Correct 1912 ms 263944 KB Output is correct
96 Correct 1905 ms 264012 KB Output is correct
97 Correct 1883 ms 263948 KB Output is correct
98 Correct 1899 ms 264116 KB Output is correct
99 Correct 1947 ms 264104 KB Output is correct
100 Correct 1898 ms 264032 KB Output is correct