제출 #1248253

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1248253		cpdreamer	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	2548 ms	34856 KiB

diameter

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define V vector
#define pb push_back
#define all(v) v.begin(),v.end()
const long long MOD=1e9+7;
#define P pair
void file() {
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
}
int up[(int)1e5+1][20];
V<P<int,ll>>adj[(int)1e5+1];
int l[(int)1e5+1];
int r[(int)1e5+1];
int l1[(int)1e5+1];
int r1[(int)1e5+1];
int f[(int)1e5+1];
ll dep[(int)1e5+1];
int d[(int)1e5+1];
int e1[(int)1e5+1];
int e2[(int)1e5+1];
ll ew[(int)1e5+1];
V<int>leaf;
int cnt=0;
int c=0;
void dfs(int n,int p) {
    int lb=INT_MAX,rb=INT_MIN;
    f[n]=c;
    l1[n]=c;
    for (int k=0;k<20;k++) {
        if (k==0) {
            up[n][0]=p;
        }
        else {
            up[n][k]=up[up[n][k-1]][k-1];
        }
        if (up[n][k]==-1) {
            break;
        }
    }
    for (auto [u,w]:adj[n]) {
        if (u==p)continue;
        dep[u]=dep[n]+w;
        d[u]=d[n]+1;
        c++;
        dfs(u,n);
        lb=min(lb,l[u]);
        rb=max(rb,r[u]);
    }
    if (lb==INT_MAX) {
        l[n]=cnt;
        r[n]=cnt;
        cnt++;
        leaf.pb(n);
    }
    else {
        l[n]=lb;
        r[n]=rb;
    }
    r1[n]=c;
}
int kth(int n,int k) {
    int cur=n;
    for (int i=0;i<20;i++) {
        if (((1<<i)&k)!=0) {
            cur=up[cur][i];
        }
    }
    return cur;
}
int lca(int a,int b) {
    if (d[a]<d[b]) {
        swap(a,b);
    }
    a=kth(a,d[a]-d[b]);
    if (a==b) {
        return a;
    }
    for (int j=19;j>=0;j--) {
        if (up[a][j]!=up[b][j]) {
            a=up[a][j];
            b=up[b][j];
        }
    }
    return up[a][0];
}
struct path {
    ll ans;
    int x;
    int y;
    int l;
};
bool cus(path a,path b) {
    return a.ans>b.ans;
}
struct seggy {
private:
    struct node {
        ll d;
    };
    node merge(node a,node b) {
        return {a.d+b.d};
    }
    node single(int v) {
        return {dep[v]};
    }
    node neutral={0LL};
public:
    int size;
    V<node>query;
    void init(int n) {
        size=1;
        while (size<n)size*=2;
        query.assign(2*size,neutral);
    }
    void set(int l,int r,ll v,int x,int lx,int rx) {
        if (lx>=r || rx<=l) {
            return;
        }
        if (l<=lx && rx<=r) {
            query[x]=merge(query[x],{v});
            return;
        }
        int m=(lx+rx)/2;
        set(l,r,v,2*x+1,lx,m);
        set(l,r,v,2*x+2,m,rx);
    }
    void set(int l,int r,ll v) {
        set(l,r,v,0,0,size);
    }
    node calc(int i,int x,int lx,int rx) {
        if (rx-lx==1) {
            return query[x];
        }
        int m=(lx+rx)/2;
        if (i<m) {
            return merge(query[x],calc(i,2*x+1,lx,m));
        }
        return merge(query[x],calc(i,2*x+2,m,rx));
    }
    ll calc(int i) {
        return calc(i,0,0,size).d;
    }
};
seggy euler;
struct segtree {
private:
    struct node {
        ll ans;
        int nd[3];
        ll mx;
    };
    node neutral={-1};
    node single(int v) {
        return {0LL,{v,v,v},dep[v]};
    }
    node merge(node a,node b) {
        if (a.ans==-1)return b;
        if (b.ans==-1)return a;
        V<path>vp;
        for (int i=0;i<2;i++) {
            for (int j=0;j<2;j++) {
                int x=a.nd[i];
                int y=b.nd[j];
                int l=lca(x,y);
                ll ans=euler.calc(f[x])+euler.calc(f[y])-2*euler.calc(f[l]);
                vp.pb({ans,x,y,l});
            }
        }
        vp.pb({a.ans,a.nd[0],a.nd[1],a.nd[2]});
        vp.pb({b.ans,b.nd[0],b.nd[1],b.nd[2]});
        sort(all(vp),cus);
        return {vp[0].ans,{vp[0].x,vp[0].y,vp[0].l},max(a.mx,b.mx)};
    }
    node modification(node a,ll v) {
        node b=a;
        b.mx+=v;
        return b;
    }

public:
    int size;
    V<node>query;
    V<ll>op;
    void init(int n) {
        size=1;
        while (size<n)size*=2;
        query.assign(2*size,neutral);
        op.assign(2*size,0LL);
    }
    void build(V<int>&a,int x,int lx,int rx) {
        if (rx-lx==1) {
            if (lx<a.size()) {
                query[x]=single(a[lx]);
            }
            return;
        }
        int m=(lx+rx)/2;
        build(a,2*x+1,lx,m);
        build(a,2*x+2,m,rx);
        query[x]=merge(query[2*x+1],query[2*x+2]);
    }
    void build(V<int>&a) {
        build(a,0,0,size);
    }
    void set(int l,int r,ll v,int x,int lx,int rx) {
        if (lx>=r || rx<=l) {
            return;
        }
        if (l<=lx && rx<=r) {
            op[x]+=v;
            query[x]=modification(query[x],v);
            return;
        }
        int m=(lx+rx)/2;
        set(l,r,v,2*x+1,lx,m);
        set(l,r,v,2*x+2,m,rx);
        query[x]=modification(merge(query[2*x+1],query[2*x+2]),op[x]);
    }
    void set(int l,int r,ll v) {
        set(l,r,v,0,0,size);
    }
    ll calc() {
        return max(query[0].ans,query[0].mx);
    }
};
void solve() {
    int n,q;
    ll x;
    cin>>n>>q>>x;
    for (int i=0;i<n-1;i++) {
        int a,b;
        ll w;
        cin>>a>>b>>w;
        adj[a].pb({b,w});
        adj[b].pb({a,w});
        e1[i]=a,e2[i]=b,ew[i]=w;
    }
    dep[1]=0LL;
    dfs(1,-1);
    euler.init(n);
    for (int i=1;i<=n;i++) {
        euler.set(f[i],f[i]+1,dep[i]);
    }
    segtree tree;
    tree.init((int)leaf.size());
    tree.build(leaf);
    ll last=0;
    while (q--) {
        ll de;
        ll dw;
        cin>>de>>dw;
        de=(de+last)%(n-1);
        dw=(dw+last)%x;
        int nd;
        if (d[e1[de]]<d[e2[de]]) {
            nd=e2[de];
        }
        else
            nd=e1[de];
        euler.set(l1[nd],r1[nd]+1,dw-ew[de]);
        tree.set(l[nd],r[nd]+1,dw-ew[de]);
        ew[de]=dw;
        last=tree.calc();
        cout<<last<<endl;
    }
}
int main(){
    //file();
    solve();

}

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

diameter.cpp: In function 'void file()':
diameter.cpp:10:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     freopen("input.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:11:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     freopen("output.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 27 / 27