제출 #884738

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
884738		Arshi	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	233 ms	51944 KiB

diameter

/**********************GOD**********************/

#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <iterator>
#include <map>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll , ll> pll;

#define len                 length()
#define MP                  make_pair
#define fs                  first
#define sc                  second
#define pb                  push_back
#define all(x)              x.begin() , x.end()
#define kill(x)             cout << x , exit(0)
#define lid                 (id << 1)
#define rid                 (lid | 1)
#define mid                 ((r + l) >> 1)

const ll MXN = 2e5 + 4;
const ll LOG = 23;

ll n, q, lim;
ll tim, lst;

set<pll> cnd;
vector<pair<pll, ll>> E;
vector<pll> adj[MXN];
ll st[MXN], sz[MXN];
ll dp[MXN];
ll seg[MXN << 2], lz[MXN << 2];
ll par[MXN][LOG];
ll h[MXN];
ll ans[MXN];

ll GetPar(ll v, ll k)
{
    for(ll i = 0; i < LOG; i ++)
        if(k >> i & 1)
            v = par[v][i];
    return v;
}

void DFS(ll v = 1, ll p = 0)
{
    st[v] = ++ tim; sz[v] = 1;
    par[v][0] = p;
    for(ll i = 1; i < LOG; i ++)
        par[v][i] = par[par[v][i - 1]][i - 1];
    for(auto[u, _] : adj[v]) {
        if(u == p)
            continue;
        h[u] = h[v] + 1;
        DFS(u, v);
        sz[v] += sz[u];
    }
}

void dfs(ll v, ll p = 0)
{
    for(auto[u, i] : adj[v]) {
        if(u == p)
            continue;
        dp[u] = dp[v] + E[i].sc;
        dfs(u, v);
    }
}

void Build(ll id = 1, ll l = 1, ll r = n + 1)
{
    if(r - l < 2) {
        seg[id] = dp[l];
        return;
    }
    Build(lid, l, mid);
    Build(rid, mid, r);
    seg[id] = max(seg[lid], seg[rid]);
}

void Shift(ll id, ll l, ll r)
{
    lz[lid] += lz[id]; lz[rid] += lz[id];
    seg[lid] += lz[id]; seg[rid] += lz[id];
    lz[id] = 0;
}

void Update(ll ql, ll qr, ll v, ll id = 1, ll l = 1, ll r = n + 1)
{
    if(qr <= l || r <= ql)
        return;
    if(ql <= l && r <= qr) {
        seg[id] += v;
        return;
    }
    Shift(id, l, r);
    Update(ql, qr, v, lid, l, mid);
    Update(ql, qr, v, rid, mid, r);
    seg[id] = max(seg[lid], seg[rid]);
}

ll Get(ll ql, ll qr, ll id = 1, ll l = 1, ll r = n + 1)
{
    if(qr <= l || r <= ql)
        return 0;
    if(ql <= l && r <= qr)
        return seg[id];
    Shift(id, l, r);
    return max(Get(ql, qr, lid, l, mid), Get(ql, qr, rid, mid, r));
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> q >> lim;
    for(ll i = 1; i < n; i ++) {
        ll v, u, w; cin >> v >> u >> w;
        E.pb({{v, u}, w});
        adj[v].pb({u, i - 1});
        adj[u].pb({v, i - 1});
    }

    DFS();
    dfs(1);
    Build();

    for(ll i = 0; i < adj[1].size(); i ++) {
        ll u = adj[1][i].fs;
        ll x = Get(st[u], st[u] + sz[u]);
        ans[u] = x;
        cnd.insert({-ans[u], u});
    }

    while(q --) {
        ll x, y; cin >> x >> y;
        x = (x + lst) % (n - 1);
        y = (y + lst) % lim;
        auto[v, u] = E[x].fs;
        if(st[v] < st[u])
            swap(v, u);
        ll c = GetPar(v, h[v] - 1);
        cnd.erase({-ans[c], c});
        Update(st[v], st[v] + sz[v], y - E[x].sc);
        E[x].sc = y;
        ans[c] = Get(st[c], st[c] + sz[c]);
        cnd.insert({-ans[c], c});
        if(cnd.size() == 1)
            lst = -(*cnd.begin()).fs;
        else {
            auto itr = cnd.begin();
            lst = -(*itr).fs;
            itr ++;
            lst -= (*itr).fs;
        }
        cout << lst << '\n';
    }

    return 0;
}

/*!
ahkh
*/

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

diameter.cpp: In function 'int main()':
diameter.cpp:140:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |     for(ll i = 0; i < adj[1].size(); i ++) {
      |                   ~~^~~~~~~~~~~~~~~

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