oj.uz

Submission #982127

# Submission time Handle Problem Language Result Execution time Memory
982127 2024-05-13T22:26:38 Z logangd Cyberland (APIO23_cyberland) C++17
100 / 100
 2975 ms 65764 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;

vector<pair<int,int>>ad[100005];
vector<int>rs,ar,vs(100005);
int h;

void dfs(int u){
    if(u==h)return;
    if(ar[u]==0)rs.push_back(u);
    vs[u]=1;
    for(auto v:ad[u])
        if(!vs[v.first])
            dfs(v.first);
}

double solve(int N,int M,int K,int H,vector<int>x,vector<int>y,vector<int>c,vector<int>arr) {
	int wha=70;
    h=H;
    for(int i=0;i<N;i++)ad[i].clear(),vs[i]=0;
    for(int i=0;i<M;i++)
        ad[x[i]].push_back({y[i],c[i]}),
        ad[y[i]].push_back({x[i],c[i]});
    rs.clear();
    ar.clear();
    rs.push_back(0);
    for(auto i:arr)ar.push_back(i);
    dfs(0);
    priority_queue<pair<double,pair<int,int>>>dj;
    for(auto i:rs)dj.push({0,{i,0}});
    double R[N][min(K,wha)+1];
    for(int i=0;i<N;i++)
        for(int j=0;j<=min(K,wha);j++)R[i][j]=1;
    
    for(int i=0;i<=min(K,wha);i++){
        priority_queue<pair<double,pair<int,int>>>djn;
        while(!dj.empty()){
            auto t=dj.top();
            dj.pop();
            if(R[t.second.first][t.second.second]!=1)continue;
            R[t.second.first][t.second.second]=t.first;
            if(t.second.first==H)continue;
            if(arr[t.second.first]==2&&t.second.second<min(K,wha))
            for(auto j:ad[t.second.first])djn.push({t.first/2-j.second,{j.first,t.second.second+1}});
            for(auto j:ad[t.second.first])dj.push({t.first-j.second,{j.first,t.second.second}});
        }
        swap(dj,djn);
    }
    double res=R[H][0];
    for(int i=1;i<=min(K,wha);i++)if(R[H][i]!=1)res=max(res,R[H][i]);
    return -res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3164 KB Correct.
2 Correct 18 ms 3164 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3420 KB Correct.
2 Correct 30 ms 3612 KB Correct.
3 Correct 31 ms 3420 KB Correct.
4 Correct 26 ms 3420 KB Correct.
5 Correct 27 ms 3592 KB Correct.
6 Correct 25 ms 6288 KB Correct.
7 Correct 32 ms 6236 KB Correct.
8 Correct 16 ms 9304 KB Correct.
9 Correct 29 ms 3164 KB Correct.
10 Correct 25 ms 3164 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3416 KB Correct.
2 Correct 29 ms 3616 KB Correct.
3 Correct 29 ms 3656 KB Correct.
4 Correct 27 ms 3160 KB Correct.
5 Correct 27 ms 3164 KB Correct.
6 Correct 8 ms 5980 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 21676 KB Correct.
2 Correct 206 ms 3420 KB Correct.
3 Correct 180 ms 3672 KB Correct.
4 Correct 197 ms 3508 KB Correct.
5 Correct 96 ms 3268 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3676 KB Correct.
2 Correct 25 ms 3420 KB Correct.
3 Correct 25 ms 3612 KB Correct.
4 Correct 28 ms 6724 KB Correct.
5 Correct 21 ms 3288 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3648 KB Correct.
2 Correct 23 ms 3684 KB Correct.
3 Correct 43 ms 27096 KB Correct.
4 Correct 19 ms 5800 KB Correct.
5 Correct 31 ms 3164 KB Correct.
6 Correct 25 ms 3676 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 3676 KB Correct.
2 Correct 68 ms 3876 KB Correct.
3 Correct 824 ms 24004 KB Correct.
4 Correct 448 ms 8864 KB Correct.
5 Correct 1331 ms 20604 KB Correct.
6 Correct 1205 ms 16736 KB Correct.
7 Correct 429 ms 8532 KB Correct.
8 Correct 348 ms 4352 KB Correct.
9 Correct 318 ms 3668 KB Correct.
10 Correct 298 ms 3672 KB Correct.
11 Correct 314 ms 3752 KB Correct.
12 Correct 324 ms 3720 KB Correct.
13 Correct 341 ms 3668 KB Correct.
14 Correct 442 ms 9392 KB Correct.
15 Correct 406 ms 5452 KB Correct.
16 Correct 351 ms 3696 KB Correct.
17 Correct 375 ms 3668 KB Correct.
18 Correct 358 ms 3676 KB Correct.
19 Correct 712 ms 3844 KB Correct.
20 Correct 14 ms 3160 KB Correct.
21 Correct 22 ms 3420 KB Correct.
22 Correct 99 ms 4608 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 839 ms 4184 KB Correct.
2 Correct 138 ms 4416 KB Correct.
3 Correct 662 ms 65764 KB Correct.
4 Correct 509 ms 5880 KB Correct.
5 Correct 2975 ms 31608 KB Correct.
6 Correct 2540 ms 21108 KB Correct.
7 Correct 872 ms 16576 KB Correct.
8 Correct 462 ms 4280 KB Correct.
9 Correct 692 ms 3920 KB Correct.
10 Correct 655 ms 4060 KB Correct.
11 Correct 242 ms 3508 KB Correct.
12 Correct 686 ms 3876 KB Correct.
13 Correct 750 ms 4460 KB Correct.
14 Correct 2640 ms 30312 KB Correct.
15 Correct 1661 ms 34440 KB Correct.
16 Correct 781 ms 13944 KB Correct.
17 Correct 510 ms 5428 KB Correct.
18 Correct 734 ms 3888 KB Correct.
19 Correct 816 ms 4012 KB Correct.
20 Correct 800 ms 3920 KB Correct.
21 Correct 1578 ms 3912 KB Correct.
22 Correct 24 ms 3164 KB Correct.
23 Correct 46 ms 3672 KB Correct.
24 Correct 225 ms 5080 KB Correct.