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 <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define ppll pair<ll,pll>
#define vpl vector<pll>
const int N=5e5+10;
vpl ma[N];
ll paid[N],dist[N];
bool vis[N];
// ll dist_[2][N];
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<2*n;i++)
{
ma[i].clear();
paid[i]=0;
vis[i]=0;
dist[i]=k+1;
}
int m=U.size();
for(int i=0;i<m;i++)
{
ma[U[i]].push_back({W[i],V[i]});
ma[U[i]+n].push_back({W[i],V[i]+n});
ma[V[i]].push_back({W[i],U[i]});
ma[V[i]+n].push_back({W[i],U[i]+n});
}
set<pll> pq;
pq.insert({0,x});
pq.insert({0,y+n});
dist[x]=0;
dist[y+n]=0;
ll cur=0;
while(pq.size()>0)
{
pll it=*pq.begin();
pq.erase(begin(pq));
int u=it.second;
ll c=it.first;
if(vis[u])continue;
ll og=cur;
cur+=c;
if(u<n)
{
// paid[u+n]+=c;
if(vis[u+n])
cur-=min(c,dist[u+n]);
}
else
{
if(vis[u-n])
cur-=min(c,dist[u-n]);
}
if((cur)>k)
{
cur=og;
continue;
}
vis[u]=1;
for(auto [w,v]:ma[u])
{
ll cop=c+w;
if(dist[v]>(cop))
{
dist[v]=cop;
pq.insert({cop,v});
}
}
}
int total=0;
for(int i=0;i<2*n;i++)
{
total+=vis[i];
}
return total;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |