이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// In the name of God
// Hope is last to die
#include <bits/stdc++.h>
using namespace std;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
// #define int long long
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
const int maxn = 1e5 + 5;
const int inf = 1e9 + 7;
struct D{
ll ans, sum, mx, mn, ul, lv;
} node[maxn * 8];
ll n, q, W, w[maxn], in[maxn], out[maxn];
vector<pll> adj[maxn];
vector<ll> vec;
void dfs(int v, int p = -1){
for(auto [u, e]: adj[v]){
if(u == p) continue;
in[e] = vec.size();
vec.pb(w[e]);
dfs(u, v);
out[e] = vec.size();
vec.pb(-w[e]);
}
}
D merge(D l, D r){
D res;
res.ans = max(l.ans, max(r.ans, max(l.ul + r.mx + l.sum, l.mx + r.lv - l.sum)));
res.sum = l.sum + r.sum;
res.mx = max(l.mx, r.mx + l.sum);
res.mn = min(l.mn, r.mn + l.sum);
res.ul = max(l.ul, max(r.ul - l.sum, l.mx - 2 * (r.mn + l.sum)));
res.lv = max(l.lv, max(r.lv - l.sum, -l.mn * 2 + r.mx + l.sum));
return res;
}
void settle(int id, ll x){
node[id].ans = abs(x);
node[id].sum = x;
node[id].mx = max(0ll, x);
node[id].mn = min(0ll, x);
node[id].ul = max(0ll, -2 * x);
node[id].lv = max(0ll, x);
}
void build(int l = 0, int r = vec.size(), int id = 1){
if(l == r - 1){
settle(id, vec[l]);
return;
}
int mid = (l + r) / 2;
build(l, mid, id * 2);
build(mid, r, id * 2 + 1);
node[id] = merge(node[id * 2], node[id * 2 + 1]);
}
void upd(int p, ll x, int l = 0, int r = vec.size(), int id = 1){
if(l == r - 1){
settle(id, x);
return;
}
int mid = (l + r) / 2;
if(p < mid) upd(p, x, l, mid, id * 2);
else upd(p, x, mid, r, id * 2 + 1);
node[id] = merge(node[id * 2], node[id * 2 + 1]);
}
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> q >> W;
for(int i = 0; i < n - 1; i++){
int u, v; cin >> u >> v >> w[i];
adj[u].pb(mp(v, i));
adj[v].pb(mp(u, i));
}
dfs(1);
build();
ll last = 0;
while(q--){
ll d, e; cin >> d >> e;
d = (d + last) % (n - 1);
e = (e + last) % W;
upd(in[d], e);
upd(out[d], -e);
last = node[1].ans;
cout << last << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |