Submission #518926

#	Time	Username	Problem	Language	Result	Execution time	Memory
518926		Koosha_mv	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	100 / 100	648 ms	180672 KiB

worst_reporter2

#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];
ll ans;
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 && 1){
		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){
	map<int,int> val;
	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();
	}
	
	vector<pair<int,int> > noname;
	for(auto u : v){
		val[a[u]]+=cost[u];
		dfs(u);
		for(auto p : s[u]){
			noname.pb(p);
		}
	}
	val[inf+inf]=0;
	sort(all(noname));
	/*for(auto e : noname){
		erorp(e);
	}
	cout<<endl;*/
	int p=0,sum=0,res=0;
	for(auto e : val){
		//erorp(e);
		while(p<noname.size() && noname[p].F<=e.F){
			sum+=noname[p].S;
			p++;
		}
		maxm(res,sum+e.S);
	}
	ans+=res;
	
	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 (stderr)

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++)
......
   50 |  f(i,0,g[u].size()){
      |    ~~~~~~~~~~~~~~~             
worst_reporter2.cpp:50:2: note: in expansion of macro 'f'
   50 |  f(i,0,g[u].size()){
      |  ^
worst_reporter2.cpp: In function 'void solve(long long int)':
worst_reporter2.cpp:145:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |   while(p<noname.size() && noname[p].F<=e.F){
      |         ~^~~~~~~~~~~~~~
worst_reporter2.cpp: At global scope:
worst_reporter2.cpp:158:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  158 | main(){
      | ^~~~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:162:7: warning: unused variable 'p' [-Wunused-variable]
  162 |   int p;
      |       ^

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