oj.uz

Submission #1077170

# Submission time Handle Problem Language Result Execution time Memory
1077170 2024-08-27T02:24:32 Z emptypringlescan Closing Time (IOI23_closing) C++17
0 / 100
 145 ms 38480 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4956 KB 2nd lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 145 ms 38480 KB 1st lines differ - on the 1st token, expected: '451', found: '68601'
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 5208 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Incorrect 2 ms 4956 KB 1st lines differ - on the 1st token, expected: '3', found: '16'
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 5208 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Incorrect 2 ms 4956 KB 1st lines differ - on the 1st token, expected: '3', found: '16'
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 5208 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Incorrect 2 ms 4956 KB 1st lines differ - on the 1st token, expected: '3', found: '16'
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4956 KB 2nd lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4956 KB 2nd lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4956 KB 2nd lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4956 KB 2nd lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4956 KB 2nd lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -