oj.uz

Submission #518921

# Submission time Handle Problem Language Result Execution time Memory
518921 2022-01-25T07:27:47 Z Koosha_mv Worst Reporter 4 (JOI21_worst_reporter4) C++14
79 / 100
 656 ms 172752 KB 
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#define int ll

const int N=2e5+99,inf=1e9,lg=20;

int n,t,cnt,a[N],sz[N],ft[N],cost[N],par[N],mark[N],vis[N],rap[lg][N];
set<pair<int,int> > s[N];
vector<pair<int,int> > vec;
vector<int> v,vtx,g[N];

void Dfs(int u){
	vtx.pb(u);
	vis[u]=1;
	for(auto v : g[u]){
		if(!vis[v]){
			Dfs(v);
		}
	}
	ft[u]=cnt++;
	if(mark[u]){
		ft[u]=inf;
	}
	vec.pb(mp(a[u],ft[u]));
}
void dfs(int u){
	int b=mark[u];
	mark[u]=1;
	sz[u]=1;
	f(i,0,g[u].size()){
		if(mark[g[u][i]]){
			g[u].erase(g[u].begin()+i);
			break;
		}
	}
	int x=0;
	for(auto v : g[u]){
		dfs(v);
		sz[u]+=sz[v];
		if(sz[x]<sz[v]){
			x=v;
		}
	}
	if(x>0){
		swap(s[u],s[x]);
		for(auto v : g[u]){
			if(v==x) continue ;
			for(auto p : s[v]){
				if(s[u].lower_bound(mp(p.F,0))!=s[u].end() && (*s[u].lower_bound(mp(p.F,0))).F==p.F){
					pair<int,int> e=*s[u].lower_bound(p);
					s[u].erase(e);
					e.S+=p.S;
					s[u].insert(e);
					
				}
				else{
					s[u].insert(p);
				}
			}
		}
	}
	if(b && 0){
		return ;
	}
	pair<int,int> p=mp(a[u],0);
	if(s[u].lower_bound(p)!=s[u].end() && (*s[u].lower_bound(p)).F==a[u]){
		p=*s[u].lower_bound(p);
		s[u].erase(p);
	}
	if(s[u].lower_bound(p)!=s[u].end()){
		pair<int,int> e=*s[u].lower_bound(p);
		s[u].erase(e);
		e.S-=cost[u];
		s[u].insert(e);
	}
	while(s[u].lower_bound(p)!=s[u].end() && (*s[u].lower_bound(p)).S<=0){
		pair<int,int> t,e=*s[u].lower_bound(p);
		s[u].erase(e);
		if(s[u].lower_bound(e)==s[u].end()) break;
		t=*s[u].lower_bound(e);
		s[u].erase(t);
		t.S+=e.S;
		s[u].insert(t);
	}
	p.S+=cost[u];
	s[u].insert(p);
}
void solve(int rt){
	mark[rt]=1;
	v.pb(rt);
	for(int u=par[rt];u!=rt;u=par[u]){
		mark[u]=1;
		v.pb(u);
	}
	Dfs(rt);
	sort(all(vec));
	for(auto u : vtx){
		a[u]=lower_bound(all(vec),mp(a[u],ft[u]))-vec.begin();
	}
	for(auto u : v){
		dfs(u);
	}
	v.clear();
	vtx.clear();
	vec.clear();
}

main(){
	ll sum=0;
	cin>>n;
	f(i,1,n+1){
		int p;
		cin>>par[i]>>a[i]>>cost[i];
		sum+=cost[i];
		a[i]=inf-a[i];
		rap[0][i]=par[i];
		g[par[i]].pb(i);
	}	
	f(l,1,lg){
		f(i,1,n+1){
			rap[l][i]=rap[l-1][rap[l-1][i]];
		}
	}
	f(i,1,n+1){
		if(!mark[rap[lg-1][i]]){
			solve(rap[lg-1][i]);
		}
	}
	ll ans=0;
	for(auto p : s[1]){
		ans+=p.S;
	}
	cout<<sum-ans;
}
/*
6
1 1 10
1 1 10
1 1 10
3 1 10
2 1 10
2 1 10
*/

Compilation message

