답안 #884738

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
884738	2023-12-08T10:01:15 Z	Arshi	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	233 ms	51944 KB

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
*/

Compilation message

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.0

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

Subtask #2
0 / 13.0

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

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	13912 KB	Output is correct
2	Correct	4 ms	14172 KB	Output is correct
3	Correct	4 ms	14180 KB	Output is correct
4	Correct	13 ms	14172 KB	Output is correct
5	Correct	54 ms	14420 KB	Output is correct
6	Correct	3 ms	13916 KB	Output is correct
7	Correct	3 ms	14172 KB	Output is correct
8	Correct	4 ms	14172 KB	Output is correct
9	Correct	4 ms	14172 KB	Output is correct
10	Correct	14 ms	14172 KB	Output is correct
11	Correct	61 ms	14644 KB	Output is correct
12	Correct	6 ms	16988 KB	Output is correct
13	Correct	6 ms	16988 KB	Output is correct
14	Correct	11 ms	17496 KB	Output is correct
15	Correct	21 ms	16988 KB	Output is correct
16	Correct	84 ms	17280 KB	Output is correct
17	Correct	78 ms	51708 KB	Output is correct
18	Correct	85 ms	51496 KB	Output is correct
19	Correct	82 ms	51436 KB	Output is correct
20	Correct	108 ms	51420 KB	Output is correct
21	Correct	233 ms	51944 KB	Output is correct