| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1267045 | imarn | Closing Time (IOI23_closing) | C++20 | 0 ms | 0 KiB |
//#include "festival.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define sz(x) (ll)x.size()
#define cd complex<double>
#define t3 tuple<ll,ll,ll>
using namespace std;
const int mxn=2e5+5;
vector<pll>g[mxn];
ll d[2][mxn]{0};
int lvl[mxn]{0};
int core[mxn]{0};
void dfs(int i,int u,int p){
for(auto [v,w]:g[u]){
if(v==p)continue;
d[i][v]=d[i][u]+w;dfs(i,v,u);
}
}multiset<pll>ms;
int max_score(int N, int X, int Y,ll K,vector<int>U,vector<int>V,vector<int>W){
for(int i=0;i<N-1;i++)g[U[i]].pb({V[i],W[i]}),g[V[i]].pb({U[i],W[i]});
dfs(0,X,X);dfs(1,Y,Y);ll sum=0;int rs1=0;ms.insert({0,-1});
priority_queue<ll,vector<ll>,greater<ll>>pq;
priority_queue<pll,vector<pll>,greater<pll>>q1,q2;
for(int i=0;i<N;i++)pq.push(d[0][i]),pq.push(d[1][i]);
while(!pq.empty()&&sum+pq.top()<=K){
sum+=pq.top();rs1++;pq.pop();
}for(int i=0;i<N;i++){
if(d[0][i]>d[1][i])swap(d[0][i],d[1][i]);
d[1][i]-=d[0][i];
}sum=0;int rs2=0;
for(int i=0;i<N;i++)if(2*d[0][i]+d[1][i]==d[1][X])sum+=d[0][i],rs2++,lvl[i]=1,q1.push({d[1][i],i+1}),core[i]=1;
for(int i=0;i<N;i++)if(lvl[i]==0)q1.push({d[0][i],-(i+1)}),q2.push({d[0][i]+d[1][i],i+1});
if(sum>K)return rs1;
/*while(!q1.empty()||!q2.empty()){
if(q2.empty()){
auto [x,i]=q1.top();q1.pop();
int lv=(i>0);i=abs(i);i--;
if(lvl[i]>lv)continue;
if(sum+x>K)return max(rs1,rs2);sum+=x;rs2++;
if(lvl[i]==0)lvl[i]=1,ms.insert({x,i}),q1.push({d[1][i],i+1});
else if(lvl[i]==1){
lvl[i]=2;
if(!core[i])ms.erase({d[0][i],i});
ms.insert({x,i});
}
}
else if(q1.empty()){
auto [x,i]=q2.top();q2.pop();i--;
if(lvl[i]!=0)continue;
if(sum+x>K)return max(rs1,rs2);sum+=x;rs2+=2;
lvl[i]=2;ms.insert({d[1][i],i});
}
else if(q1.top().f<=q2.top().f-(--ms.end())->f){
auto [x,i]=q1.top();q1.pop();
int lv=(i>0);i=abs(i);i--;
if(sum+x>K)return max(rs1,rs2);sum+=x;rs2++;
if(lvl[i]==0)lvl[i]=1,ms.insert({x,i}),q1.push({d[1][i],i+1});
else if(lvl[i]==1){
lvl[i]=2;
if(!core[i])ms.erase({d[0][i],i});
ms.insert({x,i});
}
}
else {
auto [x,i]=q2.top();q2.pop();i--;
if(lvl[i]!=0)continue;
if(sum+x-(--ms.end())->f>K)return max(rs1,rs2);sum+=x-(--ms.end())->f;rs2++;
auto it = (--ms.end());
if(lvl[it->s]==1){
lvl[it->s]=0;
q1.push({d[0][it->s],-it->s-1});
//q2.push({d[0][it->s]+d[1][it->s],it->s+1});
ms.erase(it);
}
else if(lvl[it->s]==2){
lvl[it->s]=1;
q1.push({d[1][it->s],it->s+1});
if(!core[i])ms.insert({d[0][it->s],it->s});
ms.erase(it);
}
lvl[i]=2;ms.insert({d[1][i],i});
}*/
}return max(rs1,rs2);
}
/*int main(){
cout<<max_score(7, 0, 2, 10,{0, 0, 1, 2, 2, 5},{1, 3, 2, 4, 5, 6},{2, 3, 4, 2, 5, 3});
}*/