| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 998670 | ASGA_RedSea | 봉쇄 시간 (IOI23_closing) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/**
* بسم الله الرحمن الرحيم *
﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿
*/
/// author : "ASGA"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e18;
int max_score(int n,int x,int y,ll k,int U[],int V[],int W[]){
vector <vector <array <ll,2>>> a(n);
for(int i = 0;i + 1 < n;i++){
a[U[i]].push_back({V[i],W[i]});
a[V[i]].push_back({U[i],W[i]});
}
vector <array <ll,2>> sd;
vector <ll> d(n,inf);
vector <int> v(n,0);
priority_queue <array <ll,2>> q;
q.push({0,x});
v[x] = 1;d[x] = 0;
while(!q.empty()){
int i = q.top()[1];q.pop();
for(auto& [j,w] : a[i]){
d[j] = min(d[j],d[i] + w);
if(v[j] == 0){
q.push({-d[j],j});
v[j] = 1;
}
}
}
for(int i = 0;i < n;i++)sd.push_back({d[i],i});
d = vector <ll> (n,inf);
v = vector <int> (n,0);
q.push({0,y});
v[y] = 1;d[y] = 0;
while(!q.empty()){
int i = q.top()[1];q.pop();
for(auto& [j,w] : a[i]){
d[j] = min(d[j],d[i] + w);
if(v[j] == 0){
q.push({-d[j],j});
v[j] = 1;
}
}
}
for(int i = 0;i < n;i++)sd.push_back({d[i],i});
sort(sd.begin(),sd.end());
int ans = 0;
vector <ll> ct(n,0);
for(auto& [i,j] : sd){
k += ct[j];
k -= i;
ct[j] = i;
if(k >= 0)ans++;
}
return ans;
}
//signed main(){
// ios_base::sync_with_stdio(0);cin.tie(0);
//
// int t;cin >> t;
// while(t--){
// int n,x,y;ll k;
// cin >> n >> x >> y >> k;
//
// int u[n + 5],v[n + 5],w[n + 5];
// for(int i = 0;i + 1 < n;i++)cin >> u[i] >> v[i] >> w[i];
//
// cout << max_score(n,x,y,k,u,v,w) << endl;
// }
//
// return 0;
//}