Submission #1235006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235006		lalig777	Closing Time (IOI23_closing)	C++20	0 / 100	1068 ms	2071360 KiB

closing

#include "closing.h"
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
//#define int long long
using namespace std;
typedef long long ll;

vector<vector<pair<int, ll> > >adj;
vector<ll>closx;
vector<ll>closy;

void dfs(int round, int u, int p){
	for (auto vec: adj[u]){
		int v=vec.first;
		ll w=vec.second;
		if (v==p) continue;
		if (round==1) closx[v]=closx[u]+w;
		else closy[v]=closy[u]+w;
		dfs(round, v, u);
	}return;
}

int max_score(int N, int X, int Y, ll K, vector<int>U, vector<int>V, vector<int>W){
	adj.resize(N);
	closx.assign(N, 0);
	closy.assign(N, 0);

	for (int i=0; i<N-1; i++){
		adj[U[i]].push_back(make_pair(V[i], W[i]));
		adj[V[i]].push_back(make_pair(U[i], W[i]));
	}
	dfs(1, X, X);
	dfs(2, Y, Y);
	vector<ll>all(2*N);
	for (int i=0; i<N; i++) all[i]=closx[i];
	for (int i=0; i<N; i++) all[N+i]=closy[i];
	sort(all.begin(), all.end());
	//for (int i=0; i<2*N; i++) cout<<all[i]<<' ';
	//cout<<endl;
	int ans=0;
	for (int i=0; i<2*N; i++){
		if (all[i]<=K){
			ans++;
			K-=all[i];
		}else break;
	}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