oj.uz

Submission #518914

# Submission time Handle Problem Language Result Execution time Memory
518914 2022-01-25T07:06:54 Z Koosha_mv Worst Reporter 4 (JOI21_worst_reporter4) C++14
79 / 100
 594 ms 173116 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=100,lg=20;

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

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]){
				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);
	/*cout<<u<<" : "<<endl;
	for(auto p : s[u]){
		cout<<p.F<<" "<<p.S<<endl;
	}
	cout<<endl;*/
}
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);
	}
	for(auto u : v){
		dfs(u);
	}
}

main(){
	ll sum=0;
	vector<pair<int,int> > vec;
	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);
		vec.pb(mp(a[i],-i));
	}	
	sort(all(vec));
	f(i,1,n+1){
		a[i]=lower_bound(all(vec),mp(a[i],-i))-vec.begin();
	}
	/*cout<<endl;
	f(i,1,n+1){
		cout<<i<<" : "<<a[i]<<" "<<cost[i]<<endl;
	}*/
	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++)
......
   34 |  f(i,0,g[u].size()){
      |    ~~~~~~~~~~~~~~~             
worst_reporter2.cpp:34:2: note: in expansion of macro 'f'
   34 |  f(i,0,g[u].size()){
      |  ^
worst_reporter2.cpp: At global scope:
worst_reporter2.cpp:100:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  100 | main(){
      | ^~~~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:105:7: warning: unused variable 'p' [-Wunused-variable]
  105 |   int p;
      |       ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14540 KB Output is correct
2 Correct 8 ms 14540 KB Output is correct
3 Correct 7 ms 14524 KB Output is correct
4 Correct 7 ms 14532 KB Output is correct
5 Correct 19 ms 16692 KB Output is correct
6 Correct 20 ms 16776 KB Output is correct
7 Correct 17 ms 16708 KB Output is correct
8 Correct 18 ms 16804 KB Output is correct
9 Correct 19 ms 16716 KB Output is correct
10 Correct 18 ms 16836 KB Output is correct
11 Correct 17 ms 16968 KB Output is correct
12 Correct 20 ms 16716 KB Output is correct
13 Correct 19 ms 16636 KB Output is correct
14 Correct 18 ms 16332 KB Output is correct
15 Correct 19 ms 16224 KB Output is correct
16 Correct 18 ms 17228 KB Output is correct
17 Correct 19 ms 17244 KB Output is correct
18 Correct 20 ms 17696 KB Output is correct
19 Correct 18 ms 16460 KB Output is correct
20 Correct 18 ms 16460 KB Output is correct
21 Correct 17 ms 16452 KB Output is correct
22 Correct 16 ms 16340 KB Output is correct
23 Correct 15 ms 16296 KB Output is correct
24 Correct 19 ms 16568 KB Output is correct
25 Correct 18 ms 16488 KB Output is correct
26 Correct 15 ms 16716 KB Output is correct
27 Correct 16 ms 16528 KB Output is correct
28 Correct 18 ms 16624 KB Output is correct
29 Correct 17 ms 16716 KB Output is correct
30 Correct 18 ms 16716 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 8 ms 14540 KB Output is correct
2 Correct 8 ms 14540 KB Output is correct
3 Correct 7 ms 14524 KB Output is correct
4 Correct 7 ms 14532 KB Output is correct
5 Correct 19 ms 16692 KB Output is correct
6 Correct 20 ms 16776 KB Output is correct
7 Correct 17 ms 16708 KB Output is correct
8 Correct 18 ms 16804 KB Output is correct
9 Correct 19 ms 16716 KB Output is correct
10 Correct 18 ms 16836 KB Output is correct
11 Correct 17 ms 16968 KB Output is correct
12 Correct 20 ms 16716 KB Output is correct
13 Correct 19 ms 16636 KB Output is correct
14 Correct 18 ms 16332 KB Output is correct
15 Correct 19 ms 16224 KB Output is correct
16 Correct 18 ms 17228 KB Output is correct
17 Correct 19 ms 17244 KB Output is correct
18 Correct 20 ms 17696 KB Output is correct
19 Correct 18 ms 16460 KB Output is correct
20 Correct 18 ms 16460 KB Output is correct
21 Correct 17 ms 16452 KB Output is correct
22 Correct 16 ms 16340 KB Output is correct
23 Correct 15 ms 16296 KB Output is correct
24 Correct 19 ms 16568 KB Output is correct
25 Correct 18 ms 16488 KB Output is correct
26 Correct 15 ms 16716 KB Output is correct
27 Correct 16 ms 16528 KB Output is correct
28 Correct 18 ms 16624 KB Output is correct
29 Correct 17 ms 16716 KB Output is correct
30 Correct 18 ms 16716 KB Output is correct
31 Correct 18 ms 16716 KB Output is correct
32 Correct 17 ms 16724 KB Output is correct
33 Correct 524 ms 119124 KB Output is correct
34 Correct 536 ms 118260 KB Output is correct
35 Correct 537 ms 116028 KB Output is correct
36 Correct 527 ms 118936 KB Output is correct
37 Correct 520 ms 120236 KB Output is correct
38 Correct 528 ms 130120 KB Output is correct
39 Correct 560 ms 99440 KB Output is correct
40 Correct 533 ms 99520 KB Output is correct
41 Correct 451 ms 101840 KB Output is correct
42 Correct 506 ms 83812 KB Output is correct
43 Correct 517 ms 83784 KB Output is correct
44 Correct 527 ms 146520 KB Output is correct
45 Correct 530 ms 146592 KB Output is correct
46 Correct 559 ms 173116 KB Output is correct
47 Correct 567 ms 93688 KB Output is correct
48 Correct 594 ms 92980 KB Output is correct
49 Correct 406 ms 94248 KB Output is correct
50 Correct 407 ms 87536 KB Output is correct
51 Correct 371 ms 87560 KB Output is correct
52 Correct 546 ms 94832 KB Output is correct
53 Correct 562 ms 94000 KB Output is correct
54 Correct 288 ms 99568 KB Output is correct
55 Correct 427 ms 96056 KB Output is correct
56 Correct 391 ms 102080 KB Output is correct
57 Correct 389 ms 105392 KB Output is correct
58 Correct 531 ms 101752 KB Output is correct
59 Correct 528 ms 101880 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14540 KB Output is correct
2 Correct 8 ms 14540 KB Output is correct
3 Correct 7 ms 14524 KB Output is correct
4 Correct 7 ms 14532 KB Output is correct
5 Correct 19 ms 16692 KB Output is correct
6 Correct 20 ms 16776 KB Output is correct
7 Correct 17 ms 16708 KB Output is correct
8 Correct 18 ms 16804 KB Output is correct
9 Correct 19 ms 16716 KB Output is correct
10 Correct 18 ms 16836 KB Output is correct
11 Correct 17 ms 16968 KB Output is correct
12 Correct 20 ms 16716 KB Output is correct
13 Correct 19 ms 16636 KB Output is correct
14 Correct 18 ms 16332 KB Output is correct
15 Correct 19 ms 16224 KB Output is correct
16 Correct 18 ms 17228 KB Output is correct
17 Correct 19 ms 17244 KB Output is correct
18 Correct 20 ms 17696 KB Output is correct
19 Correct 18 ms 16460 KB Output is correct
20 Correct 18 ms 16460 KB Output is correct
21 Correct 17 ms 16452 KB Output is correct
22 Correct 16 ms 16340 KB Output is correct
23 Correct 15 ms 16296 KB Output is correct
24 Correct 19 ms 16568 KB Output is correct
25 Correct 18 ms 16488 KB Output is correct
26 Correct 15 ms 16716 KB Output is correct
27 Correct 16 ms 16528 KB Output is correct
28 Correct 18 ms 16624 KB Output is correct
29 Correct 17 ms 16716 KB Output is correct
30 Correct 18 ms 16716 KB Output is correct
31 Correct 18 ms 16716 KB Output is correct
32 Correct 17 ms 16724 KB Output is correct
33 Correct 524 ms 119124 KB Output is correct
34 Correct 536 ms 118260 KB Output is correct
35 Correct 537 ms 116028 KB Output is correct
36 Correct 527 ms 118936 KB Output is correct
37 Correct 520 ms 120236 KB Output is correct
38 Correct 528 ms 130120 KB Output is correct
39 Correct 560 ms 99440 KB Output is correct
40 Correct 533 ms 99520 KB Output is correct
41 Correct 451 ms 101840 KB Output is correct
42 Correct 506 ms 83812 KB Output is correct
43 Correct 517 ms 83784 KB Output is correct
44 Correct 527 ms 146520 KB Output is correct
45 Correct 530 ms 146592 KB Output is correct
46 Correct 559 ms 173116 KB Output is correct
47 Correct 567 ms 93688 KB Output is correct
48 Correct 594 ms 92980 KB Output is correct
49 Correct 406 ms 94248 KB Output is correct
50 Correct 407 ms 87536 KB Output is correct
51 Correct 371 ms 87560 KB Output is correct
52 Correct 546 ms 94832 KB Output is correct
53 Correct 562 ms 94000 KB Output is correct
54 Correct 288 ms 99568 KB Output is correct
55 Correct 427 ms 96056 KB Output is correct
56 Correct 391 ms 102080 KB Output is correct
57 Correct 389 ms 105392 KB Output is correct
58 Correct 531 ms 101752 KB Output is correct
59 Correct 528 ms 101880 KB Output is correct
60 Correct 9 ms 14540 KB Output is correct
61 Incorrect 8 ms 14540 KB Output isn't correct
62 Halted 0 ms 0 KB -