oj.uz

Submission #837904

# Submission time Handle Problem Language Result Execution time Memory
837904 2023-08-25T19:51:15 Z beaconmc Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 80872 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include "cyberland.h"

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

typedef double ll;

using namespace std;
//using namespace __gnu_pbds;

#define FOR(i, x, y) for(int i=x; i<y; i++)
#define FORNEG(i, x, y) for(int i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
#define mp make_pair
#define fir first
#define sec second


vector<pair<long long,ll>> edges[100001];
ll dists[100001][71];



double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    FOR(i,0,N+1) FOR(j,0,71) dists[i][j] = 1000000000000000;
    FOR(i,0,N+1) edges[i].clear();
    FOR(i,0,M){
        edges[x[i]].push_back(mp(y[i], c[i]));
        edges[y[i]].push_back(mp(x[i], c[i]));
    }


    priority_queue<vector<ll>, vector<vector<ll>>, greater<vector<ll>>> p;

    FOR(i,0,N){
        if (i==0){
            dists[i][0] =  0;
            p.push({0, (ll) i, 0});
        }
    }


    while (p.size()){
        ll dist = p.top()[0];
        long long node = (long long) p.top()[1];
        long long times = (long long) p.top()[2];
        p.pop();
        if (node==H) continue;

        if (dists[node][times] < dist) continue;

        

        for (auto&i : edges[node]){
            if (arr[i.fir]==0){
                if (dists[i.fir][times] > 0){
                    dists[i.fir][times] = 0;
                    p.push({dists[i.fir][times],(ll) i.fir, (ll) times});
                }
                continue;
            }

            if (dists[i.fir][times] > dists[node][times] + i.sec){
                dists[i.fir][times] = dists[node][times] + i.sec;
                p.push({dists[i.fir][times],(ll) i.fir, (ll) times});
            }
            if (arr[i.fir] == 2){
                if (times == K || times == 70) continue;
                ll newdist = (dists[node][times] + i.sec)/2;

                if (dists[i.fir][times+1] > newdist){
                    dists[i.fir][times+1] = newdist;
                    p.push({dists[i.fir][times+1],(ll) i.fir, (ll) times+1});
                }
            }

        }
    }
    ll ans = 1000000000000000;

    FOR(i,0,min(K+1, 70)){
        ans = min(ans, dists[H][i]);
    }
    if (ans==1000000000000000) return -1;

    return ans;





}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3028 KB Correct.
2 Correct 21 ms 3028 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4180 KB Correct.
2 Correct 27 ms 4400 KB Correct.
3 Correct 24 ms 4308 KB Correct.
4 Correct 25 ms 4308 KB Correct.
5 Correct 27 ms 4436 KB Correct.
6 Correct 25 ms 9940 KB Correct.
7 Correct 31 ms 10100 KB Correct.
8 Correct 18 ms 15700 KB Correct.
9 Correct 23 ms 3668 KB Correct.
10 Correct 22 ms 3644 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 4308 KB Correct.
2 Correct 27 ms 4304 KB Correct.
3 Correct 26 ms 4300 KB Correct.
4 Correct 25 ms 3660 KB Correct.
5 Correct 26 ms 3660 KB Correct.
6 Correct 8 ms 8020 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 41008 KB Correct.
2 Correct 787 ms 4404 KB Correct.
3 Correct 676 ms 4260 KB Correct.
4 Correct 716 ms 4300 KB Correct.
5 Correct 474 ms 3700 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 4308 KB Correct.
2 Correct 25 ms 4564 KB Correct.
3 Correct 22 ms 4436 KB Correct.
4 Correct 27 ms 10420 KB Correct.
5 Correct 19 ms 3540 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4448 KB Correct.
2 Correct 22 ms 4308 KB Correct.
3 Correct 50 ms 53028 KB Correct.
4 Correct 19 ms 8148 KB Correct.
5 Correct 22 ms 3668 KB Correct.
6 Correct 24 ms 4436 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 5320 KB Correct.
2 Correct 48 ms 5368 KB Correct.
3 Correct 2160 ms 68312 KB Correct.
4 Correct 1664 ms 19508 KB Correct.
5 Correct 1824 ms 80872 KB Correct.
6 Correct 712 ms 43068 KB Correct.
7 Correct 1686 ms 20748 KB Correct.
8 Correct 1546 ms 7292 KB Correct.
9 Correct 359 ms 5284 KB Correct.
10 Correct 394 ms 5748 KB Correct.
11 Correct 1435 ms 5780 KB Correct.
12 Correct 407 ms 5472 KB Correct.
13 Correct 382 ms 5300 KB Correct.
14 Correct 1459 ms 36276 KB Correct.
15 Correct 1911 ms 13368 KB Correct.
16 Correct 368 ms 5444 KB Correct.
17 Correct 460 ms 5512 KB Correct.
18 Correct 476 ms 5380 KB Correct.
19 Correct 1414 ms 7072 KB Correct.
20 Correct 29 ms 2900 KB Correct.
21 Correct 34 ms 4164 KB Correct.
22 Correct 38 ms 6664 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1350 ms 7736 KB Correct.
2 Correct 137 ms 7092 KB Correct.
3 Correct 999 ms 68628 KB Correct.
4 Execution timed out 3047 ms 10680 KB Time limit exceeded
5 Halted 0 ms 0 KB -