Submission #1077170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077170		emptypringlescan	Closing Time (IOI23_closing)	C++17	0 / 100	145 ms	38480 KiB

closing

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,long long> > adj[200005];
pair<long long,long long> cost[200005];
void dfs1(int x, int p, long long d){
	cost[x].first=d;
	for(auto i:adj[x]){
		if(i.first==p) continue;
		dfs1(i.first,x,d+i.second);
	}
}
void dfs2(int x, int p, long long d){
	cost[x].second=d;
	for(auto i:adj[x]){
		if(i.first==p) continue;
		dfs2(i.first,x,d+i.second);
	}
}
bool cmp(pair<long long,long long> a,pair<long long,long long> b){
	return a.first+a.second<b.first+b.second;
}
int max_score(int n, int n1, int n2, long long k, vector<int> u, vector<int> v, vector<int> w){
	for(int i=0; i<n-1; i++){
		adj[u[i]].push_back({v[i],w[i]});
		adj[v[i]].push_back({u[i],w[i]});
	}
	dfs1(n1,-1,0);
	dfs2(n2,-1,0);
	long long pathd=cost[n2].first;
	for(int i=0; i<n; i++){
		if(cost[i].first>cost[i].second) swap(cost[i].first,cost[i].second);
		cost[i].second-=cost[i].first;
	}
	sort(cost,cost+n,cmp);
	multiset<long long> s1,s2;
	long long alr=0;
	int ans=0;
	for(int i=0; i<n; i++) s2.insert(cost[i].first);
	while(!s2.empty()&&alr+*s2.begin()<=k){
		long long x=*s2.begin();
		s1.insert(x);
		alr+=x;
		s2.erase(s2.begin());
	}
	ans=max(ans,(int)s1.size());
	//cout << ans << '\n';
	s1.clear(); s2.clear(); alr=0;
	int bas=0;
	for(int i=0; i<n; i++){
		if(cost[i].first+cost[i].first+cost[i].second==pathd){
			bas++;
			alr+=cost[i].first;
			s2.insert(cost[i].second);
			cost[i].first=-1;
		}
		else s2.insert(cost[i].first);
	}
	while(!s2.empty()&&alr+*s2.begin()<=k){
		long long x=*s2.begin();
		s1.insert(x);
		alr+=x;
		s2.erase(s2.begin());
	}
	ans=max(ans,(int)s1.size()+bas);
	for(int i=0; i<n; i++){
		if(cost[i].first==-1) continue;
		//cout << cost[i].first << ' ' << cost[i].second << '\n';
		if(s1.find(cost[i].first)!=s1.end()){
			s1.erase(s1.find(cost[i].first));
		}
		else{
			s2.erase(s2.find(cost[i].first));
			alr+=cost[i].first;
		}
		bas++;
		s2.insert(cost[i].second);
		long long x=*s2.begin();
		s1.insert(x);
		alr+=x;
		s2.erase(s2.begin());
		while(!s1.empty()&&alr>k){
			x=*(--s1.end());
			s2.insert(x);
			s1.erase(--s1.end());
			alr-=x;
		}
		if(alr>k) break;
		ans=max(ans,(int)s1.size()+bas);
		//cout << ans << '\n';
	}
	for(int i=0; i<=n; i++){
		adj[i].clear();
		cost[i]={0,0};
	}
	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17