Submission #1232368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232368		AMnu	Tree (IOI24_tree)	C++20	100 / 100	83 ms	22932 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int MAXN = 2e5+5;

int N, par[MAXN], siz[MAXN], cost[MAXN];
ll A[MAXN], B[MAXN];
vector <int> adj[MAXN];
vector <pii> S;

void pref(int k,ll w) {
	A[k-1] += k*w;
	B[k-1] -= w;
}

int find(int x) {
	if (par[x] == x) {
		return x;
	}
	return par[x] = find(par[x]);
}

void join(int x,int y,int z) {
	x = find(x);
	y = find(y);
	if (x == y) {
		return;
	}
	pref(siz[x],cost[x]-z);
	pref(siz[y],cost[y]-z);
	siz[x] += siz[y];
	cost[x] = z;
	par[y] = x;
}

void init(vector<int> P,vector<int> W) {
	N = P.size();
	for (int i=1;i<N;i++) {
		adj[P[i]].push_back(i);
	}
	for (int i=0;i<N;i++) {
		par[i] = i;
		siz[i] = 1;
		if (adj[i].empty()) {
			A[N] += W[i];
		}
		else if (W[i] != 0) {
			S.push_back({W[i],i});
		}
	}
	sort(S.begin(),S.end());
	reverse(S.begin(),S.end());
	for (auto p : S) {
		int w = p.fi;
		int u = p.se;
		for (int v : adj[u]) {
			join(u, v, w);
		}
		siz[find(u)]--;
	}
	for (int i=0;i<N;i++) {
		if (find(i) == i) {
			pref(siz[i], cost[i]);
		}
	}
	for (int i=N;i>=1;i--) {
		A[i] += A[i+1];
		B[i] += B[i+1];
	}
}

long long query(int L, int R) {
	int k = min(N,R/L);
	return L*A[k]+R*B[k];
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 18 / 18
• Subtask 4: 7 / 7
• Subtask 5: 11 / 11
• Subtask 6: 22 / 22
• Subtask 7: 19 / 19