QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#243672#4941. Tree Beautyideograph_advantage#WA 31ms30000kbC++172.3kb2023-11-08 15:44:532023-11-08 15:44:53

Judging History

你现在查看的是最新测评结果

  • [2023-11-08 15:44:53]
  • 评测
  • 测评结果:WA
  • 用时:31ms
  • 内存:30000kb
  • [2023-11-08 15:44:53]
  • 提交

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'