제출 #623449

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
623449		pliam	Dynamic Diameter (CEOI19_diameter)	C++14	49 / 100	4170 ms	183068 KiB

diameter

#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);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27