| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 749901 |
2023-05-28T22:42:11 Z |
doowey |
Arboras (RMI20_arboras) |
C++14 |
|
5000 ms |
17412 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = (int)1e5 + 1;
const int MOD = (int)1e9 + 7;
vector<int> E[N];
int par[N];
ll w[N];
int n;
int sub[N];
int link[N];
int rig[N];
int tin[N];
int tout[N];
int nd[N];
int tt = -1;
ll dp0[N];
int big0[N];
ll dp1[N];
void dfs(int u){
sub[u] = 1;
dp0[u] = dp1[u] = 0ll;
big0[u] = -1;
for(auto x : E[u]){
dfs(x);
if(dp0[x] + w[x] > dp0[u]){
big0[u] = x;
dp1[u] = dp0[u];
dp0[u] = dp0[x] + w[x];
}
else if(dp0[x] + w[x] > dp1[u]){
dp1[u] = dp0[x] + w[x];
}
sub[u] += sub[x];
}
}
void dfs1(int u){
tt ++ ;
tin[u] = tt;
nd[tin[u]] = u;
if(link[u] == -1) link[u] = u;
rig[link[u]] = tin[u];
int nx = -1;
for(auto x : E[u]){
if(nx == -1 || sub[x] > sub[nx]){
nx = x;
}
}
if(nx != -1){
link[nx]=link[u];
}
if(nx != -1){
dfs1(nx);
}
for(auto x : E[u]){
if(x != nx)
dfs1(x);
}
tout[u] = tt;
}
struct Node{
ll dp;
int id;
};
Node T[N * 4 + 24];
ll sum = 0;
void inc(ll y){
y %= MOD;
sum += y;
if(sum < 0) sum += MOD;
else if(sum >= MOD) sum -= MOD;
}
void build(int node, int cl, int cr){
if(cl == cr){
if(big0[nd[cl]] == -1 || link[big0[nd[cl]]] != link[nd[cl]])
T[node].id = cl;
else
T[node].id = -1;
T[node].dp = dp0[nd[cl]];
inc(dp0[nd[cl]] + dp1[nd[cl]]);
return;
}
int mid = (cl + cr) / 2;
build(node * 2, cl, mid);
build(node * 2 + 1, mid + 1, cr);
T[node].dp = 0ll;
T[node].id = max(T[node * 2].id, T[node * 2 + 1].id);
}
int query_id(int node, int cl, int cr, int tl, int tr){
if(cr < tl || cl > tr) return -1;
if(cl >= tl && cr <= tr){
return T[node].id;
}
int mid = (cl + cr) / 2;
return max(query_id(node * 2, cl, mid, tl, tr), query_id(node * 2 + 1, mid + 1, cr, tl, tr));
}
void push(int node, int cl, int cr){
if(cl != cr){
T[node * 2].dp += T[node].dp;
T[node * 2 + 1].dp += T[node].dp;
T[node].dp = 0;
}
}
void add_dp(int node, int cl, int cr, int tl, int tr, ll W){
push(node, cl, cr);
if(cr < tl || cl > tr) return;
if(cl >= tl && cr <= tr){
inc((cr - cl + 1) * 1ll * W);
T[node].dp += W;
push(node, cl, cr);
return;
}
int mid = (cl + cr) / 2;
add_dp(node * 2, cl, mid, tl, tr, W);
add_dp(node * 2 + 1, mid + 1, cr, tl, tr, W);
}
ll ask_dp(int node, int cl, int cr, int idx){
push(node, cl, cr);
if(cl == cr){
return T[node].dp;
}
int mid = (cl + cr) / 2;
if(mid >= idx)
return ask_dp(node * 2, cl, mid, idx);
else
return ask_dp(node * 2 + 1, mid + 1, cr, idx);
}
ll get_dp(int node){
return ask_dp(1, 0, n - 1, tin[node]);
}
ll add;
void check_up(int &v){
ll f = get_dp(v) + w[v];
ll par_dp = get_dp(par[v]);
if(big0[par[v]] == v){
add_dp(1, 0, n - 1, tin[par[v]], tin[par[v]], add);
v = par[v];
}
else{
if(f > par_dp){
add = f - par_dp;
add_dp(1, 0, n - 1, tin[par[v]], tin[par[v]], add);
inc(par_dp-dp1[par[v]]);
dp1[par[v]] = par_dp;
big0[par[v]] = v;
v=par[v];
}
else if(f > dp1[par[v]]){
inc(f-dp1[par[v]]);
dp1[par[v]] = f;
v=0;
}
else{
v = 0;
}
}
}
ll n0[N];
ll n1[N];
void dfs2(int u){
n0[u] = n1[u] = 0ll;
for(auto x : E[u]){
dfs2(x);
if(n0[x] + w[x] > n0[u]){
n1[u] = n0[x];
n0[u] = n0[x] + w[x];
}
else if(n0[x] + w[x] > n1[u]){
n1[u] = n0[x] + w[x];
}
}
}
int main(){
fastIO;
//freopen("in.txt", "r", stdin);
cin >> n;
for(int i = 1; i < n; i ++ ){
cin >> par[i];
E[par[i]].push_back(i);
}
for(int i = 1; i < n; i ++ ){
cin >> w[i];
}
for(int i = 0 ; i < n; i ++ ){
link[i] = -1;
}
dfs(0);
dfs1(0);
build(1, 0, n - 1);
/*
for(int i = 0; i < n; i ++ ){
cout << "(" << get_dp(i) << "," << dp1[i] << ") ";
}
cout << "\n";
*/
cout << sum << "\n";
//return 0;
int q;
cin >> q;
int v;
int g;
int i0, i1;
for(int iq = 1; iq <= q; iq ++ ){
cin >> v >> add;
// implement ze walk up
w[v] += add;
//check_up(v);
while(v > 0){
if(v == link[v]){
check_up(v);
}
else{
g = query_id(1, 0, n - 1, tin[link[v]], tin[v] - 1);
if(g == -1){
add_dp(1, 0, n - 1, tin[link[v]], tin[v] - 1, add);
v = link[v];
}
else{
add_dp(1, 0, n - 1, g + 1, tin[v] - 1, add);
v=nd[g + 1];
check_up(v);
}
}
}
dfs2(0);
/*
for(int i = 0; i < n; i ++ ){
cout << "(" << get_dp(i) << "," << dp1[i] << ") ";
}
cout << "\n";
for(int i = 0 ; i < n; i ++ ){
cout << "[" << n0[i] << "," << n1[i] << "] ";
}
cout << "\n";
*/
cout << sum << "\n";
}
return 0;
}
Compilation message
arboras.cpp: In function 'int main()':
arboras.cpp:233:9: warning: unused variable 'i0' [-Wunused-variable]
233 | int i0, i1;
| ^~
arboras.cpp:233:13: warning: unused variable 'i1' [-Wunused-variable]
233 | int i0, i1;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
2772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5044 ms |
15432 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5031 ms |
17412 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
2772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
