oj.uz

Submission #884794

# Submission time Handle Problem Language Result Execution time Memory
884794 2023-12-08T12:26:18 Z Alish Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 200 ms 72616 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp		        make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("connect.in" , "r" , stdin) ; freopen("connect.out" , "w" , stdout);


ll mod = 1e9+7 ;

const int N = 2e5+23;
vector<pll> g[N];
int st[N], ft[N], tim;
vector<pair<pll, ll> > E;


struct Node{
    ll  pref, suff, sum, allans;
    ll ans, prefans, suffans;

}seg[4*N];

int n, q;
ll h[N];
ll ans[N];

vector<ll> vec;
pii pos[N];


void dfs(int v, int p=0){

    for (auto pp: g[v]){
        ll u=pp.F, w=ans[pp.S];
        if(u==p) continue;
        vec.pb(w);
        pos[pp.S].F=(vec.size()-1);
        h[u]=h[v]+w;
        dfs(u, v);
        vec.pb(-w);
        pos[pp.S].S=(vec.size()-1);
    }

}

void Merge(int ind){

    seg[ind].pref=max(seg[2*ind+1].pref, seg[2*ind+1].sum+seg[2*ind+2].pref);
	seg[ind].suff=max(seg[2*ind+2].suff, -seg[2*ind+2].sum+seg[2*ind+1].suff);

	seg[ind].sum=seg[2*ind+1].sum+seg[2*ind+2].sum;

	seg[ind].allans=max(seg[2*ind+1].allans+seg[2*ind+2].sum, -seg[2*ind+1].sum+seg[2*ind+2].allans);

	seg[ind].prefans=max({seg[2*ind+1].prefans, seg[2*ind+1].allans+seg[2*ind+2].pref, -seg[2*ind+1].sum+seg[2*ind+2].prefans});
	seg[ind].suffans=max({seg[2*ind+2].suffans, seg[2*ind+2].allans+seg[2*ind+1].suff, seg[2*ind+2].sum+seg[2*ind+1].suffans});

	seg[ind].ans=max({seg[2*ind+1].ans, seg[2*ind+2].ans, seg[2*ind+1].suffans+seg[2*ind+2].pref, seg[2*ind+1].suff+seg[2*ind+2].prefans});

}

void build(int l=0, int r=vec.size(), int ind=0){

    if(r-l==1){
        seg[ind].pref=max(0LL, vec[l]);
        seg[ind].suff=max(0LL, -vec[l]);
		seg[ind].ans=seg[ind].prefans=seg[ind].suffans=seg[ind].allans=abs(vec[l]);
		seg[ind].sum=vec[l];
        return;
    }
    int mid=(r+l)>>1;
    build(l, mid, 2*ind+1); build(mid, r, 2*ind+2);

    Merge(ind);
}

void upd(int i, ll v, int l=0, int r=vec.size(), int ind=0){
    if(r-l==1){
        vec[l]=v;
         seg[ind].pref=max(0LL, vec[l]);
        seg[ind].suff=max(0LL, -vec[l]);
		seg[ind].ans=seg[ind].prefans=seg[ind].suffans=seg[ind].allans=abs(vec[l]);
		seg[ind].sum=vec[l];
        return;
    }
    int mid=(r+l)>>1;
    if(i<mid) upd(i, v, l, mid, 2*ind+1);
    else upd(i, v, mid, r, 2*ind+2);

    Merge(ind);
}




int main()
{
    fast_io
    cin>>n>>q>>mod;

    for (int i=0; i<n-1; i++){
        ll u, v, w; cin>>v>>u>>w;
        g[v].pb({u, i}); g[u].pb({v, i});
        E.pb({{v, u}, w});
        ans[i]=w;
    }

    dfs(1);
    build();
    ll la=0;
    while(q--){
        ll i, w;
        cin>>i>>w;
        i=(i+la)%(n-1);
        w=(w+la)%mod;
        upd(pos[i].F, w);
        upd(pos[i].S, -w);
        la=seg[0].ans;
        cout<<la<<endl;
    }

}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11868 KB Output is correct
2 Correct 2 ms 11948 KB Output is correct
3 Correct 2 ms 11928 KB Output is correct
4 Correct 2 ms 11868 KB Output is correct
5 Correct 2 ms 11868 KB Output is correct
6 Correct 2 ms 11960 KB Output is correct
7 Correct 2 ms 11868 KB Output is correct
8 Correct 2 ms 11868 KB Output is correct
9 Correct 2 ms 11868 KB Output is correct
10 Correct 3 ms 11868 KB Output is correct
11 Correct 2 ms 11868 KB Output is correct
12 Correct 3 ms 11868 KB Output is correct
13 Correct 2 ms 11868 KB Output is correct
14 Correct 2 ms 11992 KB Output is correct
15 Correct 3 ms 11864 KB Output is correct
16 Correct 2 ms 11864 KB Output is correct
17 Correct 2 ms 11868 KB Output is correct
18 Correct 2 ms 11868 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11868 KB Output is correct
2 Correct 2 ms 11948 KB Output is correct
3 Correct 2 ms 11928 KB Output is correct
4 Correct 2 ms 11868 KB Output is correct
5 Correct 2 ms 11868 KB Output is correct
6 Correct 2 ms 11960 KB Output is correct
7 Correct 2 ms 11868 KB Output is correct
8 Correct 2 ms 11868 KB Output is correct
9 Correct 2 ms 11868 KB Output is correct
10 Correct 3 ms 11868 KB Output is correct
11 Correct 2 ms 11868 KB Output is correct
12 Correct 3 ms 11868 KB Output is correct
13 Correct 2 ms 11868 KB Output is correct
14 Correct 2 ms 11992 KB Output is correct
15 Correct 3 ms 11864 KB Output is correct
16 Correct 2 ms 11864 KB Output is correct
17 Correct 2 ms 11868 KB Output is correct
18 Correct 2 ms 11868 KB Output is correct
19 Correct 5 ms 12000 KB Output is correct
20 Correct 5 ms 11996 KB Output is correct
21 Correct 6 ms 12124 KB Output is correct
22 Correct 5 ms 12124 KB Output is correct
23 Correct 7 ms 14656 KB Output is correct
24 Correct 8 ms 14932 KB Output is correct
25 Correct 7 ms 14940 KB Output is correct
26 Correct 8 ms 15452 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11868 KB Output is correct
2 Correct 2 ms 11868 KB Output is correct
3 Correct 3 ms 11868 KB Output is correct
4 Correct 8 ms 12124 KB Output is correct
5 Correct 31 ms 13128 KB Output is correct
6 Correct 2 ms 11868 KB Output is correct
7 Correct 2 ms 11996 KB Output is correct
8 Correct 3 ms 11868 KB Output is correct
9 Correct 3 ms 11996 KB Output is correct
10 Correct 10 ms 12124 KB Output is correct
11 Correct 43 ms 13000 KB Output is correct
12 Correct 4 ms 14680 KB Output is correct
13 Correct 4 ms 14564 KB Output is correct
14 Correct 5 ms 14684 KB Output is correct
15 Correct 14 ms 15096 KB Output is correct
16 Correct 64 ms 15760 KB Output is correct
17 Correct 33 ms 54456 KB Output is correct
18 Correct 35 ms 54444 KB Output is correct
19 Correct 35 ms 54968 KB Output is correct
20 Correct 53 ms 54712 KB Output is correct
21 Correct 126 ms 55984 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 7 ms 12124 KB Output is correct
3 Correct 24 ms 12724 KB Output is correct
4 Correct 45 ms 13248 KB Output is correct
5 Correct 9 ms 15920 KB Output is correct
6 Correct 12 ms 15512 KB Output is correct
7 Correct 33 ms 16012 KB Output is correct
8 Correct 60 ms 16528 KB Output is correct
9 Correct 21 ms 33428 KB Output is correct
10 Correct 27 ms 33428 KB Output is correct
11 Correct 56 ms 33792 KB Output is correct
12 Correct 95 ms 34308 KB Output is correct
13 Correct 41 ms 55300 KB Output is correct
14 Correct 51 ms 55552 KB Output is correct
15 Correct 75 ms 55856 KB Output is correct
16 Correct 121 ms 56576 KB Output is correct
17 Correct 126 ms 56328 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 55728 KB Output is correct
2 Correct 169 ms 58584 KB Output is correct
3 Correct 157 ms 58484 KB Output is correct
4 Correct 167 ms 58076 KB Output is correct
5 Correct 172 ms 58124 KB Output is correct
6 Correct 136 ms 58024 KB Output is correct
7 Correct 188 ms 63656 KB Output is correct
8 Correct 161 ms 63528 KB Output is correct
9 Correct 166 ms 63716 KB Output is correct
10 Correct 172 ms 63484 KB Output is correct
11 Correct 181 ms 63892 KB Output is correct
12 Correct 151 ms 61740 KB Output is correct
13 Correct 175 ms 71936 KB Output is correct
14 Correct 190 ms 72616 KB Output is correct
15 Correct 173 ms 72020 KB Output is correct
16 Correct 177 ms 72124 KB Output is correct
17 Correct 179 ms 70912 KB Output is correct
18 Correct 157 ms 65140 KB Output is correct
19 Correct 194 ms 72360 KB Output is correct
20 Correct 175 ms 72192 KB Output is correct
21 Correct 194 ms 72204 KB Output is correct
22 Correct 190 ms 72448 KB Output is correct
23 Correct 184 ms 70652 KB Output is correct
24 Correct 159 ms 65432 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11868 KB Output is correct
2 Correct 2 ms 11948 KB Output is correct
3 Correct 2 ms 11928 KB Output is correct
4 Correct 2 ms 11868 KB Output is correct
5 Correct 2 ms 11868 KB Output is correct
6 Correct 2 ms 11960 KB Output is correct
7 Correct 2 ms 11868 KB Output is correct
8 Correct 2 ms 11868 KB Output is correct
9 Correct 2 ms 11868 KB Output is correct
10 Correct 3 ms 11868 KB Output is correct
11 Correct 2 ms 11868 KB Output is correct
12 Correct 3 ms 11868 KB Output is correct
13 Correct 2 ms 11868 KB Output is correct
14 Correct 2 ms 11992 KB Output is correct
15 Correct 3 ms 11864 KB Output is correct
16 Correct 2 ms 11864 KB Output is correct
17 Correct 2 ms 11868 KB Output is correct
18 Correct 2 ms 11868 KB Output is correct
19 Correct 5 ms 12000 KB Output is correct
20 Correct 5 ms 11996 KB Output is correct
21 Correct 6 ms 12124 KB Output is correct
22 Correct 5 ms 12124 KB Output is correct
23 Correct 7 ms 14656 KB Output is correct
24 Correct 8 ms 14932 KB Output is correct
25 Correct 7 ms 14940 KB Output is correct
26 Correct 8 ms 15452 KB Output is correct
27 Correct 2 ms 11868 KB Output is correct
28 Correct 2 ms 11868 KB Output is correct
29 Correct 3 ms 11868 KB Output is correct
30 Correct 8 ms 12124 KB Output is correct
31 Correct 31 ms 13128 KB Output is correct
32 Correct 2 ms 11868 KB Output is correct
33 Correct 2 ms 11996 KB Output is correct
34 Correct 3 ms 11868 KB Output is correct
35 Correct 3 ms 11996 KB Output is correct
36 Correct 10 ms 12124 KB Output is correct
37 Correct 43 ms 13000 KB Output is correct
38 Correct 4 ms 14680 KB Output is correct
39 Correct 4 ms 14564 KB Output is correct
40 Correct 5 ms 14684 KB Output is correct
41 Correct 14 ms 15096 KB Output is correct
42 Correct 64 ms 15760 KB Output is correct
43 Correct 33 ms 54456 KB Output is correct
44 Correct 35 ms 54444 KB Output is correct
45 Correct 35 ms 54968 KB Output is correct
46 Correct 53 ms 54712 KB Output is correct
47 Correct 126 ms 55984 KB Output is correct
48 Correct 3 ms 12120 KB Output is correct
49 Correct 7 ms 12124 KB Output is correct
50 Correct 24 ms 12724 KB Output is correct
51 Correct 45 ms 13248 KB Output is correct
52 Correct 9 ms 15920 KB Output is correct
53 Correct 12 ms 15512 KB Output is correct
54 Correct 33 ms 16012 KB Output is correct
55 Correct 60 ms 16528 KB Output is correct
56 Correct 21 ms 33428 KB Output is correct
57 Correct 27 ms 33428 KB Output is correct
58 Correct 56 ms 33792 KB Output is correct
59 Correct 95 ms 34308 KB Output is correct
60 Correct 41 ms 55300 KB Output is correct
61 Correct 51 ms 55552 KB Output is correct
62 Correct 75 ms 55856 KB Output is correct
63 Correct 121 ms 56576 KB Output is correct
64 Correct 126 ms 56328 KB Output is correct
65 Correct 154 ms 55728 KB Output is correct
66 Correct 169 ms 58584 KB Output is correct
67 Correct 157 ms 58484 KB Output is correct
68 Correct 167 ms 58076 KB Output is correct
69 Correct 172 ms 58124 KB Output is correct
70 Correct 136 ms 58024 KB Output is correct
71 Correct 188 ms 63656 KB Output is correct
72 Correct 161 ms 63528 KB Output is correct
73 Correct 166 ms 63716 KB Output is correct
74 Correct 172 ms 63484 KB Output is correct
75 Correct 181 ms 63892 KB Output is correct
76 Correct 151 ms 61740 KB Output is correct
77 Correct 175 ms 71936 KB Output is correct
78 Correct 190 ms 72616 KB Output is correct
79 Correct 173 ms 72020 KB Output is correct
80 Correct 177 ms 72124 KB Output is correct
81 Correct 179 ms 70912 KB Output is correct
82 Correct 157 ms 65140 KB Output is correct
83 Correct 194 ms 72360 KB Output is correct
84 Correct 175 ms 72192 KB Output is correct
85 Correct 194 ms 72204 KB Output is correct
86 Correct 190 ms 72448 KB Output is correct
87 Correct 184 ms 70652 KB Output is correct
88 Correct 159 ms 65432 KB Output is correct
89 Correct 153 ms 57852 KB Output is correct
90 Correct 189 ms 57820 KB Output is correct
91 Correct 162 ms 60580 KB Output is correct
92 Correct 164 ms 60560 KB Output is correct
93 Correct 163 ms 65820 KB Output is correct
94 Correct 161 ms 64256 KB Output is correct
95 Correct 200 ms 67840 KB Output is correct
96 Correct 173 ms 65472 KB Output is correct
97 Correct 167 ms 67772 KB Output is correct
98 Correct 169 ms 71212 KB Output is correct
99 Correct 173 ms 66688 KB Output is correct
100 Correct 190 ms 66680 KB Output is correct