oj.uz

Submission #884730

# Submission time Handle Problem Language Result Execution time Memory
884730 2023-12-08T09:19:53 Z Alish Dynamic Diameter (CEOI19_diameter) C++17
24 / 100
 1118 ms 8600 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 = 1e5+23;
vector<pll> g[N];
int st[N], ft[N], tim, pos[N];
vector<pair<pll, ll> > E;
ll seg[4*N], lpz[4*N];
int n, q;
ll h[N];
ll ans[N];


pll di;
void dfs(int v, int p=0){
    di=max(di, {h[v], v});
    for (auto pp: g[v]){
        ll u=pp.F, w=ans[pp.S];
        if(u==p) continue;
        h[u]=h[v]+w;
        dfs(u, v);
    }

}




int main()
{
    fast_io
    cin>>n>>q>>mod;
    if(n>5000 || q>5000) return 0;
    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;
    }


    ll la=0;
    while(q--){
        ll i, w;
        cin>>i>>w;
        i=(i+la)%(n-1);
        w=(w+la)%mod;
        ans[i]=w;
        di={0, 0};
        dfs(1);
        int r=di.S;
        h[r]=0;

        di={0, 0};
        dfs(r);
        cout<<di.F<<endl;
        la=di.F;

    }

}

Subtask #1
11.0 / 11.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7516 KB Output is correct
2 Correct 1 ms 7516 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 1 ms 7768 KB Output is correct
6 Correct 1 ms 7516 KB Output is correct
7 Correct 1 ms 7516 KB Output is correct
8 Correct 1 ms 7516 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 2 ms 7516 KB Output is correct
14 Correct 2 ms 7516 KB Output is correct
15 Correct 2 ms 7516 KB Output is correct
16 Correct 2 ms 7516 KB Output is correct
17 Correct 2 ms 7512 KB Output is correct
18 Correct 2 ms 7516 KB Output is correct
19 Correct 67 ms 7628 KB Output is correct
20 Correct 73 ms 7516 KB Output is correct
21 Correct 81 ms 7516 KB Output is correct
22 Correct 102 ms 7680 KB Output is correct
23 Correct 741 ms 8020 KB Output is correct
24 Correct 892 ms 8276 KB Output is correct
25 Correct 1027 ms 8328 KB Output is correct
26 Correct 1118 ms 8600 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Incorrect 1 ms 7768 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7516 KB Output is correct
2 Incorrect 1 ms 7516 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7516 KB Output is correct
2 Correct 1 ms 7516 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 1 ms 7768 KB Output is correct
6 Correct 1 ms 7516 KB Output is correct
7 Correct 1 ms 7516 KB Output is correct
8 Correct 1 ms 7516 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 2 ms 7516 KB Output is correct
14 Correct 2 ms 7516 KB Output is correct
15 Correct 2 ms 7516 KB Output is correct
16 Correct 2 ms 7516 KB Output is correct
17 Correct 2 ms 7512 KB Output is correct
18 Correct 2 ms 7516 KB Output is correct
19 Correct 67 ms 7628 KB Output is correct
20 Correct 73 ms 7516 KB Output is correct
21 Correct 81 ms 7516 KB Output is correct
22 Correct 102 ms 7680 KB Output is correct
23 Correct 741 ms 8020 KB Output is correct
24 Correct 892 ms 8276 KB Output is correct
25 Correct 1027 ms 8328 KB Output is correct
26 Correct 1118 ms 8600 KB Output is correct
27 Correct 2 ms 7512 KB Output is correct
28 Correct 2 ms 7516 KB Output is correct
29 Correct 2 ms 7516 KB Output is correct
30 Incorrect 1 ms 7768 KB Output isn't correct
31 Halted 0 ms 0 KB -