oj.uz

답안 #1008200

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1008200 2024-06-26T08:21:21 Z imarn 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 3000 ms 118392 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
using namespace std;
const int mxn=1e5+5;
vector<pair<int,double>>g[mxn];
double d[67][mxn]{0};
bool vis[mxn]{0};
void dfs(int u,int n){
    vis[u]=1;
    for(auto v:g[u]){
        if(v.f==n||vis[v.f])continue;
        dfs(v.f,n);
    }
}
priority_queue<pair<double,pii>,vector<pair<double,pii>>,greater<pair<double,pii>>>q;
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
    K=min(K,66);for(int i=0;i<M;i++)g[x[i]].pb({y[i],c[i]}),g[y[i]].pb({x[i],c[i]});dfs(0,H);
    for(int i=0;i<=K;i++)for(int j=0;j<N;j++)d[i][j]=1e17;
    d[0][0]=0;q.push({0,{0,0}});arr[0]=0;double ans=1e17;
    for(int i=1;i<N;i++)if(arr[i]==0&&vis[i])d[0][i]=0,q.push({0,{0,i}});
    while(!q.empty()){
        auto u=q.top();q.pop();
        if(d[u.s.f][u.s.s]<u.f)continue;
        if(u.s.s==H){ans=min(ans,u.f);continue;}
        for(auto v:g[u.s.s]){
            if(!arr[v.f])continue;
            if(d[u.s.f][v.f]>u.f+v.s)d[u.s.f][v.f]=u.f+v.s,q.push({u.f+v.s,{u.s.f,v.f}});
            if(arr[v.f]==2&&u.s.f<K){
                double t = (u.f+v.s)/2;
                if(d[u.s.f+1][v.f]>t)d[u.s.f+1][v.f]=t,q.push({t,{u.s.f+1,v.f}});
            }
        }
    }for(int i=0;i<N;i++)g[i].clear();memset(vis,0,sizeof vis);
    return (ans>=1e17?-1:ans);
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 28508 KB Correct.
2 Correct 25 ms 28508 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 28760 KB Correct.
2 Correct 20 ms 28764 KB Correct.
3 Correct 20 ms 28736 KB Correct.
4 Correct 20 ms 28764 KB Correct.
5 Correct 20 ms 28764 KB Correct.
6 Correct 20 ms 29416 KB Correct.
7 Correct 24 ms 29532 KB Correct.
8 Correct 12 ms 30300 KB Correct.
9 Correct 19 ms 28516 KB Correct.
10 Correct 19 ms 28508 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 28760 KB Correct.
2 Correct 21 ms 28760 KB Correct.
3 Correct 20 ms 28764 KB Correct.
4 Correct 21 ms 28632 KB Correct.
5 Correct 25 ms 28508 KB Correct.
6 Correct 7 ms 29276 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 35532 KB Correct.
2 Correct 175 ms 28784 KB Correct.
3 Correct 153 ms 29520 KB Correct.
4 Correct 153 ms 29520 KB Correct.
5 Correct 140 ms 29192 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 28764 KB Correct.
2 Correct 19 ms 28764 KB Correct.
3 Correct 18 ms 28872 KB Correct.
4 Correct 21 ms 30000 KB Correct.
5 Correct 18 ms 28508 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 28764 KB Correct.
2 Correct 19 ms 28764 KB Correct.
3 Correct 33 ms 35164 KB Correct.
4 Correct 14 ms 29532 KB Correct.
5 Correct 19 ms 28636 KB Correct.
6 Correct 18 ms 28816 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 178 ms 29016 KB Correct.
2 Correct 27 ms 29404 KB Correct.
3 Correct 472 ms 30352 KB Correct.
4 Correct 432 ms 28704 KB Correct.
5 Correct 590 ms 69800 KB Correct.
6 Correct 284 ms 53692 KB Correct.
7 Correct 405 ms 30488 KB Correct.
8 Correct 419 ms 30288 KB Correct.
9 Correct 160 ms 29908 KB Correct.
10 Correct 163 ms 29768 KB Correct.
11 Correct 398 ms 30132 KB Correct.
12 Correct 163 ms 29920 KB Correct.
13 Correct 178 ms 29900 KB Correct.
14 Correct 362 ms 33388 KB Correct.
15 Correct 411 ms 31484 KB Correct.
16 Correct 156 ms 29896 KB Correct.
17 Correct 173 ms 29896 KB Correct.
18 Correct 181 ms 29900 KB Correct.
19 Correct 383 ms 30312 KB Correct.
20 Correct 15 ms 28764 KB Correct.
21 Correct 17 ms 29020 KB Correct.
22 Correct 28 ms 31448 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 553 ms 40304 KB Correct.
2 Correct 79 ms 41672 KB Correct.
3 Correct 418 ms 66896 KB Correct.
4 Correct 842 ms 42612 KB Correct.
5 Correct 2137 ms 118392 KB Correct.
6 Correct 1108 ms 111300 KB Correct.
7 Correct 999 ms 53976 KB Correct.
8 Correct 983 ms 39112 KB Correct.
9 Correct 518 ms 41980 KB Correct.
10 Correct 594 ms 39804 KB Correct.
11 Correct 1802 ms 39868 KB Correct.
12 Correct 533 ms 39376 KB Correct.
13 Correct 630 ms 39620 KB Correct.
14 Execution timed out 3015 ms 117216 KB Time limit exceeded
15 Halted 0 ms 0 KB -