oj.uz

Submission #773246

# Submission time Handle Problem Language Result Execution time Memory
773246 2023-07-04T17:31:55 Z JakobZorz Cyberland (APIO23_cyberland) C++17
100 / 100
 95 ms 15852 KB 
#include "cyberland.h"
#include <vector>
#include <iostream>
#include <limits.h>
#include <queue>
#include <algorithm>
typedef long long ll;
typedef double lld;
const lld MAX_DIST=10000000000000000000000000.0;
using namespace std;

int n,m,k,h;
vector<pair<int,lld>>nodes[100000];
lld dist[100000];
lld old_dist[100000];
bool vis[100000];

void dfs(int node){
    if(vis[node])
        return;
    vis[node]=true;
    if(node==h)
        return;
    for(pair<int,lld>ne:nodes[node]){
        dfs(ne.first);
    }
}

double solve(int N,int M,int K,int H,vector<int>x,vector<int>y,vector<int>c,vector<int>arr){
    n=N;
    m=M;
    k=K;
    h=H;
    for(int i=0;i<n;i++){
        nodes[i].clear();
        dist[i]=MAX_DIST;
        vis[i]=false;
    }
    for(int i=0;i<m;i++){
        nodes[x[i]].emplace_back(y[i],c[i]);
        nodes[y[i]].emplace_back(x[i],c[i]);
    }
    dfs(0);
    dist[0]=0;
    queue<int>q;
    q.push(0);
    if(!vis[h])
        return -1;
    for(int i=0;i<n;i++){
        if(arr[i]==0&&vis[i]){
            dist[i]=0;
            q.push(i);
        }
    }
    
    k=min(100,k);
    
    for(int j=0;j<k;j++){
        while(!q.empty()){
            int curr=q.front();
            q.pop();
            if(curr==h)
                continue;
            for(pair<int,lld>ne:nodes[curr]){
                lld new_dist=dist[curr]+ne.second;
                if(new_dist<dist[ne.first]){
                    dist[ne.first]=new_dist;
                    q.push(ne.first);
                }
            }
        }
        
        for(int i=0;i<n;i++)
            old_dist[i]=dist[i];
        
        for(int i=0;i<n;i++){
            if(arr[i]==2&&vis[i]){
                for(pair<int,lld>ne:nodes[i]){
                    lld new_dist=old_dist[i]/2.0+ne.second;
                    if(new_dist<dist[ne.first]){
                        dist[ne.first]=new_dist;
                        q.push(ne.first);
                    }
                }
            }
        }
        
        if(q.empty())
            break;
    }
    
    while(!q.empty()){
        int curr=q.front();
        q.pop();
        if(curr==h)
            continue;
        for(pair<int,lld>ne:nodes[curr]){
            lld new_dist=dist[curr]+ne.second;
            if(new_dist<dist[ne.first]){
                dist[ne.first]=new_dist;
                q.push(ne.first);
            }
        }
    }
    
    return dist[h];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2900 KB Correct.
2 Correct 15 ms 3064 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3296 KB Correct.
2 Correct 18 ms 3496 KB Correct.
3 Correct 18 ms 3412 KB Correct.
4 Correct 18 ms 3480 KB Correct.
5 Correct 18 ms 3412 KB Correct.
6 Correct 16 ms 4340 KB Correct.
7 Correct 21 ms 4280 KB Correct.
8 Correct 10 ms 4948 KB Correct.
9 Correct 18 ms 3336 KB Correct.
10 Correct 17 ms 3272 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3404 KB Correct.
2 Correct 21 ms 3484 KB Correct.
3 Correct 16 ms 3412 KB Correct.
4 Correct 25 ms 3008 KB Correct.
5 Correct 19 ms 3384 KB Correct.
6 Correct 5 ms 3572 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9248 KB Correct.
2 Correct 30 ms 3412 KB Correct.
3 Correct 20 ms 3448 KB Correct.
4 Correct 26 ms 3568 KB Correct.
5 Correct 22 ms 3288 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3572 KB Correct.
2 Correct 20 ms 3592 KB Correct.
3 Correct 18 ms 3536 KB Correct.
4 Correct 19 ms 4836 KB Correct.
5 Correct 16 ms 3312 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3560 KB Correct.
2 Correct 16 ms 3620 KB Correct.
3 Correct 34 ms 10404 KB Correct.
4 Correct 13 ms 4436 KB Correct.
5 Correct 18 ms 3332 KB Correct.
6 Correct 17 ms 3564 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3584 KB Correct.
2 Correct 4 ms 3028 KB Correct.
3 Correct 58 ms 13032 KB Correct.
4 Correct 56 ms 5676 KB Correct.
5 Correct 55 ms 10784 KB Correct.
6 Correct 35 ms 9408 KB Correct.
7 Correct 48 ms 5612 KB Correct.
8 Correct 43 ms 3660 KB Correct.
9 Correct 19 ms 3424 KB Correct.
10 Correct 19 ms 3408 KB Correct.
11 Correct 42 ms 3524 KB Correct.
12 Correct 25 ms 3768 KB Correct.
13 Correct 21 ms 3820 KB Correct.
14 Correct 53 ms 9452 KB Correct.
15 Correct 46 ms 6104 KB Correct.
16 Correct 21 ms 3796 KB Correct.
17 Correct 22 ms 4024 KB Correct.
18 Correct 20 ms 3948 KB Correct.
19 Correct 44 ms 4700 KB Correct.
20 Correct 3 ms 2772 KB Correct.
21 Correct 3 ms 2804 KB Correct.
22 Correct 4 ms 3412 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3524 KB Correct.
2 Correct 5 ms 3028 KB Correct.
3 Correct 75 ms 15852 KB Correct.
4 Correct 50 ms 4192 KB Correct.
5 Correct 74 ms 10772 KB Correct.
6 Correct 43 ms 9360 KB Correct.
7 Correct 68 ms 7800 KB Correct.
8 Correct 59 ms 3516 KB Correct.
9 Correct 22 ms 3496 KB Correct.
10 Correct 22 ms 3468 KB Correct.
11 Correct 59 ms 3400 KB Correct.
12 Correct 24 ms 3444 KB Correct.
13 Correct 26 ms 3420 KB Correct.
14 Correct 95 ms 9772 KB Correct.
15 Correct 83 ms 8384 KB Correct.
16 Correct 67 ms 5480 KB Correct.
17 Correct 46 ms 3720 KB Correct.
18 Correct 23 ms 3492 KB Correct.
19 Correct 26 ms 3280 KB Correct.
20 Correct 24 ms 3228 KB Correct.
21 Correct 50 ms 2888 KB Correct.
22 Correct 3 ms 2644 KB Correct.
23 Correct 3 ms 2772 KB Correct.
24 Correct 5 ms 3284 KB Correct.