Submission #1210731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210731		salmon	Worst Reporter 4 (JOI21_worst_reporter4)	C++20	100 / 100	540 ms	446260 KiB

worst_reporter2

#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> children[200100];
int parent[200100];
int sise[200100];
int lst[200100];
int cost[200100];
int bound = 1.1e9;
vector<int> roots;
vector<int> cycles;
vector<int> de;
bool visited[200100];
bool cyclic[200100];

struct node{
	
	int s,e,m;
	node *l,*r;
	long long int lazy;
	long long int v;
	
	node(int S, int E){
		s = S;
		e = E;
		m = (s + e)/2;
		
		lazy = 0;
		v = 0;
		
		l = NULL;
		r = NULL;
	}
	
	void merge(node* n){
		v += n -> v;
		lazy += n -> lazy;
		
		if(l == NULL) l = n -> l;
		else if(n -> l != NULL) l -> merge(n -> l);
		
		if(r == NULL) r = n -> r;
		else if(n -> r != NULL) r -> merge(n -> r);
	}
	
	long long int query(int i){
		if(i <= m){
			if(l == NULL) return lazy;
			else return lazy + l -> query(i);
		}
		else{
			if(r == NULL) return lazy;
			else return lazy + r -> query(i);
		}
	}
	
	int queryin(long long int i){
		if(s == e){
			return s;
		}
		
		if(l != NULL && l -> v >= i - lazy){
			return l -> queryin(i - lazy);
		}
		else{
			if(r == NULL) return s;
			return r -> queryin(i - lazy);
		}
	}	
	
	void update(int k){
		lazy += k;
		v += k;
	}
	
	void flapdate(int S, int E, long long int k){
		if(S <= s && e <= E){
			l = NULL;
			r = NULL;
			v = k;
			lazy = k;
			return;
		}
		
		if(l == NULL){
			l = new node(s,m);
			r = new node(m + 1, e);
		}
			
		if(S <= m){
			if(l == NULL) l = new node(s,m);
			l -> flapdate(S,E,k - lazy);
		}
		if(m < E){
			if(r == NULL) r = new node(m + 1, e);
			r -> flapdate(S,E,k - lazy);
		}
		
		if(r == NULL) v = lazy;
		else v = r -> v + lazy;
	}
	
};

node* solve(int i){
	node* n = new node(0,bound);
	
	for(int j : children[i]){
		if(j == i) continue;
		if(cyclic[j]) continue;
		n -> merge(solve(j));
	}
	//printf("l %d\n",cyclic[i]);
	if(cyclic[i]) return n;
	
	int it = lower_bound(de.begin(),de.end(),lst[i]) - de.begin();
	
	int pos = n -> queryin(n -> query(it) - cost[i]);
	
	n -> flapdate(pos,it,n -> query(it) - cost[i]);
	n -> update(cost[i]);
	//printf("%d\n",i);
	return n;
}

bool dfs(int i, int p){
	visited[i] = true;
	
	bool cycle = false;
	
	for(int j : children[i]){
		if(i == j || j == p) continue;
		if(visited[j]){
			if(!cycle){
				cycles.push_back(j);
				cycle = true;
			}
		}
		else cycle |= dfs(j,i);
	}
	
	if(parent[i] != i && parent[i] != p){
		if(visited[parent[i]]){
			if(!cycle){
				cycle = true;
				cycles.push_back(parent[i]);
			}
		}
		else cycle |= dfs(parent[i],i);
	}
	
	return cycle;
}

int main(){
	
	scanf(" %d",&N);
	
	de.push_back(0);
	
	for(int i = 1; i <= N; i++){
		scanf(" %d",&parent[i]);
		scanf(" %d",&lst[i]); 
		scanf(" %d",&cost[i]);
	//printf("%d %d\n",parent[i],i);
		children[parent[i]].push_back(i);
		de.push_back(lst[i]);
		
		visited[i] = false;
		cyclic[i] = false;
		
		if(parent[i] == i) roots.push_back(i);
	}
	//printf("mybals");
	for(int i = 1; i <= N; i++){
		if(!visited[i]){
			if(dfs(i,-1)){
				//cycles.push_back(i);
			}
		}
	}
	//printf("Ohyes");
	sort(de.begin(),de.end());
	de.resize(unique(de.begin(),de.end()) - de.begin());
	bound = de.size();
	
	long long int ans = 0;

	for(int i : roots){
		ans += solve(i) -> query(0);
	}

	for(int i : cycles){
		//printf("%d\n",i);
		node *n = new node(0,bound);
		
		vector<int> temp = {i};
		
		cyclic[i] = true;
		
		int c = i;
		while(parent[c] != i){
			c = parent[c];
			temp.push_back(c);
			cyclic[c] = true;
		}

		long long int total = 0;
		
		map<int,long long int> mep;
		
		for(int i : temp){
			mep[lst[i]] += cost[i];
			total += cost[i];
			n -> merge(solve(i));
		}

		long long int smallans = n -> query(0) + total;
		
		for(pair<int,long long int> ii : mep){
			int it = lower_bound(de.begin(),de.end(),ii.first) - de.begin();
			smallans = min(smallans, n -> query(it) + total - ii.second);
		} 
		ans += smallans;
	}
	
	
	printf("%lld\n",ans);
	
}
/*
6
5 1 2
1 0 7
2 1 2 
3 1 2
4 1 2
1 0 5
 */

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:158:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
worst_reporter2.cpp:163:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |                 scanf(" %d",&parent[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~
worst_reporter2.cpp:164:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |                 scanf(" %d",&lst[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~
worst_reporter2.cpp:165:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |                 scanf(" %d",&cost[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~

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