Submission #518914

#	Time	Username	Problem	Language	Result	Execution time	Memory
518914		Koosha_mv	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	79 / 100	594 ms	173116 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=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 (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++)
......
   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 / 14
• Subtask 2: 65 / 65
• Subtask 3: 0 / 21