oj.uz

Submission #985091

# Submission time Handle Problem Language Result Execution time Memory
985091 2024-05-17T10:33:33 Z shjeong Cyberland (APIO23_cyberland) C++17
97 / 100
 832 ms 168780 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[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 29 ms 8028 KB Correct.
2 Correct 26 ms 8024 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 10180 KB Correct.
2 Correct 31 ms 10184 KB Correct.
3 Correct 31 ms 10072 KB Correct.
4 Correct 31 ms 10076 KB Correct.
5 Correct 36 ms 10204 KB Correct.
6 Correct 35 ms 25428 KB Correct.
7 Correct 45 ms 25376 KB Correct.
8 Correct 22 ms 40540 KB Correct.
9 Correct 28 ms 8024 KB Correct.
10 Correct 28 ms 8028 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 11148 KB Correct.
2 Correct 229 ms 11120 KB Correct.
3 Correct 229 ms 11112 KB Correct.
4 Correct 139 ms 8024 KB Correct.
5 Correct 140 ms 8144 KB Correct.
6 Correct 64 ms 26560 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 116364 KB Correct.
2 Correct 151 ms 11052 KB Correct.
3 Correct 130 ms 10916 KB Correct.
4 Correct 155 ms 11068 KB Correct.
5 Correct 92 ms 8024 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 10328 KB Correct.
2 Correct 29 ms 10072 KB Correct.
3 Correct 28 ms 10072 KB Correct.
4 Correct 36 ms 25596 KB Correct.
5 Correct 27 ms 8280 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 10792 KB Correct.
2 Correct 97 ms 10836 KB Correct.
3 Correct 71 ms 133612 KB Correct.
4 Correct 123 ms 23120 KB Correct.
5 Correct 86 ms 8028 KB Correct.
6 Correct 115 ms 10856 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 11036 KB Correct.
2 Correct 31 ms 11096 KB Correct.
3 Correct 832 ms 168780 KB Correct.
4 Correct 394 ms 46348 KB Correct.
5 Correct 726 ms 106612 KB Correct.
6 Correct 268 ms 48300 KB Correct.
7 Correct 372 ms 48332 KB Correct.
8 Correct 277 ms 15000 KB Correct.
9 Correct 152 ms 11028 KB Correct.
10 Correct 135 ms 10868 KB Correct.
11 Correct 246 ms 10516 KB Correct.
12 Correct 150 ms 11128 KB Correct.
13 Correct 147 ms 11160 KB Correct.
14 Correct 407 ms 87652 KB Correct.
15 Correct 321 ms 30484 KB Correct.
16 Correct 142 ms 11112 KB Correct.
17 Correct 178 ms 11352 KB Correct.
18 Correct 161 ms 11076 KB Correct.
19 Correct 495 ms 11420 KB Correct.
20 Correct 10 ms 8024 KB Correct.
21 Correct 13 ms 10620 KB Correct.
22 Correct 22 ms 12380 KB Correct.

Subtask #8
0.0 / 3.0

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