oj.uz

답안 #697202

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
697202 2023-02-08T21:12:46 Z NintsiChkhaidze Dynamic Diameter (CEOI19_diameter) C++17
0 / 100
 140 ms 62260 KB 
#include <bits/stdc++.h>
#define ll long long
#define left (h<<1),l,((l+r)>>1)
#define right ((h<<1)|1),((l+r)>>1) + 1,r
#define pb push_back
#define pii pair<int,int>
#define s second
#define f first
#define int ll // ?
using namespace std;

const int N = 200005,M=65,inf=1e18; // ?
vector <pii> v[N];
vector <int> comp[M];
multiset <int> st[M];
int vis[N],xi[N],yi[N],wi[N];
int id,cnt,n,centroid,CH;
int tin[M][N],tout[M][N],PAR[M][N],dep[M][N];
int t[M][4*N],add[M][4*N];

void push(int k,int h){
    if (add[k][h] == 0) return;
    add[k][h*2] += add[k][h];
    t[k][h*2] += add[k][h];
    add[k][h*2+1] += add[k][h];
    t[k][h*2+1] += add[k][h];
    add[k][h] = 0;
}
void upd(int k,int h,int l,int r,int L,int R,int val){
    if (r < L || R < l) return;
    if (L <= l && r <= R){
        t[k][h] += val;
        add[k][h] += val;
        return;
    }
    push(k,h);
    upd(k,left,L,R,val);
    upd(k,right,L,R,val);
    t[k][h] = max(t[k][h*2],t[k][h*2+1]);
}

int get(int k,int h,int l,int r,int L,int R){
    if (r < L || R < l) return 0;
    if (L <= l && r <= R) return t[k][h];
    push(k,h);
    return max(get(k,left,L,R),get(k,right,L,R));
}
int dfs(int x,int par,int root,int m){
    int s = 1;
    for (auto [to,idx]: v[x])
        if (to != par && !vis[to]) s += dfs(to,x,root, m);
    if (centroid == -1 && (x == root || s*2 >= m)) centroid = x;
    return s;
}

void DFS(int x,int par){
    tin[id][x] = ++cnt;
    comp[id].pb(x);
    PAR[id][x] = CH;
    for (auto [to,q]: v[x]){
        if (to == par || vis[to]) continue;
        dep[id][to] = dep[id][x] + 1; 
        if (dep[id][x] == 1) CH = to;
        DFS(to,x);
        upd(id,1,1,n,tin[id][to],tout[id][to],+wi[q]);
        if (dep[id][x] == 1) st[id].insert(get(id,1,1,n,tin[id][to],tout[id][to]));
    }

    tout[id][x] = cnt;
}
void C(int x,int m){
    centroid = -1;
    dfs(x, x, x, m);
    vis[centroid] = 1;

    ++id; cnt=0;
    dep[id][centroid] = 1;
    DFS(centroid,centroid);

    for (auto [to,idx]: v[centroid])
        if (!vis[to]) C(to,m/2);
}
signed main(){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    
    int q,W;
    cin>>n>>q>>W;

    for (int i = 1; i < n; i++){
        cin>>xi[i]>>yi[i]>>wi[i];
        v[xi[i]].pb({yi[i],i});
        v[yi[i]].pb({xi[i],i});
    }

    C(1,n);

    int last=0;
    while (q--){
        int d,len;
        cin>>d>>len;
        d = (d + last)%(n-1) + 1;
        len = (len + last)%W;

        int x = xi[d],y =yi[d],delta = len - wi[d]; 
        wi[d] = len;

        for (int i = 1; i <= id; i++){
            if (comp[i].size()<2 || !dep[i][x] || !dep[i][y]) continue;
            
            if (!dep[i][x] || (dep[i][x] < dep[i][y])){
                int parent = PAR[i][y];
                st[i].erase(st[i].find(get(i,1,1,n,tin[i][parent],tout[i][parent])));
                upd(i,1,1,n,tin[i][y],tout[i][y],delta);
                st[i].insert(get(i,1,1,n,tin[i][parent],tout[i][parent]));
            }
            else if (!dep[i][y] || (dep[i][y] < dep[i][x])){
                int parent = PAR[i][x]; 
                st[i].erase(st[i].find(get(i,1,1,n,tin[i][parent],tout[i][parent])));
                upd(i,1,1,n,tin[i][x],tout[i][x],delta);
                st[i].insert(get(i,1,1,n,tin[i][parent],tout[i][parent]));
            }
        }

        int ans1=0;
        for (int i = 1; i <= id; i++){
            if (!st[i].size()) continue;
            int ans=0;
            if (st[i].size() == 1) ans=*st[i].begin();
            else {
                multiset <int> :: iterator it = --st[i].end(); --it;
                ans = *(--st[i].end()) + *it;
            }
            ans1=max(ans1,ans);
        }
        
        cout<<ans1<<"\n";
        last=ans1;
    }
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 3 ms 5416 KB Output is correct
3 Correct 4 ms 5416 KB Output is correct
4 Correct 3 ms 5412 KB Output is correct
5 Correct 3 ms 5416 KB Output is correct
6 Correct 3 ms 5332 KB Output is correct
7 Correct 3 ms 6740 KB Output is correct
8 Correct 4 ms 6792 KB Output is correct
9 Correct 3 ms 6868 KB Output is correct
10 Correct 3 ms 6824 KB Output is correct
11 Correct 4 ms 6868 KB Output is correct
12 Correct 4 ms 6996 KB Output is correct
13 Runtime error 12 ms 7764 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 3 ms 5416 KB Output is correct
3 Correct 4 ms 5416 KB Output is correct
4 Correct 3 ms 5412 KB Output is correct
5 Correct 3 ms 5416 KB Output is correct
6 Correct 3 ms 5332 KB Output is correct
7 Correct 3 ms 6740 KB Output is correct
8 Correct 4 ms 6792 KB Output is correct
9 Correct 3 ms 6868 KB Output is correct
10 Correct 3 ms 6824 KB Output is correct
11 Correct 4 ms 6868 KB Output is correct
12 Correct 4 ms 6996 KB Output is correct
13 Runtime error 12 ms 7764 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5588 KB Output is correct
2 Correct 3 ms 5588 KB Output is correct
3 Correct 4 ms 5684 KB Output is correct
4 Correct 15 ms 5844 KB Output is correct
5 Correct 58 ms 6720 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Runtime error 15 ms 7080 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 9136 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 140 ms 62260 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 3 ms 5416 KB Output is correct
3 Correct 4 ms 5416 KB Output is correct
4 Correct 3 ms 5412 KB Output is correct
5 Correct 3 ms 5416 KB Output is correct
6 Correct 3 ms 5332 KB Output is correct
7 Correct 3 ms 6740 KB Output is correct
8 Correct 4 ms 6792 KB Output is correct
9 Correct 3 ms 6868 KB Output is correct
10 Correct 3 ms 6824 KB Output is correct
11 Correct 4 ms 6868 KB Output is correct
12 Correct 4 ms 6996 KB Output is correct
13 Runtime error 12 ms 7764 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -