# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1081083 | Rawlat_vanak | Cyberland (APIO23_cyberland) | C++17 | 572 ms | 25800 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 <bits/stdc++.h>
using namespace std;
//#define long long long long
#define speedIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define f first
#define s second
#define pii pair<double,long long>
#define pb push_back
vector<vector<pair<long long, long long>>> graph;
vector<long long> parent,sz;
long long find(long long u){
while(u!=parent[u]) u=parent[u];
return parent[u];
}
void unite(long long a,long long b){
a=find(a);b=find(b);
if(a==b) return;
if(sz[b]>sz[a]) swap(a,b);
parent[b]=a;
sz[a]+=sz[b];
}
double solve(int N,int M,int K,int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
long long n=N,m=M,k=K,h=H;
parent.resize(n);
for(long long i=0;i<n;i++){
parent[i]=i;
}
sz.resize(n,1);
graph.resize(n);
for(long long i=0;i<n;i++){
graph[x[i]].pb({y[i],c[i]});
graph[y[i]].pb({x[i],c[i]});
unite(x[i],y[i]);
}
priority_queue<pii> q;
vector<vector<double>> dist(n,vector<double>(k+1,1e15));
vector<bool> visited(n,false);
for(long long j=0;j<=k;j++){
if(find(0)==find(h)){
dist[0][j]=0;
q.push({0,0});
}
visited[0]=false;
for(long long i=1;i<n;i++){
visited[i]=false;
if(arr[i]==0 and find(i)==find(h)){
dist[i][j]=0;
q.push({0,i});
}
}
while(!q.empty()){
pii u=q.top();
long long v=u.s;
q.pop();
if(visited[v]) continue;
visited[v]=true;
for(pii w: graph[v]){
long long xxxx=w.f;
if(arr[xxxx]==1){
if(dist[w.f][j]>dist[v][j]+w.s){
dist[w.f][j]=dist[v][j]+w.s;
q.push({-dist[w.f][j],w.f});
}
}else if(arr[xxxx]==2){
if(dist[w.f][j]>dist[v][j]+w.s){
dist[w.f][j]=dist[v][j]+w.s;
q.push({-dist[w.f][j],w.f});
}
if(j>=1){
if(dist[xxxx][j]>(dist[v][j-1]+w.s)/2){
dist[xxxx][j]=(dist[v][j-1]+w.s)/2;
q.push({-dist[xxxx][j],xxxx});
}
}
}
}
}
}
double ans=1e15;
for(long long i=0;i<=k;i++){
ans=min(ans,dist[h][i]);
}
for(long long i=0;i<n;i++){
graph[i].clear();
dist[i].clear();
parent.clear();
visited.clear();
sz.clear();
}
if(ans==1e15){
return -1;
}else{
return ans;
}
}
Compilation message (stderr)
# | 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... |