답안 #884164

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
884164	2023-12-06T16:31:41 Z	sjoonmin07	사이버랜드 (APIO23_cyberland)	C++17	100 / 100	180 ms	70288 KB

cyberland

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define all(v) v.begin(),v.end()
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;

using dii=tuple<double,int,int>;
double dist[101010][71],p[71];
int pr[101010];
vector<pair<int,double>> adj[101010];
priority_queue<dii,vector<dii>,greater<dii>> pq;

int find_(int n) {
    if(n==pr[n]) return n;
    return pr[n]=find_(pr[n]);
}
void uni(int x,int y) {
    pr[find_(x)]=find_(y);
}

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) {
    while(!pq.empty()) pq.pop();
    for(int i=0;i<N;i++) adj[i].clear();
    K=min(K,70);
    p[0]=1;
    for(int i=1;i<=K;i++) p[i]=p[i-1]*0.5;
    for(int i=0;i<N;i++) pr[i]=i;
    for(int i=0;i<M;i++) {
        if(x[i]!=H&&y[i]!=H) uni(x[i],y[i]);
        adj[x[i]].eb(make_pair(y[i],c[i])); adj[y[i]].eb(make_pair(x[i],c[i]));
    }
    for(int i=0;i<N;i++) for(int j=0;j<=K;j++) dist[i][j]=1e18;
    for(int i=0;i<=K;i++) dist[H][i]=0;
    arr[0]=0;
    pq.push(dii(0,H,0));
    while(!pq.empty()) {
        auto [d,cur,k]=pq.top(); pq.pop();
        if(d>dist[cur][k]) continue;
        if(arr[cur]==0) return d;
        for(auto [i,c]:adj[cur]) {
            if(find_(i)!=find_(0)) continue;
            if(dist[i][k]>d+c*p[k]) {
                dist[i][k]=d+c*p[k];
                pq.push(dii(dist[i][k],i,k));
            }
            if(arr[i]==2&&k+1<=K && dist[i][k+1]>d+c*p[k]) {
                dist[i][k+1]=d+c*p[k];
                pq.push(dii(dist[i][k+1],i,k+1));
            }
        }
    }
    return -1;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	4700 KB	Correct.
2	Correct	15 ms	4956 KB	Correct.

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	4700 KB	Correct.
2	Correct	17 ms	5724 KB	Correct.
3	Correct	16 ms	5724 KB	Correct.
4	Correct	21 ms	5772 KB	Correct.
5	Correct	17 ms	5724 KB	Correct.
6	Correct	14 ms	10584 KB	Correct.
7	Correct	19 ms	10844 KB	Correct.
8	Correct	10 ms	16992 KB	Correct.
9	Correct	17 ms	5540 KB	Correct.
10	Correct	17 ms	5464 KB	Correct.

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	4700 KB	Correct.
2	Correct	21 ms	5724 KB	Correct.
3	Correct	15 ms	5720 KB	Correct.
4	Correct	20 ms	5668 KB	Correct.
5	Correct	17 ms	5468 KB	Correct.
6	Correct	4 ms	9564 KB	Correct.

Subtask #4
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	42580 KB	Correct.
2	Correct	15 ms	4700 KB	Correct.
3	Correct	15 ms	5724 KB	Correct.
4	Correct	16 ms	5768 KB	Correct.
5	Correct	19 ms	5536 KB	Correct.

Subtask #5
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	4952 KB	Correct.
2	Correct	19 ms	5980 KB	Correct.
3	Correct	18 ms	5980 KB	Correct.
4	Correct	20 ms	11164 KB	Correct.
5	Correct	16 ms	5468 KB	Correct.

Subtask #6
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	4956 KB	Correct.
2	Correct	15 ms	5724 KB	Correct.
3	Correct	48 ms	54360 KB	Correct.
4	Correct	13 ms	10332 KB	Correct.
5	Correct	17 ms	5468 KB	Correct.
6	Correct	16 ms	5980 KB	Correct.

Subtask #7
29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	4956 KB	Correct.
2	Correct	3 ms	4956 KB	Correct.
3	Correct	49 ms	66132 KB	Correct.
4	Correct	38 ms	21464 KB	Correct.
5	Correct	42 ms	31292 KB	Correct.
6	Correct	26 ms	18012 KB	Correct.
7	Correct	35 ms	21332 KB	Correct.
8	Correct	38 ms	9056 KB	Correct.
9	Correct	18 ms	5980 KB	Correct.
10	Correct	16 ms	5984 KB	Correct.
11	Correct	35 ms	6884 KB	Correct.
12	Correct	17 ms	5980 KB	Correct.
13	Correct	17 ms	5980 KB	Correct.
14	Correct	40 ms	35060 KB	Correct.
15	Correct	34 ms	13940 KB	Correct.
16	Correct	18 ms	5976 KB	Correct.
17	Correct	18 ms	6232 KB	Correct.
18	Correct	18 ms	5980 KB	Correct.
19	Correct	33 ms	6828 KB	Correct.
20	Correct	3 ms	4952 KB	Correct.
21	Correct	2 ms	4700 KB	Correct.
22	Correct	3 ms	5468 KB	Correct.

Subtask #8
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	4952 KB	Correct.
2	Correct	4 ms	4956 KB	Correct.
3	Correct	68 ms	70288 KB	Correct.
4	Correct	42 ms	9552 KB	Correct.
5	Correct	39 ms	31348 KB	Correct.
6	Correct	28 ms	18056 KB	Correct.
7	Correct	39 ms	29008 KB	Correct.
8	Correct	37 ms	6832 KB	Correct.
9	Correct	19 ms	5980 KB	Correct.
10	Correct	18 ms	5980 KB	Correct.
11	Correct	180 ms	5960 KB	Correct.
12	Correct	19 ms	5976 KB	Correct.
13	Correct	19 ms	5980 KB	Correct.
14	Correct	41 ms	32576 KB	Correct.
15	Correct	50 ms	37588 KB	Correct.
16	Correct	34 ms	18952 KB	Correct.
17	Correct	33 ms	9044 KB	Correct.
18	Correct	19 ms	5980 KB	Correct.
19	Correct	20 ms	5972 KB	Correct.
20	Correct	20 ms	5980 KB	Correct.
21	Correct	41 ms	6820 KB	Correct.
22	Correct	3 ms	4736 KB	Correct.
23	Correct	2 ms	4696 KB	Correct.
24	Correct	3 ms	5468 KB	Correct.

답안 #884164

Compilation message