oj.uz

답안 #1008158

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1008158 2024-06-26T08:03:43 Z imarn 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 832 ms 69152 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[66][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,65);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 27 ms 27740 KB Correct.
2 Correct 24 ms 27936 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 28012 KB Correct.
2 Correct 17 ms 27980 KB Correct.
3 Correct 17 ms 27996 KB Correct.
4 Correct 19 ms 27992 KB Correct.
5 Correct 18 ms 27992 KB Correct.
6 Correct 24 ms 28764 KB Correct.
7 Correct 24 ms 28764 KB Correct.
8 Correct 12 ms 29532 KB Correct.
9 Correct 16 ms 27740 KB Correct.
10 Correct 18 ms 27864 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 27996 KB Correct.
2 Correct 19 ms 27996 KB Correct.
3 Correct 19 ms 27996 KB Correct.
4 Correct 19 ms 27740 KB Correct.
5 Correct 18 ms 27872 KB Correct.
6 Correct 6 ms 28504 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 172 ms 38344 KB Correct.
2 Correct 226 ms 28336 KB Correct.
3 Correct 196 ms 28300 KB Correct.
4 Correct 211 ms 28252 KB Correct.
5 Correct 178 ms 27904 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 27992 KB Correct.
2 Correct 18 ms 27996 KB Correct.
3 Correct 16 ms 27992 KB Correct.
4 Correct 18 ms 29276 KB Correct.
5 Correct 15 ms 27740 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 28092 KB Correct.
2 Correct 15 ms 28076 KB Correct.
3 Correct 35 ms 34268 KB Correct.
4 Correct 13 ms 28760 KB Correct.
5 Correct 18 ms 27736 KB Correct.
6 Correct 15 ms 28088 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 244 ms 28812 KB Correct.
2 Correct 34 ms 29576 KB Correct.
3 Correct 431 ms 27860 KB Correct.
4 Correct 402 ms 26536 KB Correct.
5 Correct 832 ms 69152 KB Correct.
6 Correct 369 ms 66636 KB Correct.
7 Correct 380 ms 28084 KB Correct.
8 Correct 393 ms 28416 KB Correct.
9 Correct 205 ms 29416 KB Correct.
10 Correct 207 ms 29020 KB Correct.
11 Correct 410 ms 28352 KB Correct.
12 Correct 224 ms 29020 KB Correct.
13 Correct 242 ms 29044 KB Correct.
14 Correct 340 ms 31660 KB Correct.
15 Correct 397 ms 29756 KB Correct.
16 Correct 237 ms 28972 KB Correct.
17 Correct 260 ms 28848 KB Correct.
18 Correct 257 ms 28860 KB Correct.
19 Correct 616 ms 28928 KB Correct.
20 Correct 20 ms 28224 KB Correct.
21 Correct 20 ms 28224 KB Correct.
22 Correct 31 ms 30424 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 792 ms 57924 KB Correct.
2 Correct 113 ms 62452 KB Correct.
3 Incorrect 406 ms 64496 KB Wrong Answer.
4 Halted 0 ms 0 KB -