제출 #1234214

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1234214		santi3223	Closing Time (IOI23_closing)	C++20	0 / 100	79 ms	33464 KiB

closing

#include <bits/stdc++.h>
#include "closing.h"
using namespace std;
#define ll long long
#define vb vector<bool>
#define pb push_back
#define ff(aa, bb, cc) for(ll aa = bb; aa < cc; aa++)
#define vl vector<ll>
#define pll pair<ll, ll>
#define fi first
#define se second
#define ed "\n"
#define all(aaa) aaa.begin(), aaa.end()
#define rall(aaa) aaa.rbegin(), aaa.rend()
ll MOD = 1e9+7;

priority_queue<ll, vector<ll>, greater<ll>> pq;
vector<vector<pll>> conexiones;


void dfs(ll cur, ll p, ll sum){
	pq.push(sum);
	for(auto &x : conexiones[cur]){
		if(x.fi != p){
			dfs(x.fi, cur, sum+x.se);
		}
	}
}


int max_score(int n, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W){
	conexiones = vector<vector<pll>>(n);
	ff(i, 0, n-1){
		conexiones[U[i]].pb({V[i], W[i]});
		conexiones[V[i]].pb({U[i], W[i]});
	}
	dfs(X, -1, 0);
	dfs(Y, -1, 0);
	ll tot = 0, ktot = 0;
	while(ktot <= K && !pq.empty()){
		ll cur = pq.top();
		//cout << ktot << " " << cur << " " << K << ed;
		if(ktot+cur > K){
			break;
		}
		else{
			ktot += cur;
			tot++;
			pq.pop();
		}
	}
    return tot;
}
/*
int main(){

    int Q;
    assert(1 == scanf("%d", &Q));

    std::vector<int> N(Q), X(Q), Y(Q);
    std::vector<long long> K(Q);
    std::vector<std::vector<int>> U(Q), V(Q), W(Q);

    for (int q = 0; q < Q; q++)
    {
        assert(4 == scanf("%d %d %d %lld", &N[q], &X[q], &Y[q], &K[q]));

        U[q].resize(N[q] - 1);
        V[q].resize(N[q] - 1);
        W[q].resize(N[q] - 1);
        for (int i = 0; i < N[q] - 1; ++i)
        {
            assert(3 == scanf("%d %d %d", &U[q][i], &V[q][i], &W[q][i]));
        }
    }
    fclose(stdin);

    std::vector<int> result(Q);
    for (int q = 0; q < Q; q++)
    {
        result[q] = max_score(N[q], X[q], Y[q], K[q], U[q], V[q], W[q]);
    }

    for (int q = 0; q < Q; q++)
    {
        printf("%d\n", result[q]);
    }
    fclose(stdout);

    return 0;
}
*/

• 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