oj.uz

Submission #278524

# Submission time Handle Problem Language Result Execution time Memory
278524 2020-08-21T13:43:42 Z egekabas Dynamic Diameter (CEOI19_diameter) C++14
31 / 100
 5000 ms 293272 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
ll seg[8000000];
ll lazy[8000000];
ll maxn = 2000000-1;
void push(ll v){
    seg[2*v] += lazy[v];
    seg[2*v+1] += lazy[v];
    lazy[2*v] += lazy[v];
    lazy[2*v+1] += lazy[v];
    lazy[v] = 0;
}
void upd(ll v, ll tl, ll tr, ll l, ll r, ll val){
    if(r < tl || tr < l)
        return;
    if(l <= tl && tr <= r){
        seg[v] += val;
        lazy[v] += val;
    }
    else{
        push(v);
        upd(2*v, tl, (tl+tr)/2, l, r, val);
        upd(2*v+1, (tl+tr)/2+1, tr, l, r, val);
        seg[v] = max(seg[2*v], seg[2*v+1]);
    }
}
ll get(ll v, ll tl, ll tr, ll l, ll r){
    if(r < tl || tr < l)
        return -1e18;
    if(l <= tl && tr <= r){
        return seg[v];
    }
    else{
        push(v);
        return max(
        get(2*v, tl, (tl+tr)/2, l, r),
        get(2*v+1, (tl+tr)/2+1, tr, l, r));
    }
}
struct edge{
    ll x, y, z;
};
vector<pll> g[100009];
edge e[100009];
    
ll sz[100009];
ll block[100009];
void findsz(ll v, ll prt){
    sz[v] = 1;
    for(auto u : g[v]){
        if(block[u.ff] || u.ff == prt) continue;
        findsz(u.ff, v);
        sz[v] += sz[u.ff];
    }
}
ll findcentroid(ll v, ll prt, ll totsz){
    for(auto u : g[v]){
        if(block[u.ff] || u.ff == prt) continue;
        if(sz[u.ff]*2 > totsz)
            return findcentroid(u.ff, v, totsz);
    }
    return v;
}
ll curtime = 0;
ll root;
map<ll, ll> tin[100009];
map<ll, ll> tout[100009];
vector<ll> change[100009];
vector<pll> entry[100009];
multiset<ll, greater<ll>> centmax[100009];
ll centans[100009];
multiset<ll, greater<ll>> totmax;
void dfs(ll v, ll prt){
    tin[root][v] = curtime++;
    ll distoprt;
    for(auto u : g[v]){
        if(block[u.ff])
            continue;
        if(u.ff == prt){
            change[u.ss].pb(root);
            distoprt = e[u.ss].z;
            continue;
        }
        dfs(u.ff, v);
    }
    tout[root][v] = curtime-1;
    upd(1, 0, maxn, tin[root][v], tout[root][v], distoprt);
}
void decomp(){
    findsz(root, 0);
    root = findcentroid(root, 0, sz[root]);
    tin[root][root] = curtime++;
    for(auto u : g[root]){
        if(block[u.ff]) continue;
        dfs(u.ff, root);
        entry[root].pb({tin[root][u.ff], tout[root][u.ff]});
        centmax[root].insert(get(1, 0, maxn, tin[root][u.ff], tout[root][u.ff]));
    }
    tout[root][root] = curtime-1;
    if(centmax[root].empty()) return;
    auto it = centmax[root].begin();
    centans[root] = *it;    
    if(centmax[root].size() >= 2){
        ++it;
        centans[root] += *it;
    }
    totmax.insert(centans[root]);
    block[root] = 1;
    ll v = root;
    for(auto u : g[v]){
        if(block[u.ff]) continue;
        root = u.ff;
        decomp();
    }
}
    
ll n, q, w;
ll last = 0;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n >> q >> w;
    for(ll i = 0; i < n-1; ++i){
        cin >> e[i].x >> e[i].y >> e[i].z;
        g[e[i].x].pb({e[i].y, i});
        g[e[i].y].pb({e[i].x, i});
    }
    root = 1;
    decomp();
    
    assert(curtime <= maxn);
    for(ll i = 0; i < q; ++i){
        ll d, val;
        cin >> d >> val;
        d = (d+last)%(n-1);
        val = (val+last)%w;
        ll ch = val - e[d].z;
        for(auto root : change[d]){
            ll v;
            
            if(tin[root][e[d].x] > tin[root][e[d].y])
                v = e[d].x;
            else
                v = e[d].y;
            ll in = tin[root][v];
            ll out = tout[root][v];

            pii cursub = entry[root][upper_bound(all(entry[root]), mp(in, (ll)1e18))-entry[root].begin()-1];
            centmax[root].erase(centmax[root].lower_bound(get(1, 0, maxn, cursub.ff, cursub.ss)));
            upd(1, 0, maxn, in, out, ch);
            centmax[root].insert(get(1, 0, maxn, cursub.ff, cursub.ss));
            totmax.erase(totmax.lower_bound(centans[root]));
            auto it = centmax[root].begin();
            centans[root] = *it;    
            
            if(centmax[root].size() >= 2){  
                ++it;
                centans[root] += *it;
            }
            totmax.insert(centans[root]);
        }
        last = *totmax.begin();
        cout << last << '\n';
        e[d].z = val;
    }
}

Compilation message

diameter.cpp: In function 'void dfs(ll, ll)':
diameter.cpp:99:8: warning: 'distoprt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   99 |     upd(1, 0, maxn, tin[root][v], tout[root][v], distoprt);
      |     ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21632 KB Output is correct
