oj.uz

Submission #884164

# Submission time Handle Problem Language Result Execution time Memory
884164 2023-12-06T16:31:41 Z sjoonmin07 Cyberland (APIO23_cyberland) C++17
100 / 100
 180 ms 70288 KB 
#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

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4700 KB Correct.
2 Correct 15 ms 4956 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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.