| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1070435 | Marco_Escandon | 봉쇄 시간 (IOI23_closing) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define x first
#define y second
int max_score(int n, int X, int Y, long long K,std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
vector<vector<pair<ll,ll>>> cad(n+2);
for(int i=0; i<n-1; i++)
{
cad[U[i]].push_back({V[i],W[i]});
cad[V[i]].push_back({U[i],W[i]});
}
priority_queue<pair<ll,ll>> q;q.push({0,X});q.push({0,Y});
vector<ll> v(n+2,-1);
ll cont=0;
while(!q.empty())
{
pair<ll,ll> a=q.top();q.pop();
if(K>=-a.x&&v[a.y]==-1)
{
v[a.y]=-a.x;
K+=a.x;
cont++;
for(auto i:cad[a.y])
{
q.push({a.x+-i.y,i.x});
}
}
}
return cont;
}
//#include "closing.h"
#include <cassert>
#include <cstdio>
#include <vector>
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;
}