oj.uz

답안 #623449

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
623449 2022-08-05T15:44:26 Z pliam Dynamic Diameter (CEOI19_diameter) C++14
49 / 100
 4170 ms 183068 KB 
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
typedef long long ll;
typedef pair<ll,int> pli;
typedef pair<pli,pli> ppli;
#define INF 1000005

int Q;
ll N,W;
vector<int> adj[MAXN];
vector<pair<int,int>> edges;
map<pair<int,int>,ll> w;//each edge is stored with two elements (order of the pair)

ll last;

//centroid decomposition
vector<int> ch[MAXN];
int par[MAXN],sz[MAXN],r[MAXN];
map<pair<int,int>,vector<pair<int,int>>> edge_info;//edge->(centroid,order of child), for the ancestors (O(logN)) worst-case
vector<pair<int,int>> leaf_range[MAXN];//range of leaves for each centroid and for each vertex(vertices are in dfs order)
vector<ll> st[MAXN];//max segment tree for each centroid
vector<ll> lazy[MAXN];
vector<ll> chp_sub[MAXN];//dfs-order->head order
int num_leaf[MAXN];//for each centroid number of leaves
int curcen,dfs_order,leaf_order;
ll leaf_dist[MAXN];//temporary for build centroid st
set<pli,greater<pli>> mxpaths[MAXN];
set<pli,greater<pli>> diams;//holds for each centroid the diameter 
vector<ll> order_ch[MAXN];

//segment tree
void build(int c,int v,int start,int end){
    if(start==end){
        st[c][v]=leaf_dist[start];
        lazy[c][v]=0;
        return;
    }
    int mid=(start+end)/2;
    build(c,2*v,start,mid);
    build(c,2*v+1,mid+1,end);
    st[c][v]=max(st[c][2*v],st[c][2*v+1]);
}

void update(int c,int from,int to,ll val,int v,int start,int end){
    if(start==from&&end==to){
        st[c][v]+=val;
        lazy[c][v]+=val;
        return;
    }
    int mid=(start+end)/2;
    //propagate
    if(lazy[c][v]){
        update(c,start,mid,lazy[c][v],2*v,start,mid);
        update(c,mid+1,end,lazy[c][v],2*v+1,mid+1,end);
        lazy[c][v]=0;
    }
    if(to<=mid){
        update(c,from,to,val,2*v,start,mid);
    }else if(from>mid){
        update(c,from,to,val,2*v+1,mid+1,end);
    }else{
        update(c,from,mid,val,2*v,start,mid);
        update(c,mid+1,to,val,2*v+1,mid+1,end);
    }
    st[c][v]=max(st[c][2*v],st[c][2*v+1]);
}

ll query(int c,int from,int to,int v,int start,int end){//for full query: st[c][1]
    if(start==from&&end==to){
        return st[c][v];
    }
    int mid=(start+end)/2;
    //propagate
    if(lazy[c][v]){
        update(c,start,mid,lazy[c][v],2*v,start,mid);
        update(c,mid+1,end,lazy[c][v],2*v+1,mid+1,end);
        lazy[c][v]=0;
    }
    if(to<=mid){
        return query(c,from,to,2*v,start,mid);
    }else if(from>mid){
        return query(c,from,to,2*v+1,mid+1,end);
    }else{
        return max(query(c,from,mid,2*v,start,mid),query(c,mid+1,to,2*v+1,mid+1,end));
    }
}

void dfs_sz(int curr,int p){
    sz[curr]=1;
    for(int to:adj[curr]){
        if(to==p||r[to]) continue;
        dfs_sz(to,curr);
        sz[curr]+=sz[to];
    }
}
int centroid(int curr,int p,int n){
    for(int to:adj[curr]){
        if(to==p||r[to]) continue;
        if(2*sz[to]>n) return centroid(to,curr,n);
    }
    return curr;
}

