Submission #198629

#	Time	Username	Problem	Language	Result	Execution time	Memory
198629		arnold518	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	829 ms	61676 KiB

diameter

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const ll INF = 1e18;

struct Edge { int u, v; ll w; };

int N, Q, S;
ll W, ans;
Edge edge[MAXN+10];

vector<pll> adj[MAXN+10];
ll dist[MAXN+10];
vector<int> tour;
int ss[MAXN+10], ee[MAXN+10];

void dfs(int now, int bef, ll dep)
{
    dist[now]=dep;
    tour.push_back(now);
    for(auto nxt : adj[now])
    {
        if(nxt.first==bef) continue;
        dfs(nxt.first, now, dep+nxt.second);
        tour.push_back(now);
    }
}

struct Node
{
    ll aba, ab, ba, a, b;
    Node() : aba(-INF), ab(-INF), ba(-INF), a(-INF), b(-INF) {}
};
Node tree[4*MAXN+10];
ll lazy[4*MAXN+10];

Node operator + (const Node &p, const Node &q)
{
    Node ret;
    ret.aba=max({p.aba, q.aba, p.ab+q.a, p.a+q.ba});
    ret.ab=max({p.ab, q.ab, p.a+q.b});
    ret.ba=max({p.ba, q.ba, p.b+q.a});
    ret.a=max(p.a, q.a);
    ret.b=max(p.b, q.b);
    return ret;
}

void init(int node, int tl, int tr)
{
    if(tl==tr)
    {
        tree[node].a=dist[tour[tl]];
        tree[node].b=-2*dist[tour[tl]];
        tree[node].ab=tree[node].ba=-dist[tour[tl]];
        tree[node].aba=0;
        return;
    }
    int mid=tl+tr>>1;
    init(node*2, tl, mid);
    init(node*2+1, mid+1, tr);
    tree[node]=tree[node*2]+tree[node*2+1];
    lazy[node]=0;
}

void busy(int node, int tl, int tr)
{
    if(lazy[node]==0) return;
    if(tl!=tr) lazy[node*2]+=lazy[node], lazy[node*2+1]+=lazy[node];
    tree[node].ab-=lazy[node];
    tree[node].ba-=lazy[node];
    tree[node].a+=lazy[node];
    tree[node].b-=2*lazy[node];
    lazy[node]=0;
}

void update(int node, int tl, int tr, int l, int r, ll val)
{
    busy(node, tl, tr);
    if(r<tl || tr<l) return;
    if(l<=tl && tr<=r)
    {
        lazy[node]+=val;
        busy(node, tl, tr);
        return;
    }
    int mid=tl+tr>>1;
    update(node*2, tl, mid, l, r, val);
    update(node*2+1, mid+1, tr, l, r, val);
    tree[node]=tree[node*2]+tree[node*2+1];
}

ll query()
{
    busy(1, 1, S);
    return tree[1].aba;
}

int main()
{
    int i, j;

    scanf("%d%d%lld", &N, &Q, &W);
    for(i=0; i<N-1; i++)
    {
        int u, v; ll w;
        scanf("%d%d%lld", &u, &v, &w);
        edge[i]={u, v, w};
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    tour.push_back(-1);
    dfs(1, 0, 0);
    S=tour.size()-1;

    for(i=1; i<=S; i++) ee[tour[i]]=i;
    for(i=S; i>=1; i--) ss[tour[i]]=i;

    for(i=0; i<N-1; i++) if(dist[edge[i].u]>dist[edge[i].v]) swap(edge[i].u, edge[i].v);

    init(1, 1, S);

    while(Q--)
    {
        int d; ll e;
        scanf("%d%lld", &d, &e);
        d=(d+ans)%(N-1);
        e=(e+ans)%W;

        update(1, 1, S, ss[edge[d].v], ee[edge[d].v], e-edge[d].w);
        edge[d].w=e;

        ans=query();
        printf("%lld\n", ans);
    }
}

Compilation message (stderr)

diameter.cpp: In function 'void init(int, int, int)':
diameter.cpp:63:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
diameter.cpp: In function 'void update(int, int, int, int, int, ll)':
diameter.cpp:91:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
diameter.cpp: In function 'int main()':
diameter.cpp:105:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
diameter.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%lld", &N, &Q, &W);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%lld", &u, &v, &w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%lld", &d, &e);
         ~~~~~^~~~~~~~~~~~~~~~~~

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