oj.uz

Submission #947016

# Submission time Handle Problem Language Result Execution time Memory
947016 2024-03-15T10:27:00 Z amirhoseinfar1385 Worst Reporter 4 (JOI21_worst_reporter4) C++17
100 / 100
 558 ms 137808 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
long long mainres,n,p[maxn],c[maxn],todor[maxn],vas[maxn];
set<long long>adj[maxn];
set<pair<long long,long long>>dp[maxn];
map<long long,long long>mp;
map<long long,long long>h[maxn];

void vorod(){
	cin>>n;
	for(long long i=1;i<=n;i++){
		int d;
		cin>>p[i]>>d>>c[i];
		h[i][d]+=c[i];
		mainres+=c[i];
		if(i!=p[i]){
			adj[p[i]].insert(i);
		}
	}
}

void merge(long long u,long long v){
	long long fu=u;
	if((long long)dp[u].size()<(long long)dp[v].size()){
		swap(u,v);
	}
	for(auto x:dp[v]){
		auto y=*dp[u].lower_bound(make_pair(x.first,-1));
		if(y.first==x.first){
			dp[u].erase(y);
			y.second+=x.second;
			dp[u].insert(y);
		}else{
			dp[u].insert(x);
		}
	}
	if(fu!=u){
		swap(dp[u],dp[fu]);
	}
}

void ins(long long u,long long w,long long ww){
	long long moonde=ww;
	while(moonde>0&&(long long)dp[u].size()>0&&(*dp[u].begin()).first<w){
		auto xx=dp[u].lower_bound(make_pair(w,-1));
		xx--;
		auto x=*xx;
		if(x.second>=moonde){
			dp[u].erase(x);
			x.second-=moonde;
			dp[u].insert(x);
			break;
		}else{
			dp[u].erase(x);
			moonde-=x.second;
		}
	}
	if((long long)dp[u].size()==0||(*dp[u].begin()).first>w){
		dp[u].insert(make_pair(w,ww));
		return ;
	}
	auto xx=dp[u].lower_bound(make_pair(w,-1));
	auto x=*xx;
	if(x.first==w){
		dp[u].erase(x);
		x.second+=ww;
		dp[u].insert(x);
	}else{
		dp[u].insert(make_pair(w,ww));
	}
}

void solved(long long u){
	//cout<<"wtf: "<<u<<endl;
	for(auto x:adj[u]){
		solved(x);
		merge(u,x);
	}
	for(auto x:h[u]){
		ins(u,x.first,x.second);
	}
}
deque<int>wtf;

void cald(int u){
	if(vas[u]){
		while((int)wtf.size()>0&&wtf.back()!=u){
			wtf.pop_back();
		}
		return ;
	}
	vas[u]=1;
	wtf.push_front(u);
	cald(p[u]);
}

void pre(){
	for(int i=1;i<=n;i++){
		if(p[i]==i||vas[i]){
			continue;
		}
		cald(i);
		if((int)wtf.size()<=1){
			wtf.clear();
			continue;
		}
		set<int>st;
		for(auto x:wtf){
			st.insert(x);
		}
		int u=wtf.front();
		wtf.pop_front();
		p[u]=u;
		for(auto x:wtf){
			for(auto y:h[x]){
				h[u][y.first]+=y.second;
			}
			for(auto y:adj[x]){
				if(st.count(y)==0){
					adj[u].insert(y);
				}
			}
			adj[u].erase(x);
		}
		wtf.clear();
	}
}

void solve(){
	for(int i=1;i<=n;i++){
		if(p[i]!=i){
			continue;
		}
		solved(i);
		for(auto x:dp[i]){
			mainres-=x.second;
		}
	}
}

