| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 878486 | 2023-11-24T14:15:24 Z | Sandro123 | 봉쇄 시간 (IOI23_closing) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
#pragma GCC diagnostic warning "-std=c++11"
#define pb push_back
#define int long long
#define f first
#define s second
using namespace std;
const int P=2*1e6+5;
vector <pair <int,int> > gr[P];
int fix[P],dist[2*P];
int d,nd;
void dfs(int x){
fix[x]=1;
for(int i=0; i<(int)gr[x].size(); i++){
int v=gr[x][i].f;
if(fix[v]==0){
nd++; d+=gr[x][i].s; dist[nd]=d; dfs(v); d-=gr[x][i].s;
}
}
}
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W){
for(int i=0; i<N; i++){
fix[i]=0; gr[i].clear();
}
for(int i=0; i<2*N; i++){
dist[i]=0;
}
for(int i=0; i<N; i++){
gr[U[i]].pb({V[i],W[i]});
gr[V[i]].pb({U[i],W[i]});
}
d=0; nd=0; dist[0]=0;
dfs(X);
for(int i=0; i<N; i++){
fix[i]=0;
}
nd++; d=0; dist[nd]=0; dfs(Y);
sort(dist,dist+nd+1);
int sm=0,ans=0;
for(int i=0; i<2*N; i++){
if(sm+dist[i]>K){
break;
}
sm+=dist[i];
ans++;
}
return ans;
}