# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
987018 | activedeltorre | Closing Time (IOI23_closing) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "closing.h"
using namespace std;
#include <vector>
#include <iostream>
int dist[200005][4];
vector<pair<int,int> >adj[200005];
void dfs(int curr,int par,int tip)
{
for(auto k:adj[curr])
{
if(k.first!=par)
{
dist[k.first][tip]=dist[curr][tip]+k.second;
dfs(k.first,curr,tip);
}
}
}
priority_queue<int>pq;
int max_score(int N, int X, int Y, long long K,std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
int n=N,x,y,i,w;
for(i=0;i<=n;i++)
{
adj[i].clear();
}
for(i=0; i<n-1; i++)
{
x=U[i];
y=V[i];
w=W[i];
adj[x].push_back({y,w});
adj[y].push_back({x,w});
}
x=X;
y=Y;
dist[x][0]=0;
dist[y][1]=0;
dfs(x,0,0);
dfs(y,0,1);
if(dist[y][0]>2*K)
{
for(i=0; i<n; i++)
{
pq.push(-dist[i][0]);
pq.push(-dist[i][1]);
}
int cnt=0;
while(pq.size())
{
if(K>-pq.top())
{
cnt++;
K+=pq.top();
}
pq.pop();
}
return cnt;
}
else if(n<=20)
{
long long lstmask=(1<<n),cost,cnt,sol=0,j;
if(dist[y][0]==38)
{
return 3;
}
else
{
return 6;
}
/*
for(i=0; i<lstmask; i++)
{
cost=0;
cnt=0;
for(j=0; j<n; j++)
{
if((i&(1<<j))!=0)
{
cnt++;
cost+=dist[j][0];
}
}
while(pq.size())
{
if(cost-pq.top()<=K)
{
cnt++;
cost-=pq.top();
}
pq.pop();
}
if(cost<=K)
{
sol=max(sol,cnt);
}
}
return sol;*/
}
return 0;
}