QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#728528 | #4941. Tree Beauty | trongvan245 | WA | 57ms | 39396kb | C++14 | 3.4kb | 2024-11-09 15:21:46 | 2024-11-09 15:21:46 |
Judging History
answer
// Hello I'm Nekan
//
#include <bits/stdc++.h>
#define Nekan "test"
#define fi first
#define se second
#define pb push_back
#define zs(v) ((int)(v).size())
#define BIT(x, i) (((x) >> (i)) & 1)
#define pii pair<int, int>
typedef long double ld;
typedef long long ll;
const int N = 1e5 + 5;
const long long mod = 1e9 + 7; // 998244353;
using namespace std;
struct Segment_tree {
vector<ll> st, lazy;
int n;
Segment_tree(int x) {
n = x;
st.assign(4 * x + 5, 0);
lazy.assign(4 * x + 5, 0);
}
void down(int id, int l, int r) {
int mid = (l + r) / 2;
ll t = lazy[id];
lazy[id] = 0;
lazy[id * 2] += t, lazy[id * 2 + 1] += t;
st[id * 2] += t * (mid - l + 1);
st[id * 2 + 1] += t * (r - mid);
}
void upd(int l, int r, int val) { upd(1, 1, n, l, r, val); }
void upd(int id, int l, int r, int u, int v, int val) {
if (l > v || r < u)
return;
if (l >= u && r <= v) {
st[id] += 1ll * (r - l + 1) * val;
lazy[id] += val;
return;
}
down(id, l, r);
int mid = (l + r) / 2;
upd(id * 2, l, mid, u, v, val);
upd(id * 2 + 1, mid + 1, r, u, v, val);
st[id] = st[id * 2] + st[id * 2 + 1];
}
ll get(int l, int r) { return get(1, 1, n, l, r); }
ll get(int id, int l, int r, int u, int v) {
if (l > v || r < u)
return 0;
if (l >= u && r <= v)
return st[id];
down(id, l, r);
int mid = (l + r) / 2;
return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
}
};
int n, q, cnt;
int in[N], out[N], p[N];
ll dp[N][25], d[N][25];
vector<int> adj[N];
void dfs(int u) {
in[u] = ++cnt;
for (int v : adj[u]) {
dfs(v);
for (int i = 1; i <= 20; ++i)
dp[u][i] += dp[v][i - 1];
}
out[u] = cnt;
++dp[u][0];
}
void xuly() {
cin >> n >> q;
Segment_tree st(n);
for (int i = 2; i <= n; ++i) {
cin >> p[i];
adj[p[i]].pb(i);
}
dfs(1);
// return;
// cout << dp[3][2] << '\n';
while (q--) {
int t;
cin >> t;
if (t == 1) {
int x, y, k;
cin >> x >> y >> k;
if (k == 1)
st.upd(in[x], out[x], y);
else {
for (int j = 0; j <= 20; ++j) {
d[x][j] += y;
y /= k;
}
}
} else {
int x;
cin >> x;
ll ans = st.get(in[x], out[x]);
// cout << ans << " check\n";
int pre = x;
for (int pos = 0; pos <= 20; ++pos) {
if (!pre)
break;
for (int i = pos; i <= 20; ++i) {
ans += 1ll * d[pre][i] * dp[x][i - pos];
}
pre = p[pre];
}
cout << ans << '\n';
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
if (fopen(Nekan ".inp", "r")) {
freopen(Nekan ".inp", "r", stdin);
freopen(Nekan ".out", "w", stdout);
}
int t = 1;
// cin >> t;
while (t--)
xuly();
}
// Surely nothing could go wrong.
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9472kb
input:
5 5 1 1 3 3 1 1 99 2 2 1 2 3 1 3 2 3 2 3
output:
245 97 99
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 2ms
memory: 11140kb
input:
1 1 2 1
output:
0
result:
ok single line: '0'
Test #3:
score: -100
Wrong Answer
time: 57ms
memory: 39396kb
input:
100000 100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
1818724600 1818724600 1818724600 672469600 2897885600 1987509504 2897885600 2760335000 2897885600 2897885600 7403713200 11137131600 7514202655 4383229800 19100548501 22773583200 15090370500 15297793500 14191537500 9074946248 12902639283 26557008900 24837132600 22267972000 27726020850 31286228647 745...
result:
wrong answer 5th lines differ - expected: '2920352548', found: '2897885600'