Submission #391518

#	Time	Username	Problem	Language	Result	Execution time	Memory
391518		patrikpavic2	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	1139 ms	172096 KiB

worst_reporter2

#include <cstdio>
#include <algorithm>
#include <vector>

#define PB push_back

using namespace std;

const int N = 4e5 + 500;
const int OFF = (1 << 18);

typedef long long ll;

struct node{
	node *L, *R;
	ll sum;
	node(){
		sum = 0, L = NULL, R = NULL;
	}
};

typedef node* pnode;

ll get_sum(pnode x) { return x ? x -> sum : 0LL;} 
int bio[N];

void update(pnode &x, int a, int b, int gdj, ll dod){
	if(!x) x = new node();
	x -> sum += dod;
	if(a != b && gdj <= (a + b) / 2)
		update(x -> L, a, (a + b) / 2, gdj, dod);
	else if(a != b)
		update(x -> R, (a + b) / 2 + 1, b, gdj, dod);
}

ll query(pnode &x, int a, int b, int gdj){
	if(!x || a > gdj) return 0;
	if(gdj == b) return x -> sum;
	if(gdj <= (a + b) / 2)
		return query(x -> L, a, (a + b) / 2, gdj);
	else
		return get_sum(x -> L) + query(x -> R, (a + b) / 2 + 1, b, gdj);
}

void brisi(pnode &x, int a, int b, int lo, int hi){
	if(!x) return;
	if(a > hi || b < lo) return;
	brisi(x -> L, a, (a + b) / 2, lo, hi);
	brisi(x -> R, (a + b) / 2 + 1, b, lo, hi);
	if(lo <= a && b <= hi){
		delete x; x = NULL;
	}
	else{
		x -> sum = get_sum(x -> L) + get_sum(x -> R);
	}
}

ll OSTALO;

int bar(pnode &x, int a, int b, ll kol){
	if(!x || a == b) {
		OSTALO = kol;
		return b;
	}
	if(get_sum(x -> L) >= kol)
		return bar(x -> L, a, (a + b) / 2, kol);
	return bar(x -> R, (a + b) / 2 + 1, b, kol - get_sum(x -> L));
}

void prodi_sve(pnode &x, int a, int b, pnode novi){
	if(!x || (x -> sum == 0)) return;
	if(a == b){
		update(novi, 0, OFF - 1, a, x -> sum);
		return;
	}
	prodi_sve(x -> L, a, (a + b) / 2, novi);
	prodi_sve(x -> R, (a + b) / 2 + 1, b, novi);
	delete x; x = NULL;
}

pnode root[N];
int siz[N], C[N], A[N], P[N], boja[N];
vector < int > v[N], cik[N];

void print(pnode x, int a, int b, int mks){
	if(a > mks || !x) return;
	if(a == b)
		printf("(%d, %lld) ", a, x -> sum);
	else{
		print(x -> L, a, (a + b) / 2, mks);
		print(x -> R, (a + b) / 2 + 1, b, mks);
	}
}

int n;

void primjeni(pnode &x, int AA, int CC){
	ll ja = query(x, 0, OFF - 1, AA) + CC;
	int gr = bar(x, 0, OFF - 1, ja);
	if(gr != OFF - 1){
		update(x, 0, OFF - 1, gr, -OSTALO);
		brisi(x, 0, OFF - 1, AA + 1, gr - 1);
	}
	else{
		brisi(x, 0, OFF - 1, AA + 1, OFF - 1);
	}
	update(x, 0, OFF - 1, AA, CC);
}

bool cmp(int x, int y){
	return A[x] > A[y];
}

void dfs(int x){
	siz[x] = 0;
	for(int y : v[x]){
		dfs(y);
		if(siz[y] > siz[x]){
			swap(siz[x], siz[y]);
			swap(root[x], root[y]);
		}
		prodi_sve(root[y], 0, OFF - 1, root[x]);
		siz[x] += siz[y];
	}
	siz[x]++;
	if(x <= n){
		primjeni(root[x], A[x], C[x]);
	}
	else{
		sort(cik[x].begin(), cik[x].end(), cmp);
		for(int xx : cik[x]){
			primjeni(root[x], A[xx], C[xx]);
		}
	}
}

vector < int > saz;
vector < int > g[N];
ll sve = 0;
int novi = 0;

void biooo(int x){
	if(bio[x] == 2) return;
	bio[x] = 2;
	for(int y : g[x])
		biooo(y);
}

int main(){
	scanf("%d", &n); novi = n + 1;
	for(int i = 1;i <= n;i++){
		scanf("%d%d%d", P + i, A + i, C + i);
		saz.PB(-A[i]); 
		sve += C[i];
		g[P[i]].PB(i); 
		g[i].PB(P[i]);
	}
	sort(saz.begin(), saz.end());
	saz.erase(unique(saz.begin(), saz.end()), saz.end());
	for(int i = 1;i <= n;i++)
		A[i] = lower_bound(saz.begin(), saz.end(), -A[i]) - saz.begin() + 1;
	
	for(int i = 1;i <= n;i++){
		if(bio[i]) continue;
		int cur = i;
		while(!bio[cur]){
			bio[cur] = 1;
			cur = P[cur];
		}
		biooo(cur);
		int poc = cur, st = 1;
		while(cur != poc || st){
			boja[cur] = novi;
			cik[novi].PB(cur);
			cur = P[cur];
			st = 0;
		}
		novi++;
	}
	for(int i = 1;i <= n;i++){
		if(boja[i]) continue;
		if(boja[P[i]]) v[boja[P[i]]].PB(i);
		else 		   v[P[i]].PB(i);
	}
	for(int i = n + 1;i < novi;i++){
		dfs(i);
		sve -= query(root[i], 0, OFF - 1, OFF - 1);
	}	
	printf("%lld\n", sve);
	return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:150:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  150 |  scanf("%d", &n); novi = n + 1;
      |  ~~~~~^~~~~~~~~~
worst_reporter2.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  152 |   scanf("%d%d%d", P + i, A + i, C + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 65 / 65
• Subtask 3: 21 / 21