int dfs_cen(int curr,int p,int d,int s,int ch_p){//returns dfs order
    int ord=dfs_order++;
    chp_sub[curcen].push_back(ch_p?ord:s);
    leaf_range[curcen].push_back({INF,0});//placeholder
    if(p!=-1){
        edge_info[{curr,p}].push_back({curcen,ord});
        edge_info[{p,curr}].push_back({curcen,ord});
    }
    int leaf=1;
    for(int to:adj[curr]){
        if(to==p||r[to]) continue;
        leaf=0;
        int ordch=dfs_cen(to,curr,d+w[{curr,to}],ch_p?ord:s,p==-1);
        if(p==-1) order_ch[curcen].push_back(ordch);
        leaf_range[curcen][ord].first=min(leaf_range[curcen][ord].first,leaf_range[curcen][ordch].first);
        leaf_range[curcen][ord].second=max(leaf_range[curcen][ord].second,leaf_range[curcen][ordch].second);
    }
    if(leaf){
        leaf_order++;
        leaf_dist[leaf_order]=d;
        leaf_range[curcen][ord]={leaf_order,leaf_order};
    }
    return ord;
}

ll diam(int cen,int ch){
    return query(cen,leaf_range[cen][ch].first,leaf_range[cen][ch].second,1,1,num_leaf[cen]);
}

ll tdiam(int cen){
    ll d=0;
    if(!mxpaths[cen].empty()){
        auto it=mxpaths[cen].begin();
        d+=it->first;
        if(mxpaths[cen].size()>=2){
            it++;
            d+=it->first;
        }
    }
    return d;
}

//returns centroid
int centroid_decomp(int curr,int p=-1){
    dfs_sz(curr,-1);
    int cen=centroid(curr,-1,sz[curr]);
    curcen=cen;
    //now prepare stuff this centroid
    dfs_order=0;
    leaf_order=0;
    dfs_cen(cen,-1,0,0,1);
    st[cen]=vector<ll>(4*leaf_order,0);
    lazy[cen]=vector<ll>(4*leaf_order,0);
    num_leaf[cen]=leaf_order;
    build(cen,1,1,num_leaf[cen]);
    for(int to:order_ch[cen]){
        mxpaths[cen].insert({diam(cen,to),to});
    }
    diams.insert({tdiam(cen),cen});
    //--
    r[cen]=1;
    par[cen]=p;
    for(int to:adj[cen]){
        if(r[to]) continue;
        int c_to=centroid_decomp(to,cen);
        ch[cen].push_back(c_to);
    }
    
    return cen;
}

ll query_cen(int a,int b,ll we){
    ll diff=we-w[{a,b}];
    w[{a,b}]=w[{b,a}]=we;
    auto changes=edge_info[{a,b}];
    for(auto p:changes){
        int cen,ord;
        tie(cen,ord)=p;
        diams.erase({tdiam(cen),cen});
        mxpaths[cen].erase({diam(cen,chp_sub[cen][ord]),chp_sub[cen][ord]});
        update(cen,leaf_range[cen][ord].first,leaf_range[cen][ord].second,diff,1,1,num_leaf[cen]);
        mxpaths[cen].insert({diam(cen,chp_sub[cen][ord]),chp_sub[cen][ord]});
        diams.insert({tdiam(cen),cen});
    }
    return diams.begin()->first;
}

void initialize(){
    centroid_decomp(1);
}

int main(){
    //freopen("ddiameter.in","r",stdin);
    scanf("%d%d%lld",&N,&Q,&W);
    for(int i=0;i<N-1;i++){
        int a,b;
        ll c;
        scanf("%d%d%lld",&a,&b,&c);
        edges.push_back({a,b});
        adj[a].push_back(b);
        adj[b].push_back(a);
        w[{a,b}]=c;
        w[{b,a}]=c;
    }
    initialize();
    while(Q--){
        ll d;ll e;
        scanf("%lld%lld",&d,&e);
        d=(d+last)%(N-1);
        e=(e+last)%W;
        last=query_cen(edges[d].first,edges[d].second,e);
        printf("%lld\n",last);
    }
}

Compilation message

diameter.cpp: In function 'int main()':
diameter.cpp:198:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
  198 |     scanf("%d%d%lld",&N,&Q,&W);
      |            ~^        ~~
      |             |        |
      |             int*     ll* {aka long long int*}
      |            %lld
