QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#243672 | #4941. Tree Beauty | ideograph_advantage# | WA | 31ms | 30000kb | C++17 | 2.3kb | 2023-11-08 15:44:53 | 2023-11-08 15:44:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define iter(v) v.begin(), v.end()
#define SZ(v) (int)v.size()
#define pb emplace_back
#define ff first
#define ss second
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U>
void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
while(l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) void()
#define pary(...) void()
#endif
template<class A, class B>
ostream& operator<<(ostream& o, pair<A, B> p){
return o << '(' << p.ff << ',' << p.ss << ')';
}
#define maxn 100005
#define maxk 20
struct BIT{
ll bit[maxn];
void modify(int ind, ll val) {
ind++;
for (;ind < maxn;ind += ind & (-ind)) bit[ind] += val;
}
ll query(int ind) {
ind++;
ll ret = 0;
for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind];
return ret;
}
} bit, bc;
vector<int> adj[maxn];
int ord[maxn], lef[maxn], rig[maxn], par[maxn];
ll sum[maxn][maxk], siz[maxn];
ll chicnt[maxn][maxk];
int C = 0;
void dfs(int n) {
ord[n] = C;
lef[n] = C;
C++;
siz[n] = 1;
chicnt[n][0] = 1;
for (int v:adj[n]) {
dfs(v);
siz[n] += siz[v];
for (int i = 1;i < maxk;i++) chicnt[n][i] += chicnt[v][i-1];
}
rig[n] = C; //[lef, rig)
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
for (int i = 2;i <= n;i++) {
int pi;
cin >> pi;
par[i] = pi;
adj[pi].push_back(i);
}
dfs(1);
//pary(lef + 1, lef + n + 1);
//pary(rig + 1, rig + n + 1);
while (q--) {
int type; cin >> type;
if (type == 1) {
int x, y, k;
cin >> x >> y >> k;
if (k == 1) {
bit.modify(lef[x], y);
bit.modify(rig[x], -y);
bc.modify(lef[x], siz[x] * y);
} else {
ll mysum = 0;
for (int d = 0;d < maxk;d++) {
sum[x][d] = y;
mysum += chicnt[x][d] * y;
y /= k;
}
bc.modify(lef[x], mysum);
}
} else {
int x;
cin >> x;
ll ans = bc.query(rig[x] - 1) - bc.query(lef[x]);
ans += bit.query(lef[x]) * siz[x];
int p = x;
for (int d = 0;d < maxk;d++) {
for (int i = 0;d + i < maxk;i++) {
ans += sum[x][d+i] * chicnt[p][i];
}
x = par[x];
}
cout << ans << "\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11812kb
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: 0ms
memory: 11812kb
input:
1 1 2 1
output:
0
result:
ok single line: '0'
Test #3:
score: -100
Wrong Answer
time: 31ms
memory: 30000kb
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 2920352548 1987509504 2920352548 2782801948 2920352548 2920352548 7518672977 11295020015 7543062544 4383229800 19258702398 22947288874 15221147536 15428570536 14322314536 9119623396 12969783379 26872020588 25039643385 22398749036 27923029652 31534374661 745...
result:
wrong answer 50th lines differ - expected: '20722423038', found: '20722420930'