oj.uz

Submission #957570

# Submission time Handle Problem Language Result Execution time Memory
957570 2024-04-04T04:10:24 Z zeta7532 Cyberland (APIO23_cyberland) C++17
100 / 100
 2487 ms 15156 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = int;
using P = pair<double,int>;
const ll mod = 998244353;
#define fi first
#define se second
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define faster ios::sync_with_stdio(false);cin.tie(nullptr)

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) {
    vector<double> dis(N,1e15);
    double ans=1e15;
    dis[0]=0;
    vector<vector<pair<int,int>>> G(N);
    rep(i,M){
        G[x[i]].push_back({y[i],i});
        G[y[i]].push_back({x[i],i});
    }
    rep(loop,100){
        priority_queue<P,vector<P>,greater<P>> pq;
        rep(i,N) pq.emplace(dis[i],i);
        while(!pq.empty()){
            P p=pq.top();
            pq.pop();
            int v=p.se;
            if(p.fi>dis[v]) continue;
            if(p.fi==1e15) continue;
            if(v==H) continue;
            for(auto &e:G[v]){
                double cost=dis[v]+c[e.se];
                if(arr[e.fi]==0) cost=0;
                if(dis[e.fi]>cost){
                    dis[e.fi]=cost;
                    pq.emplace(dis[e.fi],e.fi);
                }
            }
        }
        ans=min(ans,dis[H]);
        dis[H]=1e15;
        vector<double> next_dis(N,1e15);
        if(loop<K) rep(i,M){
            if(arr[x[i]]==2) if(dis[y[i]]<1e15) next_dis[x[i]]=min(next_dis[x[i]],(dis[y[i]]+c[i])/2);
            if(arr[y[i]]==2) if(dis[x[i]]<1e15) next_dis[y[i]]=min(next_dis[y[i]],(dis[x[i]]+c[i])/2);
        }
        rep(i,N){
            dis[i]=min(dis[i],next_dis[i]);
        }
        ans=min(ans,dis[H]);
        dis[H]=1e15;
    }
    if(ans==1e15) return -1;
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 848 KB Correct.
2 Correct 102 ms 852 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 1364 KB Correct.
2 Correct 338 ms 1368 KB Correct.
3 Correct 321 ms 1372 KB Correct.
4 Correct 359 ms 1652 KB Correct.
5 Correct 334 ms 1328 KB Correct.
6 Correct 545 ms 2772 KB Correct.
7 Correct 717 ms 2592 KB Correct.
8 Correct 314 ms 3652 KB Correct.
9 Correct 145 ms 1104 KB Correct.
10 Correct 153 ms 1196 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 1180 KB Correct.
2 Correct 340 ms 1536 KB Correct.
3 Correct 307 ms 1388 KB Correct.
4 Correct 167 ms 1148 KB Correct.
5 Correct 176 ms 1272 KB Correct.
6 Correct 109 ms 1628 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 669 ms 9120 KB Correct.
2 Correct 315 ms 1372 KB Correct.
3 Correct 287 ms 1340 KB Correct.
4 Correct 283 ms 1360 KB Correct.
5 Correct 160 ms 1292 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 1640 KB Correct.
2 Correct 277 ms 1364 KB Correct.
3 Correct 285 ms 1476 KB Correct.
4 Correct 423 ms 2012 KB Correct.
5 Correct 149 ms 1104 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 1360 KB Correct.
2 Correct 250 ms 1616 KB Correct.
3 Correct 662 ms 12548 KB Correct.
4 Correct 360 ms 1960 KB Correct.
5 Correct 160 ms 1104 KB Correct.
6 Correct 271 ms 1224 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 1272 KB Correct.
2 Correct 40 ms 760 KB Correct.
3 Correct 2487 ms 15136 KB Correct.
4 Correct 1610 ms 4756 KB Correct.
5 Correct 780 ms 8900 KB Correct.
6 Correct 290 ms 6108 KB Correct.
7 Correct 1470 ms 4420 KB Correct.
8 Correct 875 ms 1944 KB Correct.
9 Correct 267 ms 1416 KB Correct.
10 Correct 278 ms 1208 KB Correct.
11 Correct 592 ms 2192 KB Correct.
12 Correct 322 ms 1252 KB Correct.
13 Correct 274 ms 1640 KB Correct.
14 Correct 1582 ms 7792 KB Correct.
15 Correct 1265 ms 3432 KB Correct.
16 Correct 275 ms 1244 KB Correct.
17 Correct 330 ms 1396 KB Correct.
18 Correct 306 ms 1380 KB Correct.
19 Correct 981 ms 1632 KB Correct.
20 Correct 15 ms 344 KB Correct.
21 Correct 32 ms 608 KB Correct.
22 Correct 23 ms 1116 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 1300 KB Correct.
2 Correct 42 ms 604 KB Correct.
3 Correct 1478 ms 15156 KB Correct.
4 Correct 1269 ms 2584 KB Correct.
5 Correct 845 ms 8808 KB Correct.
6 Correct 336 ms 6204 KB Correct.
7 Correct 1481 ms 7328 KB Correct.
8 Correct 612 ms 2096 KB Correct.
9 Correct 296 ms 1356 KB Correct.
10 Correct 297 ms 1524 KB Correct.
11 Correct 350 ms 1304 KB Correct.
12 Correct 361 ms 1616 KB Correct.
13 Correct 303 ms 1188 KB Correct.
14 Correct 1218 ms 8324 KB Correct.
15 Correct 1929 ms 8508 KB Correct.
16 Correct 1516 ms 4052 KB Correct.
17 Correct 928 ms 2200 KB Correct.
18 Correct 291 ms 1412 KB Correct.
19 Correct 344 ms 1264 KB Correct.
20 Correct 323 ms 1580 KB Correct.
21 Correct 1024 ms 1840 KB Correct.
22 Correct 16 ms 600 KB Correct.
23 Correct 30 ms 604 KB Correct.
24 Correct 26 ms 1116 KB Correct.