Submission #1241077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241077		vako_p	Closing Time (IOI23_closing)	C++20	8 / 100	216 ms	63160 KiB

closing

#include "closing.h"
#include <bits/stdc++.h> 
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second
#define debug(x) cerr << #x << "----> " << x << endl;
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3")

const int mxN = 1e6 + 5;
ll n,dis[mxN];
vector<pair<ll,ll>> v[mxN];

void dfs(ll at, ll par){
	for(auto it : v[at]){
		if(it.ff == par) continue;
		dis[it.ff] = dis[at] + it.sd;
		dfs(it.ff, at);
	}
}

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W){
    n = N;
    for(int i = 0; i < n - 1; i++){
    	v[U[i]].pb({V[i], W[i]});
    	v[V[i]].pb({U[i], W[i]});
	}
	dis[X] = 0;
	dfs(X, X);
	multiset<ll> s;
	for(int i = 0; i < n; i++) s.insert(dis[i]);
	dis[Y] = 0;
	dfs(Y, Y);
	for(int i = 0; i < n; i++) s.insert(dis[i]);
	ll ans = 0;
	while(!s.empty()){
		auto it = s.begin();
		if(*it > K) break;
		K -= *it;
		s.erase(it);
		ans++;
	}
	for(int i = 0; i < n; i++) v[i].clear();
	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 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