oj.uz

Submission #849124

# Submission time Handle Problem Language Result Execution time Memory
849124 2023-09-14T06:40:10 Z adhityamv Cyberland (APIO23_cyberland) C++17
97 / 100
 1147 ms 68740 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=100000;
vector<pair<int,double>> edges[N];
bool visited[N]={};
double ans[31][N];
void dfs(int u,int h){
    for(auto v:edges[u]){
        if(v.first==h) continue;
        if(!visited[v.first]){
            visited[v.first]=true;
            dfs(v.first, h);
        }
    }
}
double solve(int n,int m,int k,int h,vector<int> x,vector<int> y,vector<int> c,vector<int> a){
    for(int j=0;j<=k;j++)for(int i=0;i<n;i++) ans[j][i]=-1;
    for(int i=0;i<m;i++){
        edges[x[i]].push_back(make_pair(y[i],(double) c[i]));
        edges[y[i]].push_back(make_pair(x[i],(double) c[i]));
    }
    priority_queue<pair<double,pair<int,int>>,vector<pair<double,pair<int,int>>>,greater<pair<double,pair<int,int>>>> pq;
    ans[0][0]=0;
    visited[0]=true;
    dfs(0,h);
    pq.push(make_pair(0,make_pair(0,0)));
    for(int i=0;i<n;i++){
        if(a[i]==0 && visited[i]){
            ans[0][i]=0;
            pq.push(make_pair(0,make_pair(0,i)));
        }
    }
    while(!pq.empty()){
        auto u=pq.top();
        pq.pop();
        if(u.second.second==h) continue;
        if(u.first!=ans[u.second.first][u.second.second]) continue;
        for(auto v:edges[u.second.second]){
            if(ans[u.second.first][v.first]==-1 || ans[u.second.first][v.first]>u.first+v.second){
                ans[u.second.first][v.first]=u.first+v.second;
                pq.push(make_pair(ans[u.second.first][v.first],make_pair(u.second.first,v.first)));
            }
            if(a[v.first]==2 && u.second.first<k){
                if(ans[u.second.first+1][v.first]==-1 || ans[u.second.first+1][v.first]>(u.first+v.second)/((double) 2)){
                ans[u.second.first+1][v.first]=(u.first+v.second)/((double) 2);
                pq.push(make_pair(ans[u.second.first+1][v.first],make_pair(u.second.first+1,v.first)));
            }
            }
        }
    }
    double fans=-1;
    for(int j=0;j<=k;j++){
        if(ans[j][h]==-1) continue;
        if(fans==-1 || fans>ans[j][h]) fans=ans[j][h];
    }
    for(int i=0;i<n;i++){
        edges[i].clear();
        visited[i]=false;
    }
    for(int j=0;j<=k;j++) for(int i=0;i<n;i++) ans[j][i]=0;
    return fans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 26968 KB Correct.
2 Correct 21 ms 27224 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 26968 KB Correct.
2 Correct 24 ms 26972 KB Correct.
3 Correct 24 ms 26972 KB Correct.
4 Correct 24 ms 27480 KB Correct.
5 Correct 24 ms 26968 KB Correct.
6 Correct 21 ms 27992 KB Correct.
7 Correct 27 ms 27736 KB Correct.
8 Correct 14 ms 28760 KB Correct.
9 Correct 23 ms 26968 KB Correct.
10 Correct 23 ms 26968 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 26968 KB Correct.
2 Correct 24 ms 26968 KB Correct.
3 Correct 25 ms 27224 KB Correct.
4 Correct 24 ms 26968 KB Correct.
5 Correct 24 ms 26968 KB Correct.
6 Correct 8 ms 27736 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 37828 KB Correct.
2 Correct 270 ms 28376 KB Correct.
3 Correct 250 ms 28384 KB Correct.
4 Correct 253 ms 28404 KB Correct.
5 Correct 214 ms 27984 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 27736 KB Correct.
2 Correct 26 ms 27224 KB Correct.
3 Correct 23 ms 27224 KB Correct.
4 Correct 23 ms 28216 KB Correct.
5 Correct 21 ms 26972 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 27212 KB Correct.
2 Correct 20 ms 27224 KB Correct.
3 Correct 39 ms 33648 KB Correct.
4 Correct 17 ms 27992 KB Correct.
5 Correct 24 ms 27036 KB Correct.
6 Correct 22 ms 27228 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 28120 KB Correct.
2 Correct 43 ms 29144 KB Correct.
3 Correct 724 ms 31456 KB Correct.
4 Correct 516 ms 30148 KB Correct.
5 Correct 1147 ms 68740 KB Correct.
6 Correct 447 ms 68524 KB Correct.
7 Correct 457 ms 31404 KB Correct.
8 Correct 483 ms 29560 KB Correct.
9 Correct 247 ms 29312 KB Correct.
10 Correct 241 ms 29124 KB Correct.
11 Correct 477 ms 29468 KB Correct.
12 Correct 256 ms 29176 KB Correct.
13 Correct 271 ms 29096 KB Correct.
14 Correct 364 ms 35276 KB Correct.
15 Correct 449 ms 31032 KB Correct.
16 Correct 244 ms 28964 KB Correct.
17 Correct 300 ms 29124 KB Correct.
18 Correct 301 ms 29024 KB Correct.
19 Correct 691 ms 30084 KB Correct.
20 Correct 23 ms 27480 KB Correct.
21 Correct 22 ms 27508 KB Correct.
22 Correct 36 ms 29908 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 54360 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -