oj.uz

Submission #884728

# Submission time Handle Problem Language Result Execution time Memory
884728 2023-12-08T09:16:58 Z Alish Dynamic Diameter (CEOI19_diameter) C++17
0 / 100
 14 ms 7624 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;
        dfs(r);
        cout<<di.F<<endl;
        la=di.F;

    }

}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 24.0

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

Subtask #6
0 / 27.0

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