diameter.cpp:198:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  198 |     scanf("%d%d%lld",&N,&Q,&W);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
diameter.cpp:202:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  202 |         scanf("%d%d%lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
diameter.cpp:212:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  212 |         scanf("%lld%lld",&d,&e);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 21460 KB Output is correct
2 Correct 12 ms 21460 KB Output is correct
3 Correct 11 ms 21460 KB Output is correct
4 Correct 12 ms 21456 KB Output is correct
5 Correct 13 ms 21460 KB Output is correct
6 Correct 11 ms 21460 KB Output is correct
7 Correct 11 ms 21460 KB Output is correct
8 Correct 13 ms 21464 KB Output is correct
9 Correct 11 ms 21460 KB Output is correct
10 Correct 13 ms 21476 KB Output is correct
11 Correct 11 ms 21460 KB Output is correct
12 Correct 11 ms 21468 KB Output is correct
13 Correct 12 ms 21456 KB Output is correct
14 Correct 14 ms 21456 KB Output is correct
15 Correct 12 ms 21460 KB Output is correct
16 Correct 14 ms 21456 KB Output is correct
17 Correct 12 ms 21452 KB Output is correct
18 Correct 12 ms 21460 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 21460 KB Output is correct
2 Correct 12 ms 21460 KB Output is correct
3 Correct 11 ms 21460 KB Output is correct
4 Correct 12 ms 21456 KB Output is correct
5 Correct 13 ms 21460 KB Output is correct
6 Correct 11 ms 21460 KB Output is correct
7 Correct 11 ms 21460 KB Output is correct
8 Correct 13 ms 21464 KB Output is correct
9 Correct 11 ms 21460 KB Output is correct
10 Correct 13 ms 21476 KB Output is correct
11 Correct 11 ms 21460 KB Output is correct
12 Correct 11 ms 21468 KB Output is correct
13 Correct 12 ms 21456 KB Output is correct
14 Correct 14 ms 21456 KB Output is correct
15 Correct 12 ms 21460 KB Output is correct
16 Correct 14 ms 21456 KB Output is correct
17 Correct 12 ms 21452 KB Output is correct
18 Correct 12 ms 21460 KB Output is correct
19 Correct 40 ms 22552 KB Output is correct
20 Correct 35 ms 22568 KB Output is correct
21 Correct 41 ms 22624 KB Output is correct
22 Correct 40 ms 22564 KB Output is correct
23 Correct 92 ms 27004 KB Output is correct
24 Correct 81 ms 27620 KB Output is correct
25 Correct 103 ms 28068 KB Output is correct
26 Correct 90 ms 28048 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 21460 KB Output is correct
2 Correct 12 ms 21460 KB Output is correct
3 Correct 13 ms 21460 KB Output is correct
4 Correct 26 ms 21612 KB Output is correct
5 Correct 83 ms 22492 KB Output is correct
6 Correct 12 ms 21392 KB Output is correct
7 Correct 15 ms 21844 KB Output is correct
8 Correct 12 ms 21844 KB Output is correct
9 Correct 14 ms 21840 KB Output is correct
10 Correct 51 ms 22112 KB Output is correct
11 Correct 132 ms 23068 KB Output is correct
12 Correct 21 ms 25428 KB Output is correct
13 Correct 22 ms 25428 KB Output is correct
14 Correct 25 ms 25428 KB Output is correct
15 Correct 70 ms 25692 KB Output is correct
16 Correct 235 ms 26828 KB Output is correct
17 Correct 451 ms 100828 KB Output is correct
18 Correct 387 ms 100832 KB Output is correct
19 Correct 340 ms 100912 KB Output is correct
20 Correct 466 ms 101240 KB Output is correct
21 Correct 987 ms 102500 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 22604 KB Output is correct
2 Correct 46 ms 22740 KB Output is correct
3 Correct 186 ms 23164 KB Output is correct
4 Correct 416 ms 24092 KB Output is correct
5 Correct 98 ms 35972 KB Output is correct
6 Correct 138 ms 35884 KB Output is correct
7 Correct 345 ms 36504 KB Output is correct
8 Correct 682 ms 37272 KB Output is correct
9 Correct 472 ms 98884 KB Output is correct
10 Correct 536 ms 99012 KB Output is correct
11 Correct 876 ms 99768 KB Output is correct
12 Correct 1315 ms 100524 KB Output is correct
13 Correct 1010 ms 181508 KB Output is correct
14 Correct 1120 ms 181760 KB Output is correct
15 Correct 1537 ms 182268 KB Output is correct
16 Correct 2134 ms 183068 KB Output is correct
17 Correct 3463 ms 182884 KB Output is correct

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4170 ms 162712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 21460 KB Output is correct
2 Correct 12 ms 21460 KB Output is correct
3 Correct 11 ms 21460 KB Output is correct
4 Correct 12 ms 21456 KB Output is correct
5 Correct 13 ms 21460 KB Output is correct
6 Correct 11 ms 21460 KB Output is correct
7 Correct 11 ms 21460 KB Output is correct
8 Correct 13 ms 21464 KB Output is correct
9 Correct 11 ms 21460 KB Output is correct
10 Correct 13 ms 21476 KB Output is correct
11 Correct 11 ms 21460 KB Output is correct
12 Correct 11 ms 21468 KB Output is correct
13 Correct 12 ms 21456 KB Output is correct
14 Correct 14 ms 21456 KB Output is correct
15 Correct 12 ms 21460 KB Output is correct
16 Correct 14 ms 21456 KB Output is correct
17 Correct 12 ms 21452 KB Output is correct
18 Correct 12 ms 21460 KB Output is correct
19 Correct 40 ms 22552 KB Output is correct
20 Correct 35 ms 22568 KB Output is correct
21 Correct 41 ms 22624 KB Output is correct
22 Correct 40 ms 22564 KB Output is correct
23 Correct 92 ms 27004 KB Output is correct
24 Correct 81 ms 27620 KB Output is correct
25 Correct 103 ms 28068 KB Output is correct
26 Correct 90 ms 28048 KB Output is correct
27 Correct 14 ms 21460 KB Output is correct
28 Correct 12 ms 21460 KB Output is correct
29 Correct 13 ms 21460 KB Output is correct
30 Correct 26 ms 21612 KB Output is correct
31 Correct 83 ms 22492 KB Output is correct
32 Correct 12 ms 21392 KB Output is correct
33 Correct 15 ms 21844 KB Output is correct
34 Correct 12 ms 21844 KB Output is correct
35 Correct 14 ms 21840 KB Output is correct
36 Correct 51 ms 22112 KB Output is correct
37 Correct 132 ms 23068 KB Output is correct
38 Correct 21 ms 25428 KB Output is correct
39 Correct 22 ms 25428 KB Output is correct
40 Correct 25 ms 25428 KB Output is correct
41 Correct 70 ms 25692 KB Output is correct
42 Correct 235 ms 26828 KB Output is correct
43 Correct 451 ms 100828 KB Output is correct
44 Correct 387 ms 100832 KB Output is correct
45 Correct 340 ms 100912 KB Output is correct
46 Correct 466 ms 101240 KB Output is correct
47 Correct 987 ms 102500 KB Output is correct
48 Correct 20 ms 22604 KB Output is correct
49 Correct 46 ms 22740 KB Output is correct
50 Correct 186 ms 23164 KB Output is correct
51 Correct 416 ms 24092 KB Output is correct
52 Correct 98 ms 35972 KB Output is correct
53 Correct 138 ms 35884 KB Output is correct
54 Correct 345 ms 36504 KB Output is correct
55 Correct 682 ms 37272 KB Output is correct
56 Correct 472 ms 98884 KB Output is correct
57 Correct 536 ms 99012 KB Output is correct
58 Correct 876 ms 99768 KB Output is correct
59 Correct 1315 ms 100524 KB Output is correct
60 Correct 1010 ms 181508 KB Output is correct
61 Correct 1120 ms 181760 KB Output is correct
62 Correct 1537 ms 182268 KB Output is correct
63 Correct 2134 ms 183068 KB Output is correct
64 Correct 3463 ms 182884 KB Output is correct
65 Incorrect 4170 ms 162712 KB Output isn't correct
66 Halted 0 ms 0 KB -