oj.uz

Submission #753471

# Submission time Handle Problem Language Result Execution time Memory
753471 2023-06-05T09:39:05 Z quanlt206 Cyberland (APIO23_cyberland) C++17
97 / 100
 1868 ms 126856 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, 50);
    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 21 ms 2796 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3972 KB Correct.
2 Correct 29 ms 3904 KB Correct.
3 Correct 27 ms 3964 KB Correct.
4 Correct 29 ms 3988 KB Correct.
5 Correct 29 ms 3924 KB Correct.
6 Correct 34 ms 14976 KB Correct.
7 Correct 55 ms 14780 KB Correct.
8 Correct 27 ms 27248 KB Correct.
9 Correct 28 ms 2856 KB Correct.
10 Correct 26 ms 2984 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3992 KB Correct.
2 Correct 28 ms 3924 KB Correct.
3 Correct 31 ms 4068 KB Correct.
4 Correct 30 ms 2900 KB Correct.
5 Correct 27 ms 2772 KB Correct.
6 Correct 11 ms 13024 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 83344 KB Correct.
2 Correct 452 ms 4780 KB Correct.
3 Correct 394 ms 4800 KB Correct.
4 Correct 429 ms 4704 KB Correct.
5 Correct 326 ms 2980 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4040 KB Correct.
2 Correct 25 ms 4040 KB Correct.
3 Correct 30 ms 3988 KB Correct.
4 Correct 34 ms 14980 KB Correct.
5 Correct 21 ms 2840 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3984 KB Correct.
2 Correct 23 ms 4052 KB Correct.
3 Correct 76 ms 96944 KB Correct.
4 Correct 30 ms 11628 KB Correct.
5 Correct 28 ms 2844 KB Correct.
6 Correct 24 ms 4076 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 5828 KB Correct.
2 Correct 70 ms 8236 KB Correct.
3 Correct 1047 ms 125284 KB Correct.
4 Correct 842 ms 31172 KB Correct.
5 Correct 1868 ms 115212 KB Correct.
6 Correct 811 ms 84508 KB Correct.
7 Correct 775 ms 33808 KB Correct.
8 Correct 766 ms 7544 KB Correct.
9 Correct 405 ms 6964 KB Correct.
10 Correct 394 ms 5928 KB Correct.
11 Correct 735 ms 4712 KB Correct.
12 Correct 425 ms 5948 KB Correct.
13 Correct 436 ms 5932 KB Correct.
14 Correct 707 ms 63704 KB Correct.
15 Correct 821 ms 19772 KB Correct.
16 Correct 397 ms 5804 KB Correct.
17 Correct 507 ms 5780 KB Correct.
18 Correct 466 ms 5712 KB Correct.
19 Correct 1162 ms 5756 KB Correct.
20 Correct 31 ms 3592 KB Correct.
21 Correct 35 ms 4792 KB Correct.
22 Correct 56 ms 8380 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 982 ms 8156 KB Correct.
2 Correct 127 ms 11992 KB Correct.
3 Incorrect 809 ms 126856 KB Wrong Answer.
4 Halted 0 ms 0 KB -