oj.uz

답안 #1008143

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1008143 2024-06-26T07:57:26 Z imarn 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 3000 ms 376904 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#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,long double>>g[mxn];
long double d[70][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);
    }
}
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,69);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]=1e18;
    priority_queue<pair<long double,pii>,vector<pair<long double,pii>>,greater<pair<long double,pii>>>q;d[0][0]=0;q.push({0,{0,0}});
    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)continue;
        for(auto v:g[u.s.s]){
            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&&d[u.s.f+1][v.f]>(u.f+v.s)/2)d[u.s.f+1][v.f]=(u.f+v.s)/2,q.push({(u.f+v.s)/2,{u.s.f+1,v.f}});
        }
    }long double ans=1e18;
    for(int i=0;i<=K;i++)ans=min(ans,d[i][H]);
    for(int i=0;i<N;i++)g[i].clear();memset(vis,0,sizeof vis);
    return (ans>=1e17?-1:ans);
}

Compilation message

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:40:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   40 |     for(int i=0;i<N;i++)g[i].clear();memset(vis,0,sizeof vis);
      |     ^~~
cyberland.cpp:40:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   40 |     for(int i=0;i<N;i++)g[i].clear();memset(vis,0,sizeof vis);
      |                                      ^~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 50780 KB Correct.
2 Correct 40 ms 50928 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 51036 KB Correct.
2 Correct 41 ms 51100 KB Correct.
3 Correct 38 ms 51036 KB Correct.
4 Correct 38 ms 51032 KB Correct.
5 Correct 36 ms 51108 KB Correct.
6 Correct 35 ms 52316 KB Correct.
7 Correct 46 ms 52352 KB Correct.
8 Correct 23 ms 55444 KB Correct.
9 Correct 34 ms 50912 KB Correct.
10 Correct 32 ms 50932 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 51112 KB Correct.
2 Correct 36 ms 51036 KB Correct.
3 Correct 38 ms 51124 KB Correct.
4 Correct 36 ms 50912 KB Correct.
5 Correct 37 ms 50780 KB Correct.
6 Correct 17 ms 52060 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 420 ms 68964 KB Correct.
2 Correct 536 ms 51780 KB Correct.
3 Correct 428 ms 51820 KB Correct.
4 Correct 466 ms 51732 KB Correct.
5 Correct 364 ms 51036 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 51284 KB Correct.
2 Correct 32 ms 51148 KB Correct.
3 Correct 35 ms 51284 KB Correct.
4 Correct 34 ms 53256 KB Correct.
5 Correct 30 ms 50940 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 51288 KB Correct.
2 Correct 28 ms 51292 KB Correct.
3 Correct 52 ms 62316 KB Correct.
4 Correct 24 ms 52720 KB Correct.
5 Correct 32 ms 50776 KB Correct.
6 Correct 30 ms 51280 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 474 ms 53112 KB Correct.
2 Correct 69 ms 54592 KB Correct.
3 Correct 986 ms 49024 KB Correct.
4 Correct 850 ms 47552 KB Correct.
5 Correct 1781 ms 129188 KB Correct.
6 Correct 947 ms 127396 KB Correct.
7 Correct 818 ms 52944 KB Correct.
8 Correct 820 ms 51976 KB Correct.
9 Correct 388 ms 54168 KB Correct.
10 Correct 430 ms 53188 KB Correct.
11 Correct 739 ms 51536 KB Correct.
12 Correct 431 ms 53204 KB Correct.
13 Correct 450 ms 53076 KB Correct.
14 Correct 571 ms 56480 KB Correct.
15 Correct 795 ms 54212 KB Correct.
16 Correct 451 ms 53012 KB Correct.
17 Correct 540 ms 52920 KB Correct.
18 Correct 537 ms 52912 KB Correct.
19 Correct 1242 ms 52888 KB Correct.
20 Correct 41 ms 51472 KB Correct.
21 Correct 39 ms 52012 KB Correct.
22 Correct 61 ms 56008 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1768 ms 108060 KB Correct.
2 Correct 249 ms 112976 KB Correct.
3 Correct 1081 ms 125584 KB Correct.
4 Correct 2007 ms 109312 KB Correct.
5 Execution timed out 3077 ms 376904 KB Time limit exceeded
6 Halted 0 ms 0 KB -