oj.uz

답안 #1008231

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1008231 2024-06-26T08:32:38 Z imarn 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 3000 ms 94892 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,int>>g[mxn];
double d[67][mxn]{0};
int pr[mxn]{0};
int get(int r){
    return pr[r]==r?r:pr[r]=get(pr[r]);
}
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){
    iota(pr,pr+N,0);
    K=min(K,66);for(int i=0;i<M;i++){
        g[x[i]].pb({y[i],i}),g[y[i]].pb({x[i],i});
        if(x[i]==H||y[i]==H)continue;
        pr[get(x[i])]=get(y[i]);
    }
    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&&get(i)==get(0))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+c[v.s])d[u.s.f][v.f]=u.f+c[v.s],q.push({u.f+c[v.s],{u.s.f,v.f}});
            if(arr[v.f]==2&&u.s.f<K){
                double t = (u.f+c[v.s])/2.0;
                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();
    return (ans>=1e17?-1:ans);
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 6488 KB Correct.
2 Correct 11 ms 6488 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 6744 KB Correct.
2 Correct 18 ms 6748 KB Correct.
3 Correct 23 ms 4700 KB Correct.
4 Correct 23 ms 4700 KB Correct.
5 Correct 18 ms 6748 KB Correct.
6 Correct 17 ms 9048 KB Correct.
7 Correct 21 ms 9052 KB Correct.
8 Correct 11 ms 12172 KB Correct.
9 Correct 16 ms 6236 KB Correct.
10 Correct 17 ms 6236 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 6492 KB Correct.
2 Correct 17 ms 6748 KB Correct.
3 Correct 16 ms 6628 KB Correct.
4 Correct 17 ms 4188 KB Correct.
5 Correct 17 ms 6232 KB Correct.
6 Correct 6 ms 6876 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 25676 KB Correct.
2 Correct 199 ms 6864 KB Correct.
3 Correct 139 ms 6744 KB Correct.
4 Correct 142 ms 6748 KB Correct.
5 Correct 137 ms 4184 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 4696 KB Correct.
2 Correct 32 ms 4700 KB Correct.
3 Correct 17 ms 3160 KB Correct.
4 Correct 18 ms 5980 KB Correct.
5 Correct 14 ms 2904 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 3420 KB Correct.
2 Correct 18 ms 3344 KB Correct.
3 Correct 38 ms 26716 KB Correct.
4 Correct 13 ms 5256 KB Correct.
5 Correct 20 ms 2908 KB Correct.
6 Correct 21 ms 3416 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 179 ms 3520 KB Correct.
2 Correct 26 ms 4052 KB Correct.
3 Correct 664 ms 26596 KB Correct.
4 Correct 446 ms 11980 KB Correct.
5 Correct 772 ms 51824 KB Correct.
6 Correct 316 ms 27300 KB Correct.
7 Correct 417 ms 11820 KB Correct.
8 Correct 436 ms 5560 KB Correct.
9 Correct 163 ms 7112 KB Correct.
10 Correct 159 ms 5064 KB Correct.
11 Correct 411 ms 4896 KB Correct.
12 Correct 169 ms 7124 KB Correct.
13 Correct 182 ms 5080 KB Correct.
14 Correct 384 ms 14544 KB Correct.
15 Correct 423 ms 9176 KB Correct.
16 Correct 163 ms 7120 KB Correct.
17 Correct 200 ms 5080 KB Correct.
18 Correct 198 ms 7116 KB Correct.
19 Correct 412 ms 6972 KB Correct.
20 Correct 14 ms 6492 KB Correct.
21 Correct 17 ms 4824 KB Correct.
22 Correct 27 ms 9168 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 580 ms 8132 KB Correct.
2 Correct 80 ms 7624 KB Correct.
3 Correct 421 ms 61776 KB Correct.
4 Correct 940 ms 10180 KB Correct.
5 Correct 2383 ms 93048 KB Correct.
6 Correct 1152 ms 79436 KB Correct.
7 Correct 1053 ms 25380 KB Correct.
8 Correct 1065 ms 7880 KB Correct.
9 Correct 546 ms 7108 KB Correct.
10 Correct 550 ms 9332 KB Correct.
11 Correct 1808 ms 4692 KB Correct.
12 Correct 551 ms 9124 KB Correct.
13 Correct 608 ms 7048 KB Correct.
14 Execution timed out 3043 ms 94892 KB Time limit exceeded
15 Halted 0 ms 0 KB -