void khor(){
	cout<<mainres<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
	//freopen("inp.txt","r",stdin);
	vorod();
	pre();
//	//cout<<"ha"<<endl;
	solve();
	khor();
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31324 KB Output is correct
2 Correct 6 ms 31320 KB Output is correct
3 Correct 6 ms 31324 KB Output is correct
4 Correct 6 ms 31404 KB Output is correct
5 Correct 12 ms 32860 KB Output is correct
6 Correct 11 ms 32604 KB Output is correct
7 Correct 11 ms 32344 KB Output is correct
8 Correct 12 ms 32860 KB Output is correct
9 Correct 14 ms 32604 KB Output is correct
10 Correct 12 ms 32308 KB Output is correct
11 Correct 9 ms 32088 KB Output is correct
12 Correct 13 ms 32092 KB Output is correct
13 Correct 9 ms 32092 KB Output is correct
14 Correct 10 ms 32180 KB Output is correct
15 Correct 10 ms 32092 KB Output is correct
16 Correct 12 ms 33372 KB Output is correct
17 Correct 11 ms 32604 KB Output is correct
18 Correct 10 ms 32092 KB Output is correct
19 Correct 10 ms 32332 KB Output is correct
20 Correct 12 ms 32348 KB Output is correct
21 Correct 9 ms 32252 KB Output is correct
22 Correct 11 ms 32476 KB Output is correct
23 Correct 10 ms 32204 KB Output is correct
24 Correct 11 ms 32600 KB Output is correct
25 Correct 10 ms 32264 KB Output is correct
26 Correct 10 ms 32604 KB Output is correct
27 Correct 10 ms 32344 KB Output is correct
28 Correct 10 ms 32688 KB Output is correct
29 Correct 10 ms 32344 KB Output is correct
30 Correct 11 ms 32604 KB Output is correct
31 Correct 11 ms 32604 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31324 KB Output is correct
2 Correct 6 ms 31320 KB Output is correct
3 Correct 6 ms 31324 KB Output is correct
4 Correct 6 ms 31404 KB Output is correct
5 Correct 12 ms 32860 KB Output is correct
6 Correct 11 ms 32604 KB Output is correct
7 Correct 11 ms 32344 KB Output is correct
8 Correct 12 ms 32860 KB Output is correct
9 Correct 14 ms 32604 KB Output is correct
10 Correct 12 ms 32308 KB Output is correct
11 Correct 9 ms 32088 KB Output is correct
12 Correct 13 ms 32092 KB Output is correct
13 Correct 9 ms 32092 KB Output is correct
14 Correct 10 ms 32180 KB Output is correct
15 Correct 10 ms 32092 KB Output is correct
16 Correct 12 ms 33372 KB Output is correct
17 Correct 11 ms 32604 KB Output is correct
18 Correct 10 ms 32092 KB Output is correct
19 Correct 10 ms 32332 KB Output is correct
20 Correct 12 ms 32348 KB Output is correct
21 Correct 9 ms 32252 KB Output is correct
22 Correct 11 ms 32476 KB Output is correct
23 Correct 10 ms 32204 KB Output is correct
24 Correct 11 ms 32600 KB Output is correct
25 Correct 10 ms 32264 KB Output is correct
26 Correct 10 ms 32604 KB Output is correct
27 Correct 10 ms 32344 KB Output is correct
28 Correct 10 ms 32688 KB Output is correct
29 Correct 10 ms 32344 KB Output is correct
30 Correct 11 ms 32604 KB Output is correct
31 Correct 11 ms 32604 KB Output is correct
32 Correct 12 ms 32860 KB Output is correct
33 Correct 375 ms 112844 KB Output is correct
34 Correct 316 ms 87748 KB Output is correct
35 Correct 386 ms 109696 KB Output is correct
36 Correct 313 ms 88240 KB Output is correct
37 Correct 220 ms 69016 KB Output is correct
38 Correct 200 ms 64588 KB Output is correct
39 Correct 198 ms 68404 KB Output is correct
40 Correct 183 ms 67924 KB Output is correct
41 Correct 112 ms 67924 KB Output is correct
42 Correct 185 ms 63308 KB Output is correct
43 Correct 177 ms 63056 KB Output is correct
44 Correct 353 ms 137808 KB Output is correct
45 Correct 268 ms 102124 KB Output is correct
46 Correct 96 ms 64592 KB Output is correct
47 Correct 258 ms 76112 KB Output is correct
48 Correct 175 ms 69204 KB Output is correct
49 Correct 107 ms 69260 KB Output is correct
50 Correct 272 ms 82988 KB Output is correct
51 Correct 171 ms 70672 KB Output is correct
52 Correct 277 ms 76696 KB Output is correct
53 Correct 183 ms 69688 KB Output is correct
54 Correct 249 ms 80464 KB Output is correct
55 Correct 227 ms 78132 KB Output is correct
56 Correct 192 ms 78188 KB Output is correct
57 Correct 182 ms 78680 KB Output is correct
58 Correct 213 ms 81796 KB Output is correct
59 Correct 218 ms 81676 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31324 KB Output is correct
2 Correct 6 ms 31320 KB Output is correct
3 Correct 6 ms 31324 KB Output is correct
4 Correct 6 ms 31404 KB Output is correct
5 Correct 12 ms 32860 KB Output is correct
6 Correct 11 ms 32604 KB Output is correct
7 Correct 11 ms 32344 KB Output is correct
8 Correct 12 ms 32860 KB Output is correct
9 Correct 14 ms 32604 KB Output is correct
10 Correct 12 ms 32308 KB Output is correct
11 Correct 9 ms 32088 KB Output is correct
12 Correct 13 ms 32092 KB Output is correct
13 Correct 9 ms 32092 KB Output is correct
14 Correct 10 ms 32180 KB Output is correct
15 Correct 10 ms 32092 KB Output is correct
16 Correct 12 ms 33372 KB Output is correct
17 Correct 11 ms 32604 KB Output is correct
18 Correct 10 ms 32092 KB Output is correct
19 Correct 10 ms 32332 KB Output is correct
20 Correct 12 ms 32348 KB Output is correct
21 Correct 9 ms 32252 KB Output is correct
22 Correct 11 ms 32476 KB Output is correct
23 Correct 10 ms 32204 KB Output is correct
24 Correct 11 ms 32600 KB Output is correct
25 Correct 10 ms 32264 KB Output is correct
26 Correct 10 ms 32604 KB Output is correct
27 Correct 10 ms 32344 KB Output is correct
28 Correct 10 ms 32688 KB Output is correct
29 Correct 10 ms 32344 KB Output is correct
30 Correct 11 ms 32604 KB Output is correct
31 Correct 11 ms 32604 KB Output is correct
32 Correct 12 ms 32860 KB Output is correct
33 Correct 375 ms 112844 KB Output is correct
34 Correct 316 ms 87748 KB Output is correct
35 Correct 386 ms 109696 KB Output is correct
36 Correct 313 ms 88240 KB Output is correct
37 Correct 220 ms 69016 KB Output is correct
38 Correct 200 ms 64588 KB Output is correct
39 Correct 198 ms 68404 KB Output is correct
40 Correct 183 ms 67924 KB Output is correct
41 Correct 112 ms 67924 KB Output is correct
42 Correct 185 ms 63308 KB Output is correct
43 Correct 177 ms 63056 KB Output is correct
44 Correct 353 ms 137808 KB Output is correct
45 Correct 268 ms 102124 KB Output is correct
46 Correct 96 ms 64592 KB Output is correct
47 Correct 258 ms 76112 KB Output is correct
48 Correct 175 ms 69204 KB Output is correct
49 Correct 107 ms 69260 KB Output is correct
50 Correct 272 ms 82988 KB Output is correct
51 Correct 171 ms 70672 KB Output is correct
52 Correct 277 ms 76696 KB Output is correct
53 Correct 183 ms 69688 KB Output is correct
54 Correct 249 ms 80464 KB Output is correct
55 Correct 227 ms 78132 KB Output is correct
56 Correct 192 ms 78188 KB Output is correct
57 Correct 182 ms 78680 KB Output is correct
58 Correct 213 ms 81796 KB Output is correct
59 Correct 218 ms 81676 KB Output is correct
60 Correct 6 ms 31320 KB Output is correct
61 Correct 6 ms 31320 KB Output is correct
62 Correct 6 ms 31320 KB Output is correct
63 Correct 7 ms 31424 KB Output is correct
64 Correct 365 ms 96992 KB Output is correct
65 Correct 304 ms 80004 KB Output is correct
66 Correct 390 ms 97864 KB Output is correct
67 Correct 320 ms 79916 KB Output is correct
68 Correct 239 ms 66380 KB Output is correct
69 Correct 212 ms 63060 KB Output is correct
70 Correct 414 ms 76540 KB Output is correct
71 Correct 277 ms 63456 KB Output is correct
72 Correct 475 ms 81096 KB Output is correct
73 Correct 291 ms 68600 KB Output is correct
74 Correct 558 ms 83280 KB Output is correct
75 Correct 359 ms 69460 KB Output is correct
76 Correct 340 ms 69284 KB Output is correct
77 Correct 440 ms 83284 KB Output is correct
78 Correct 267 ms 69268 KB Output is correct
79 Correct 424 ms 92772 KB Output is correct
80 Correct 314 ms 74576 KB Output is correct
81 Correct 239 ms 63828 KB Output is correct
82 Correct 526 ms 83680 KB Output is correct
83 Correct 78 ms 60496 KB Output is correct
84 Correct 399 ms 76120 KB Output is correct
85 Correct 394 ms 76172 KB Output is correct
86 Correct 357 ms 72944 KB Output is correct
87 Correct 380 ms 76172 KB Output is correct
88 Correct 393 ms 76032 KB Output is correct