worst_reporter2.cpp: In function 'void dfs(long long int)':
worst_reporter2.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   49 |  f(i,0,g[u].size()){
      |    ~~~~~~~~~~~~~~~             
worst_reporter2.cpp:49:2: note: in expansion of macro 'f'
   49 |  f(i,0,g[u].size()){
      |  ^
worst_reporter2.cpp: At global scope:
worst_reporter2.cpp:127:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  127 | main(){
      | ^~~~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:131:7: warning: unused variable 'p' [-Wunused-variable]
  131 |   int p;
      |       ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14540 KB Output is correct
2 Correct 7 ms 14540 KB Output is correct
3 Correct 7 ms 14668 KB Output is correct
4 Correct 8 ms 14540 KB Output is correct
5 Correct 23 ms 16688 KB Output is correct
6 Correct 25 ms 16752 KB Output is correct
7 Correct 19 ms 16716 KB Output is correct
8 Correct 18 ms 16792 KB Output is correct
9 Correct 18 ms 16840 KB Output is correct
10 Correct 18 ms 16824 KB Output is correct
11 Correct 18 ms 17020 KB Output is correct
12 Correct 19 ms 16876 KB Output is correct
13 Correct 19 ms 16844 KB Output is correct
14 Correct 18 ms 16504 KB Output is correct
15 Correct 18 ms 16460 KB Output is correct
16 Correct 20 ms 17164 KB Output is correct
17 Correct 20 ms 17168 KB Output is correct
18 Correct 17 ms 17612 KB Output is correct
19 Correct 22 ms 16480 KB Output is correct
20 Correct 17 ms 16528 KB Output is correct
21 Correct 21 ms 16588 KB Output is correct
22 Correct 15 ms 16332 KB Output is correct
23 Correct 15 ms 16332 KB Output is correct
24 Correct 18 ms 16488 KB Output is correct
25 Correct 22 ms 16568 KB Output is correct
26 Correct 15 ms 16780 KB Output is correct
27 Correct 16 ms 16588 KB Output is correct
28 Correct 16 ms 16716 KB Output is correct
29 Correct 20 ms 16844 KB Output is correct
30 Correct 17 ms 16788 KB Output is correct
31 Correct 18 ms 16716 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14540 KB Output is correct
2 Correct 7 ms 14540 KB Output is correct
3 Correct 7 ms 14668 KB Output is correct
4 Correct 8 ms 14540 KB Output is correct
5 Correct 23 ms 16688 KB Output is correct
6 Correct 25 ms 16752 KB Output is correct
7 Correct 19 ms 16716 KB Output is correct
8 Correct 18 ms 16792 KB Output is correct
9 Correct 18 ms 16840 KB Output is correct
10 Correct 18 ms 16824 KB Output is correct
11 Correct 18 ms 17020 KB Output is correct
12 Correct 19 ms 16876 KB Output is correct
13 Correct 19 ms 16844 KB Output is correct
14 Correct 18 ms 16504 KB Output is correct
15 Correct 18 ms 16460 KB Output is correct
16 Correct 20 ms 17164 KB Output is correct
17 Correct 20 ms 17168 KB Output is correct
18 Correct 17 ms 17612 KB Output is correct
19 Correct 22 ms 16480 KB Output is correct
20 Correct 17 ms 16528 KB Output is correct
21 Correct 21 ms 16588 KB Output is correct
22 Correct 15 ms 16332 KB Output is correct
23 Correct 15 ms 16332 KB Output is correct
24 Correct 18 ms 16488 KB Output is correct
25 Correct 22 ms 16568 KB Output is correct
26 Correct 15 ms 16780 KB Output is correct
27 Correct 16 ms 16588 KB Output is correct
28 Correct 16 ms 16716 KB Output is correct
29 Correct 20 ms 16844 KB Output is correct
30 Correct 17 ms 16788 KB Output is correct
31 Correct 18 ms 16716 KB Output is correct
32 Correct 19 ms 16832 KB Output is correct
33 Correct 617 ms 118928 KB Output is correct
34 Correct 616 ms 117932 KB Output is correct
35 Correct 609 ms 115764 KB Output is correct
36 Correct 625 ms 118732 KB Output is correct
37 Correct 592 ms 120076 KB Output is correct
38 Correct 613 ms 129868 KB Output is correct
39 Correct 554 ms 102184 KB Output is correct
40 Correct 563 ms 102192 KB Output is correct
41 Correct 505 ms 104504 KB Output is correct
42 Correct 506 ms 84980 KB Output is correct
43 Correct 514 ms 85008 KB Output is correct
44 Correct 613 ms 146356 KB Output is correct
45 Correct 635 ms 146332 KB Output is correct
46 Correct 595 ms 172752 KB Output is correct
47 Correct 656 ms 95000 KB Output is correct
48 Correct 574 ms 94212 KB Output is correct
49 Correct 464 ms 95472 KB Output is correct
50 Correct 417 ms 88496 KB Output is correct
51 Correct 429 ms 88432 KB Output is correct
52 Correct 592 ms 95928 KB Output is correct
53 Correct 538 ms 95112 KB Output is correct
54 Correct 316 ms 102156 KB Output is correct
55 Correct 458 ms 98016 KB Output is correct
56 Correct 427 ms 105144 KB Output is correct
57 Correct 391 ms 108528 KB Output is correct
58 Correct 551 ms 103640 KB Output is correct
59 Correct 533 ms 103844 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14540 KB Output is correct
2 Correct 7 ms 14540 KB Output is correct
3 Correct 7 ms 14668 KB Output is correct
4 Correct 8 ms 14540 KB Output is correct
5 Correct 23 ms 16688 KB Output is correct
6 Correct 25 ms 16752 KB Output is correct
7 Correct 19 ms 16716 KB Output is correct
8 Correct 18 ms 16792 KB Output is correct
9 Correct 18 ms 16840 KB Output is correct
10 Correct 18 ms 16824 KB Output is correct
11 Correct 18 ms 17020 KB Output is correct
12 Correct 19 ms 16876 KB Output is correct
13 Correct 19 ms 16844 KB Output is correct
14 Correct 18 ms 16504 KB Output is correct
15 Correct 18 ms 16460 KB Output is correct
16 Correct 20 ms 17164 KB Output is correct
17 Correct 20 ms 17168 KB Output is correct
18 Correct 17 ms 17612 KB Output is correct
19 Correct 22 ms 16480 KB Output is correct
20 Correct 17 ms 16528 KB Output is correct
21 Correct 21 ms 16588 KB Output is correct
22 Correct 15 ms 16332 KB Output is correct
23 Correct 15 ms 16332 KB Output is correct
24 Correct 18 ms 16488 KB Output is correct
25 Correct 22 ms 16568 KB Output is correct
26 Correct 15 ms 16780 KB Output is correct
27 Correct 16 ms 16588 KB Output is correct
28 Correct 16 ms 16716 KB Output is correct
29 Correct 20 ms 16844 KB Output is correct
30 Correct 17 ms 16788 KB Output is correct
31 Correct 18 ms 16716 KB Output is correct
32 Correct 19 ms 16832 KB Output is correct
33 Correct 617 ms 118928 KB Output is correct
34 Correct 616 ms 117932 KB Output is correct
35 Correct 609 ms 115764 KB Output is correct
36 Correct 625 ms 118732 KB Output is correct
37 Correct 592 ms 120076 KB Output is correct
38 Correct 613 ms 129868 KB Output is correct
39 Correct 554 ms 102184 KB Output is correct
40 Correct 563 ms 102192 KB Output is correct
41 Correct 505 ms 104504 KB Output is correct
42 Correct 506 ms 84980 KB Output is correct
43 Correct 514 ms 85008 KB Output is correct
44 Correct 613 ms 146356 KB Output is correct
45 Correct 635 ms 146332 KB Output is correct
46 Correct 595 ms 172752 KB Output is correct
47 Correct 656 ms 95000 KB Output is correct
48 Correct 574 ms 94212 KB Output is correct
49 Correct 464 ms 95472 KB Output is correct
50 Correct 417 ms 88496 KB Output is correct
51 Correct 429 ms 88432 KB Output is correct
52 Correct 592 ms 95928 KB Output is correct
53 Correct 538 ms 95112 KB Output is correct
54 Correct 316 ms 102156 KB Output is correct
55 Correct 458 ms 98016 KB Output is correct
56 Correct 427 ms 105144 KB Output is correct
57 Correct 391 ms 108528 KB Output is correct
58 Correct 551 ms 103640 KB Output is correct
59 Correct 533 ms 103844 KB Output is correct
60 Correct 8 ms 14540 KB Output is correct
61 Incorrect 8 ms 14540 KB Output isn't correct
62 Halted 0 ms 0 KB -