2 Correct 15 ms 21632 KB Output is correct
3 Correct 18 ms 21632 KB Output is correct
4 Correct 15 ms 21632 KB Output is correct
5 Correct 16 ms 21632 KB Output is correct
6 Correct 16 ms 21760 KB Output is correct
7 Correct 16 ms 21632 KB Output is correct
8 Correct 15 ms 21760 KB Output is correct
9 Correct 15 ms 21632 KB Output is correct
10 Correct 16 ms 21632 KB Output is correct
11 Correct 16 ms 21632 KB Output is correct
12 Correct 16 ms 21760 KB Output is correct
13 Correct 16 ms 21760 KB Output is correct
14 Correct 18 ms 21760 KB Output is correct
15 Correct 16 ms 21760 KB Output is correct
16 Correct 16 ms 21760 KB Output is correct
17 Correct 16 ms 21760 KB Output is correct
18 Correct 18 ms 21760 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21632 KB Output is correct
2 Correct 15 ms 21632 KB Output is correct
3 Correct 18 ms 21632 KB Output is correct
4 Correct 15 ms 21632 KB Output is correct
5 Correct 16 ms 21632 KB Output is correct
6 Correct 16 ms 21760 KB Output is correct
7 Correct 16 ms 21632 KB Output is correct
8 Correct 15 ms 21760 KB Output is correct
9 Correct 15 ms 21632 KB Output is correct
10 Correct 16 ms 21632 KB Output is correct
11 Correct 16 ms 21632 KB Output is correct
12 Correct 16 ms 21760 KB Output is correct
13 Correct 16 ms 21760 KB Output is correct
14 Correct 18 ms 21760 KB Output is correct
15 Correct 16 ms 21760 KB Output is correct
16 Correct 16 ms 21760 KB Output is correct
17 Correct 16 ms 21760 KB Output is correct
18 Correct 18 ms 21760 KB Output is correct
19 Correct 73 ms 23000 KB Output is correct
20 Correct 91 ms 23040 KB Output is correct
21 Correct 94 ms 23296 KB Output is correct
22 Correct 115 ms 23552 KB Output is correct
23 Correct 162 ms 28664 KB Output is correct
24 Correct 196 ms 30456 KB Output is correct
25 Correct 216 ms 31480 KB Output is correct
26 Correct 255 ms 32888 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21632 KB Output is correct
2 Correct 15 ms 21632 KB Output is correct
3 Correct 17 ms 21632 KB Output is correct
4 Correct 42 ms 21760 KB Output is correct
5 Correct 153 ms 22136 KB Output is correct
6 Correct 15 ms 21760 KB Output is correct
7 Correct 16 ms 21888 KB Output is correct
8 Correct 16 ms 21888 KB Output is correct
9 Correct 19 ms 21888 KB Output is correct
10 Correct 53 ms 22008 KB Output is correct
11 Correct 206 ms 22420 KB Output is correct
12 Correct 27 ms 23936 KB Output is correct
13 Correct 28 ms 23936 KB Output is correct
14 Correct 32 ms 24056 KB Output is correct
15 Correct 76 ms 24060 KB Output is correct
16 Correct 265 ms 24440 KB Output is correct
17 Correct 369 ms 67300 KB Output is correct
18 Correct 365 ms 67176 KB Output is correct
19 Correct 418 ms 67300 KB Output is correct
20 Correct 471 ms 67300 KB Output is correct
21 Correct 1051 ms 68024 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 23168 KB Output is correct
2 Correct 117 ms 23296 KB Output is correct
3 Correct 506 ms 23544 KB Output is correct
4 Correct 963 ms 23800 KB Output is correct
5 Correct 156 ms 43384 KB Output is correct
6 Correct 335 ms 43512 KB Output is correct
7 Correct 1093 ms 43828 KB Output is correct
8 Correct 2148 ms 44084 KB Output is correct
9 Correct 934 ms 149368 KB Output is correct
10 Correct 1325 ms 149400 KB Output is correct
11 Correct 3030 ms 149508 KB Output is correct
12 Correct 4300 ms 150260 KB Output is correct
13 Correct 1802 ms 292856 KB Output is correct
14 Correct 2192 ms 292600 KB Output is correct
15 Correct 3910 ms 292988 KB Output is correct
16 Execution timed out 5074 ms 293272 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5095 ms 230856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21632 KB Output is correct
2 Correct 15 ms 21632 KB Output is correct
3 Correct 18 ms 21632 KB Output is correct
4 Correct 15 ms 21632 KB Output is correct
5 Correct 16 ms 21632 KB Output is correct
6 Correct 16 ms 21760 KB Output is correct
7 Correct 16 ms 21632 KB Output is correct
8 Correct 15 ms 21760 KB Output is correct
9 Correct 15 ms 21632 KB Output is correct
10 Correct 16 ms 21632 KB Output is correct
11 Correct 16 ms 21632 KB Output is correct
12 Correct 16 ms 21760 KB Output is correct
13 Correct 16 ms 21760 KB Output is correct
14 Correct 18 ms 21760 KB Output is correct
15 Correct 16 ms 21760 KB Output is correct
16 Correct 16 ms 21760 KB Output is correct
17 Correct 16 ms 21760 KB Output is correct
18 Correct 18 ms 21760 KB Output is correct
19 Correct 73 ms 23000 KB Output is correct
20 Correct 91 ms 23040 KB Output is correct
21 Correct 94 ms 23296 KB Output is correct
22 Correct 115 ms 23552 KB Output is correct
23 Correct 162 ms 28664 KB Output is correct
24 Correct 196 ms 30456 KB Output is correct
25 Correct 216 ms 31480 KB Output is correct
26 Correct 255 ms 32888 KB Output is correct
27 Correct 15 ms 21632 KB Output is correct
28 Correct 15 ms 21632 KB Output is correct
29 Correct 17 ms 21632 KB Output is correct
30 Correct 42 ms 21760 KB Output is correct
31 Correct 153 ms 22136 KB Output is correct
32 Correct 15 ms 21760 KB Output is correct
33 Correct 16 ms 21888 KB Output is correct
34 Correct 16 ms 21888 KB Output is correct
35 Correct 19 ms 21888 KB Output is correct
36 Correct 53 ms 22008 KB Output is correct
37 Correct 206 ms 22420 KB Output is correct
38 Correct 27 ms 23936 KB Output is correct
39 Correct 28 ms 23936 KB Output is correct
40 Correct 32 ms 24056 KB Output is correct
41 Correct 76 ms 24060 KB Output is correct
42 Correct 265 ms 24440 KB Output is correct
43 Correct 369 ms 67300 KB Output is correct
44 Correct 365 ms 67176 KB Output is correct
45 Correct 418 ms 67300 KB Output is correct
46 Correct 471 ms 67300 KB Output is correct
47 Correct 1051 ms 68024 KB Output is correct
48 Correct 32 ms 23168 KB Output is correct
49 Correct 117 ms 23296 KB Output is correct
50 Correct 506 ms 23544 KB Output is correct
51 Correct 963 ms 23800 KB Output is correct
52 Correct 156 ms 43384 KB Output is correct
53 Correct 335 ms 43512 KB Output is correct
54 Correct 1093 ms 43828 KB Output is correct
55 Correct 2148 ms 44084 KB Output is correct
56 Correct 934 ms 149368 KB Output is correct
57 Correct 1325 ms 149400 KB Output is correct
58 Correct 3030 ms 149508 KB Output is correct
59 Correct 4300 ms 150260 KB Output is correct
60 Correct 1802 ms 292856 KB Output is correct
61 Correct 2192 ms 292600 KB Output is correct
62 Correct 3910 ms 292988 KB Output is correct
63 Execution timed out 5074 ms 293272 KB Time limit exceeded
64 Halted 0 ms 0 KB -