Submission #386294

#	Time	Username	Problem	Language	Result	Execution time	Memory
386294		model_code	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	438 ms	55772 KiB

worst_reporter2

// O(NlogN)

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
typedef vector<int> vi;

class Segment_Tree{
	private:
	int n;
	vi a,b;
	void Max(int &x,int y){
		if(x<=y||!b[x]) x=y;
	}
	public:
	Segment_Tree(int n_){
		n=1;
		while(n<n_) n*=2;
		a=vi(2*n-1,-1);
		b=vi(n_,1);
	}
	void ChangeMax(int l,int r,int id){
		l+=n-1;r+=n-1;
		while(l<r){
			if(l%2==0){
				Max(a[l],id);
				l++;
			}
			if(r%2==0){
				r--;
				Max(a[r],id);
			}
			l/=2;r/=2;
		}
	}
	void Erase(int x){b[x]=0;}
	int Access(int k){
		k+=n-1;
		int m=a[k];
		while(k>0){
			k=(k-1)/2;
			Max(m,a[k]);
		}
		return m;
	}
};

void dfs(int v,vector<vi> &g,vi &lt,vi &rt,int &id){
	lt[v]=id++;
	for(auto u:g[v]) dfs(u,g,lt,rt,id);
	rt[v]=id;
}

ll Solve(int N,vi A,vi H,vi C){
	vi lt(N),rt(N);
	int id=0;
	vector<vi> g(N);
	vector<pair<int,int>> a(N);
	vector<ll> b(N);
	Segment_Tree st(N);
	ll res=0;
	for(int i=0;i<N;i++){
		a[i]={H[i],i};
		if(i) g[A[i]].push_back(i);
		res+=C[i];
	}
	sort(a.rbegin(),a.rend());
	dfs(0,g,lt,rt,id);
	for(auto p:a){
		int i=p.second;
		ll t=C[i];
		b[i]=C[i];
		st.ChangeMax(lt[i],rt[i],i);
		while(t){
			int pr=(i?st.Access(lt[A[i]]):-1);
			if(pr<0){
				res-=t;
				break;
			}
			i=pr;
			ll mn=min(t,b[i]);
			t-=mn,b[i]-=mn;
			if(b[i]) continue;
			st.Erase(i);
			pr=(i?st.Access(lt[A[i]]):-1);
			if(pr>=0) st.ChangeMax(lt[pr],rt[pr],pr);
		}
	}
	return res;
}

int N;
vi A,H,C;

int main(){
	scanf("%d",&N);
	A=H=C=vi(N);
	vi deg(N),ind(N,-1);
	vector<vi> g(N);
	queue<int> q;
	ll res=0;
	for(int i=0;i<N;i++){
		scanf("%d%d%d",&A[i],&H[i],&C[i]);
		A[i]--;
		deg[A[i]]++;
		g[A[i]].push_back(i);
	}
	for(int i=0;i<N;i++) if(!deg[i]) q.push(i);
	while(!q.empty()){
		int v=q.front(),u=A[v];
		q.pop();
		deg[u]--;
		if(!deg[u]) q.push(u);
	}
	for(int i=0;i<N;i++) if(ind[i]<0&&deg[i]){
		int v=i,I=1;
		vector<pair<int,int>> b;
		do{
			b.push_back({H[v],C[v]});
			ind[v]=0;
			for(auto u:g[v]) if(!deg[u]){
				ind[u]=I++;
				q.push(u);
			}
			v=A[v];
		}while(v!=i);
		sort(b.rbegin(),b.rend());
		int N_=(int)b.size();
		vi A_(N_),H_,C_;
		for(int i=1;i<N_;i++) A_[i]=i-1;
		for(auto p:b){
			H_.push_back(p.first);
			C_.push_back(p.second);
		}
		while(!q.empty()){
			int u=q.front();
			q.pop();
			A_.push_back(ind[A[u]]+N_-1);
			H_.push_back(H[u]);
			C_.push_back(C[u]);
			for(auto w:g[u]){
				ind[w]=I++;
				q.push(w);
			}
		}
		N_=A_.size();
		res+=Solve(N_,A_,H_,C_);
	}
	printf("%lld\n",res);
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   99 |  scanf("%d",&N);
      |  ~~~~~^~~~~~~~~
worst_reporter2.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  106 |   scanf("%d%d%d",&A[i],&H[i],&C[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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