oj.uz

Submission #753474

# Submission time Handle Problem Language Result Execution time Memory
753474 2023-06-05T09:40:26 Z quanlt206 Cyberland (APIO23_cyberland) C++17
97 / 100
 2163 ms 126928 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
#define all(x) begin(x), end(x)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define FORD(i, b, a) for(int i = (b); i >= (a); i--)
#define REP(i, a, b) for (int i = (a); i < (b); i++)
#define mxx max_element
#define mnn min_element
#define SQR(x) (1LL * (x) * (x))
#define MASK(i) (1LL << (i))
#define Point Vector
#define left Left
#define right Right
#define div Div


using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<db, db> pdb;
typedef pair<ld, ld> pld;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
typedef pair<ll, int> pli;
typedef pair<ll, pii> plii;

template<class A, class B>
    bool maximize(A& x, B y) {
        if (x < y) return x = y, true; else return false;
    }
template<class A, class B>
    bool minimize(A& x, B y) {
        if (x > y) return x = y, true; else return false;
    }
/* END OF TEMPLATE */

const int N = 1e5 + 7;

vector<pii> v[N];

double d[N][150];

bool p[N];

int a[N];

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) {
    REP(i, 0, n) v[i].clear();
    REP(i, 0, n) a[i] = arr[i];
    REP(i, 0, m) {
        v[x[i]].push_back({y[i], c[i]});
        v[y[i]].push_back({x[i], c[i]});
//        cout<<x[i]<<" "<<y[i]<<" "<<c[i]<<"\n";
    }
    #define pdii pair<ld, pii>
    priority_queue<pdii, vector<pdii>, greater<pdii>> pq;
    FOR(i, 0, n) p[i] = true;
    p[0] = false;
    queue<int> qu;
    qu.push(0);
    while (!qu.empty()) {
        int x = qu.front();
        qu.pop();
        for (auto y : v[x])
            if (p[y.X] && y.X != H) {
                p[y.X] = false;
                qu.push(y.X);
            }
    }
    k = min(k, 60);
    FOR(i, 0, n)
        FOR(j, 0, k) d[i][j] = 1e15;
    d[0][0] = 0;
    pq.push({0, {0, 0}});
    REP(i, 0, n)
        if (a[i] == 0 && !p[i]) {
            pq.push({0, {i, 0}});
            d[i][0] = 0;
        }
    while (!pq.empty()) {
        pdii tmp = pq.top();
        pq.pop();
        double w = tmp.X;
        int x = tmp.Y.X, t = tmp.Y.Y;
        if (w > d[x][t]) continue;
//        cout<<x<<" "<<t<<" "<<w<<"\n";
        for (auto y : v[x]) {
            double new_w = w + y.Y;
            if (minimize(d[y.X][t], new_w) && y.X != H) pq.push({d[y.X][t], {y.X, t}});
            if (t + 1 <= k && a[y.X] == 2 && minimize(d[y.X][t + 1], new_w / 2.0) && y.X != H)
                pq.push({d[y.X][t + 1], {y.X, t + 1}});
        }
    }
    double res = 1e18;
    FOR(j, 0, k) minimize(res, d[H][j]);
    if (res > 1e14) return -1;
    return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2772 KB Correct.
2 Correct 30 ms 2796 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3924 KB Correct.
2 Correct 29 ms 3924 KB Correct.
3 Correct 30 ms 3968 KB Correct.
4 Correct 30 ms 3968 KB Correct.
5 Correct 31 ms 3924 KB Correct.
6 Correct 36 ms 14984 KB Correct.
7 Correct 44 ms 14712 KB Correct.
8 Correct 30 ms 27212 KB Correct.
9 Correct 29 ms 2848 KB Correct.
10 Correct 29 ms 2840 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3988 KB Correct.
2 Correct 35 ms 3932 KB Correct.
3 Correct 34 ms 4052 KB Correct.
4 Correct 32 ms 2848 KB Correct.
5 Correct 69 ms 2836 KB Correct.
6 Correct 22 ms 13012 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 83284 KB Correct.
2 Correct 494 ms 4828 KB Correct.
3 Correct 409 ms 4820 KB Correct.
4 Correct 497 ms 4792 KB Correct.
5 Correct 355 ms 2996 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4068 KB Correct.
2 Correct 26 ms 3924 KB Correct.
3 Correct 28 ms 3940 KB Correct.
4 Correct 35 ms 14928 KB Correct.
5 Correct 26 ms 2856 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4016 KB Correct.
2 Correct 28 ms 4048 KB Correct.
3 Correct 78 ms 96944 KB Correct.
4 Correct 22 ms 11636 KB Correct.
5 Correct 31 ms 2936 KB Correct.
6 Correct 37 ms 4052 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 542 ms 5916 KB Correct.
2 Correct 66 ms 8276 KB Correct.
3 Correct 1143 ms 125212 KB Correct.
4 Correct 911 ms 31160 KB Correct.
5 Correct 2163 ms 115000 KB Correct.
6 Correct 1031 ms 84452 KB Correct.
7 Correct 945 ms 33712 KB Correct.
8 Correct 933 ms 7504 KB Correct.
9 Correct 499 ms 6948 KB Correct.
10 Correct 457 ms 5896 KB Correct.
11 Correct 857 ms 4652 KB Correct.
12 Correct 432 ms 6004 KB Correct.
13 Correct 537 ms 5936 KB Correct.
14 Correct 808 ms 63512 KB Correct.
15 Correct 921 ms 19716 KB Correct.
16 Correct 453 ms 5792 KB Correct.
17 Correct 591 ms 5752 KB Correct.
18 Correct 595 ms 5696 KB Correct.
19 Correct 1345 ms 5664 KB Correct.
20 Correct 34 ms 3528 KB Correct.
21 Correct 44 ms 4796 KB Correct.
22 Correct 60 ms 8416 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1492 ms 10292 KB Correct.
2 Correct 198 ms 17204 KB Correct.
3 Incorrect 1042 ms 126928 KB Wrong Answer.
4 Halted 0 ms 0 KB -