oj.uz

Submission #985086

# Submission time Handle Problem Language Result Execution time Memory
985086 2024-05-17T10:32:25 Z shjeong Cyberland (APIO23_cyberland) C++17
97 / 100
 2149 ms 71656 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][33];
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) {
    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[33];
    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 27 ms 8648 KB Correct.
2 Correct 27 ms 8796 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 9052 KB Correct.
2 Correct 34 ms 9640 KB Correct.
3 Correct 31 ms 9092 KB Correct.
4 Correct 32 ms 9116 KB Correct.
5 Correct 32 ms 9300 KB Correct.
6 Correct 30 ms 16060 KB Correct.
7 Correct 40 ms 16708 KB Correct.
8 Correct 20 ms 20816 KB Correct.
9 Correct 29 ms 9048 KB Correct.
10 Correct 29 ms 9048 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 10404 KB Correct.
2 Correct 229 ms 10052 KB Correct.
3 Correct 206 ms 9628 KB Correct.
4 Correct 142 ms 9556 KB Correct.
5 Correct 140 ms 9028 KB Correct.
6 Correct 61 ms 18904 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 55428 KB Correct.
2 Correct 159 ms 10524 KB Correct.
3 Correct 132 ms 10352 KB Correct.
4 Correct 142 ms 10380 KB Correct.
5 Correct 92 ms 9440 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 9048 KB Correct.
2 Correct 29 ms 9308 KB Correct.
3 Correct 28 ms 9308 KB Correct.
4 Correct 29 ms 16644 KB Correct.
5 Correct 25 ms 8796 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 10028 KB Correct.
2 Correct 103 ms 9776 KB Correct.
3 Correct 57 ms 55388 KB Correct.
4 Correct 99 ms 17684 KB Correct.
5 Correct 94 ms 9124 KB Correct.
6 Correct 116 ms 9792 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 10096 KB Correct.
2 Correct 26 ms 11868 KB Correct.
3 Correct 861 ms 71484 KB Correct.
4 Correct 397 ms 26312 KB Correct.
5 Correct 718 ms 71656 KB Correct.
6 Correct 276 ms 39980 KB Correct.
7 Correct 384 ms 25224 KB Correct.
8 Correct 295 ms 13140 KB Correct.
9 Correct 141 ms 10492 KB Correct.
10 Correct 140 ms 10068 KB Correct.
11 Correct 254 ms 10536 KB Correct.
12 Correct 164 ms 10452 KB Correct.
13 Correct 151 ms 10384 KB Correct.
14 Correct 404 ms 40832 KB Correct.
15 Correct 318 ms 18460 KB Correct.
16 Correct 157 ms 10312 KB Correct.
17 Correct 181 ms 10400 KB Correct.
18 Correct 162 ms 10376 KB Correct.
19 Correct 481 ms 11528 KB Correct.
20 Correct 11 ms 8540 KB Correct.
21 Correct 13 ms 8940 KB Correct.
22 Correct 22 ms 10916 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 2149 ms 41408 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -