oj.uz

Submission #849127

# Submission time Handle Problem Language Result Execution time Memory
849127 2023-09-14T06:42:50 Z adhityamv Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 222872 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=100000;
vector<pair<int,double>> edges[N];
bool visited[N]={};
double ans[101][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){
    k=min(k,100);
    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 28508 KB Correct.
2 Correct 21 ms 28764 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28508 KB Correct.
2 Correct 27 ms 28580 KB Correct.
3 Correct 23 ms 28504 KB Correct.
4 Correct 24 ms 28504 KB Correct.
5 Correct 24 ms 28616 KB Correct.
6 Correct 23 ms 29456 KB Correct.
7 Correct 27 ms 29216 KB Correct.
8 Correct 14 ms 30216 KB Correct.
9 Correct 23 ms 28252 KB Correct.
10 Correct 22 ms 28252 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 28508 KB Correct.
2 Correct 26 ms 28512 KB Correct.
3 Correct 23 ms 28504 KB Correct.
4 Correct 24 ms 28248 KB Correct.
5 Correct 24 ms 28260 KB Correct.
6 Correct 8 ms 29276 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 38584 KB Correct.
2 Correct 271 ms 28888 KB Correct.
3 Correct 251 ms 28896 KB Correct.
4 Correct 262 ms 29020 KB Correct.
5 Correct 212 ms 28508 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28504 KB Correct.
2 Correct 31 ms 28648 KB Correct.
3 Correct 23 ms 28764 KB Correct.
4 Correct 23 ms 29788 KB Correct.
5 Correct 20 ms 28252 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28504 KB Correct.
2 Correct 21 ms 28508 KB Correct.
3 Correct 40 ms 34908 KB Correct.
4 Correct 17 ms 29392 KB Correct.
5 Correct 22 ms 28252 KB Correct.
6 Correct 23 ms 28504 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 29568 KB Correct.
2 Correct 41 ms 30348 KB Correct.
3 Correct 609 ms 28520 KB Correct.
4 Correct 479 ms 27280 KB Correct.
5 Correct 1132 ms 69544 KB Correct.
6 Correct 481 ms 68776 KB Correct.
7 Correct 463 ms 28816 KB Correct.
8 Correct 481 ms 27016 KB Correct.
9 Correct 253 ms 29948 KB Correct.
10 Correct 248 ms 29648 KB Correct.
11 Correct 474 ms 26836 KB Correct.
12 Correct 260 ms 29656 KB Correct.
13 Correct 277 ms 29512 KB Correct.
14 Correct 383 ms 32328 KB Correct.
15 Correct 471 ms 28156 KB Correct.
16 Correct 250 ms 29512 KB Correct.
17 Correct 304 ms 29484 KB Correct.
18 Correct 299 ms 29584 KB Correct.
19 Correct 705 ms 29436 KB Correct.
20 Correct 23 ms 28760 KB Correct.
21 Correct 22 ms 28964 KB Correct.
22 Correct 36 ms 31192 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1351 ms 88524 KB Correct.
2 Correct 185 ms 89940 KB Correct.
3 Correct 765 ms 94292 KB Correct.
4 Correct 1228 ms 87180 KB Correct.
5 Execution timed out 3072 ms 222872 KB Time limit exceeded
6 Halted 0 ms 0 KB -