oj.uz

답안 #1008156

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1008156 2024-06-26T08:02:10 Z imarn 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 3000 ms 195576 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,double>>g[mxn];
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]=1e17;
    priority_queue<pair<double,pii>,vector<pair<double,pii>>,greater<pair<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){
                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}});
            }
        }
    }double ans=1e17;
    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:43:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   43 |     for(int i=0;i<N;i++)g[i].clear();memset(vis,0,sizeof vis);
      |     ^~~
cyberland.cpp:43:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   43 |     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 34 ms 29016 KB Correct.
2 Correct 29 ms 29020 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 29020 KB Correct.
2 Correct 26 ms 29020 KB Correct.
3 Correct 20 ms 29016 KB Correct.
4 Correct 20 ms 29012 KB Correct.
5 Correct 20 ms 29020 KB Correct.
6 Correct 19 ms 29776 KB Correct.
7 Correct 23 ms 29788 KB Correct.
8 Correct 13 ms 30552 KB Correct.
9 Correct 20 ms 28764 KB Correct.
10 Correct 19 ms 28760 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 29016 KB Correct.
2 Correct 22 ms 29016 KB Correct.
3 Correct 20 ms 29016 KB Correct.
4 Correct 27 ms 28764 KB Correct.
5 Correct 27 ms 28940 KB Correct.
6 Correct 7 ms 29788 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 205 ms 39644 KB Correct.
2 Correct 255 ms 29320 KB Correct.
3 Correct 228 ms 29368 KB Correct.
4 Correct 245 ms 29416 KB Correct.
5 Correct 204 ms 29008 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 29020 KB Correct.
2 Correct 19 ms 29020 KB Correct.
3 Correct 17 ms 29016 KB Correct.
4 Correct 28 ms 30192 KB Correct.
5 Correct 20 ms 28764 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 29016 KB Correct.
2 Correct 17 ms 29164 KB Correct.
3 Correct 29 ms 35420 KB Correct.
4 Correct 13 ms 30040 KB Correct.
5 Correct 19 ms 28764 KB Correct.
6 Correct 22 ms 29268 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 289 ms 30044 KB Correct.
2 Correct 39 ms 30856 KB Correct.
3 Correct 523 ms 28944 KB Correct.
4 Correct 423 ms 27712 KB Correct.
5 Correct 908 ms 69128 KB Correct.
6 Correct 402 ms 69296 KB Correct.
7 Correct 420 ms 29116 KB Correct.
8 Correct 439 ms 29520 KB Correct.
9 Correct 213 ms 30504 KB Correct.
10 Correct 249 ms 30028 KB Correct.
11 Correct 428 ms 29260 KB Correct.
12 Correct 269 ms 30072 KB Correct.
13 Correct 272 ms 29992 KB Correct.
14 Correct 334 ms 32524 KB Correct.
15 Correct 402 ms 30780 KB Correct.
16 Correct 221 ms 30004 KB Correct.
17 Correct 275 ms 29924 KB Correct.
18 Correct 254 ms 29940 KB Correct.
19 Correct 678 ms 30108 KB Correct.
20 Correct 21 ms 29272 KB Correct.
21 Correct 20 ms 29476 KB Correct.
22 Correct 34 ms 31448 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 791 ms 61396 KB Correct.
2 Correct 129 ms 64348 KB Correct.
3 Correct 426 ms 67408 KB Correct.
4 Correct 972 ms 60112 KB Correct.
5 Execution timed out 3047 ms 195576 KB Time limit exceeded
6 Halted 0 ms 0 KB -