oj.uz

Submission #985097

# Submission time Handle Problem Language Result Execution time Memory
985097 2024-05-17T10:35:35 Z shjeong Cyberland (APIO23_cyberland) C++17
100 / 100
 2414 ms 185376 KB 
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define MOD2 998244353
#define debug(x) cout << #x<<" is "<<x<<"\n";
#define X first
#define Y second
#define DEB cout<<"[DEBUG]"
#define PAIR(a,b) "("<<a<<", "<<b<<")"
#define PRINT1(V) DEB<<#V<<endl; for(auto i : V)DEB<<i<<"\n"
#define PRINT2(V) DEB<<#V<<endl; for(auto [a,b] : V)DEB<<PAIR(a,b)<<"\n";
typedef long long ll;
typedef __int128_t lll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
typedef pair<ld,ll> Pd;
vector<P> adj[202020];
ld dist[202020][101];
ll p[202020];
ll find(ll x){
    if(p[x]<0)return x;
    return p[x] = find(p[x]);
}
void merge(ll x, ll y){
    x = find(x), y = find(y);
    if(x==y)return;
    p[y]=x;
}
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<ll>(K,99);
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j <= K ; j++)dist[i][j] = 1e15;
        adj[i].clear();
        p[i]=-1;
    }
    for(int i = 0 ; i < M ; i++){
        if(x[i] != H and y[i] != H)merge(x[i],y[i]);
        adj[x[i]].push_back({y[i],c[i]});
        adj[y[i]].push_back({x[i],c[i]});
    }
    priority_queue<Pd,vector<Pd>,greater<Pd>> pq[101];
    for(int i = 0 ; i < N ; i++)if(arr[i]==0 and find(0) == find(i)){
        for(int j = 0 ; j <= K ; j++)dist[i][j]=0, pq[j].push({0,i});
    }
    ld ret = 1e15;
    pq[0].push({0,0});
    dist[0][0] = 0;
    for(int i = 0 ; i <= K ; i++){
        while(pq[i].size()){
            auto [d,cur] = pq[i].top(); pq[i].pop();
            if(cur==H or dist[cur][i] < d)continue;
            for(auto [next,w] : adj[cur]){
                if(dist[next][i] > d+w){
                    dist[next][i] = d+w;
                    pq[i].push({d+w,next});
                }
                if(arr[next]==2 and i<K and dist[next][i+1] > (d+w)/2.0){
                    dist[next][i+1] = (d+w)/2.0;
                    pq[i+1].push({(d+w)/2.0,next});
                }
            }
        }
        ret = min(ret, dist[H][i]);
    }
    if(ret==1e15)return -1;
    return (double)ret;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 8072 KB Correct.
2 Correct 29 ms 8028 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 10076 KB Correct.
2 Correct 44 ms 10212 KB Correct.
3 Correct 34 ms 10188 KB Correct.
4 Correct 37 ms 10208 KB Correct.
5 Correct 36 ms 10208 KB Correct.
6 Correct 31 ms 25436 KB Correct.
7 Correct 39 ms 25432 KB Correct.
8 Correct 21 ms 40536 KB Correct.
9 Correct 29 ms 8028 KB Correct.
10 Correct 41 ms 8272 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 11040 KB Correct.
2 Correct 243 ms 11036 KB Correct.
3 Correct 216 ms 11096 KB Correct.
4 Correct 148 ms 8104 KB Correct.
5 Correct 150 ms 8140 KB Correct.
6 Correct 72 ms 26524 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 116448 KB Correct.
2 Correct 154 ms 11068 KB Correct.
3 Correct 145 ms 10988 KB Correct.
4 Correct 150 ms 11028 KB Correct.
5 Correct 93 ms 8164 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 10072 KB Correct.
2 Correct 41 ms 10300 KB Correct.
3 Correct 28 ms 10292 KB Correct.
4 Correct 34 ms 25692 KB Correct.
5 Correct 36 ms 8028 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 10832 KB Correct.
2 Correct 98 ms 10836 KB Correct.
3 Correct 61 ms 133548 KB Correct.
4 Correct 105 ms 23052 KB Correct.
5 Correct 88 ms 8024 KB Correct.
6 Correct 129 ms 10808 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 11156 KB Correct.
2 Correct 27 ms 11240 KB Correct.
3 Correct 898 ms 169056 KB Correct.
4 Correct 381 ms 46368 KB Correct.
5 Correct 693 ms 106612 KB Correct.
6 Correct 305 ms 48404 KB Correct.
7 Correct 422 ms 48160 KB Correct.
8 Correct 328 ms 15024 KB Correct.
9 Correct 149 ms 11088 KB Correct.
10 Correct 137 ms 10840 KB Correct.
11 Correct 276 ms 10940 KB Correct.
12 Correct 217 ms 11072 KB Correct.
13 Correct 147 ms 11024 KB Correct.
14 Correct 529 ms 87600 KB Correct.
15 Correct 326 ms 30212 KB Correct.
16 Correct 145 ms 11108 KB Correct.
17 Correct 168 ms 11080 KB Correct.
18 Correct 172 ms 11040 KB Correct.
19 Correct 467 ms 11168 KB Correct.
20 Correct 10 ms 8028 KB Correct.
21 Correct 13 ms 10524 KB Correct.
22 Correct 23 ms 12380 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 13560 KB Correct.
2 Correct 104 ms 13424 KB Correct.
3 Correct 1489 ms 175976 KB Correct.
4 Correct 477 ms 22056 KB Correct.
5 Correct 2239 ms 185376 KB Correct.
6 Correct 838 ms 91048 KB Correct.
7 Correct 958 ms 70776 KB Correct.
8 Correct 442 ms 13072 KB Correct.
9 Correct 368 ms 13624 KB Correct.
10 Correct 367 ms 13064 KB Correct.
11 Correct 248 ms 9300 KB Correct.
12 Correct 426 ms 13908 KB Correct.
13 Correct 415 ms 13756 KB Correct.
14 Correct 2414 ms 120172 KB Correct.
15 Correct 2200 ms 101248 KB Correct.
16 Correct 654 ms 43736 KB Correct.
17 Correct 468 ms 17848 KB Correct.
18 Correct 409 ms 13860 KB Correct.
19 Correct 513 ms 14048 KB Correct.
20 Correct 440 ms 13492 KB Correct.
21 Correct 1397 ms 15296 KB Correct.
22 Correct 29 ms 8276 KB Correct.
23 Correct 30 ms 11776 KB Correct.
24 Correct 60 ms 16720 KB Correct.