Submission #1113951

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1113951	2024-11-17T22:06:45 Z	lucascgar	Cyberland (APIO23_cyberland)	C++17	97 / 100	1891 ms	113564 KB

cyberland

#include <bits/stdc++.h>

using namespace std;

/*
tem um ponto de equilibrio mas eu nao ligo o bastante por 3 pontos
*/

typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;

const int MAXN = 1e5+10, MAXK = 50+5;
const long long BIG = 1e18+8;

const long double PRECISION = 1e-7;

vector<pair<int, long double>> e[MAXN];

long double ds[MAXN][MAXK];

bool r[MAXN];

void dfs(int x, int H){
    r[x] = 1;
    if (x==H) return;
    for (auto &[i,cst]:e[x]) if (!r[i]) dfs(i, H);
}

double solve(int n, int m, int k, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
    k = min(k, MAXK-1);
    for (int i=0;i<n;i++){
        e[i].clear();
        for (int j=0;j<=k;j++) ds[i][j]=BIG;
        r[i] = 0;
    }

    for (int i=0;i<m;i++){
        int a = x[i], b = y[i];
        e[a].emplace_back(b, c[i]);
        e[b].emplace_back(a,c[i]);
    }
    dfs(0, H);
    typedef tuple<long double, int, int> node;  // {dst, qntk, u}
    priority_queue<node, vector<node>, greater<>> q;
    for (int i=0;i<n;i++) if (!i || (r[i] && arr[i]==0)){
        ds[i][0] = 0;
        q.emplace(0, 0, i);
    }

    while (!q.empty()){
        auto [d, qk, u] = q.top();
        q.pop();
        if (ds[u][qk] != d) continue;

        if (u == H) continue;

        for (auto &[i, cs]:e[u]){
            long double nc = d+cs;
            // sem usar
            if (ds[i][qk]>nc){
                ds[i][qk] = nc;
                q.emplace(nc, qk, i);
            }

            // usando

            nc /= 2.00;
            if (qk<k && arr[i] == 2 && ds[i][qk+1]> nc){
                ds[i][qk+1] = nc;
                q.emplace(nc, qk+1, i);
            }
        }
    }
    long double ans = BIG;
    for (int i=0;i<=k;i++) ans = min(ans, ds[H][i]);
 
    // cerr << ds[1][4] << '\n';

    if (ans == BIG) return -1;
    return ans;

}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	4688 KB	Correct.
2	Correct	21 ms	4880 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	6992 KB	Correct.
2	Correct	31 ms	6992 KB	Correct.
3	Correct	35 ms	7076 KB	Correct.
4	Correct	30 ms	6992 KB	Correct.
5	Correct	31 ms	6992 KB	Correct.
6	Correct	31 ms	16540 KB	Correct.
7	Correct	37 ms	14416 KB	Correct.
8	Correct	20 ms	25640 KB	Correct.
9	Correct	28 ms	6736 KB	Correct.
10	Correct	29 ms	6736 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	6992 KB	Correct.
2	Correct	32 ms	6992 KB	Correct.
3	Correct	29 ms	6992 KB	Correct.
4	Correct	29 ms	7068 KB	Correct.
5	Correct	31 ms	6904 KB	Correct.
6	Correct	10 ms	14160 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	430 ms	73044 KB	Correct.
2	Correct	510 ms	7764 KB	Correct.
3	Correct	440 ms	8044 KB	Correct.
4	Correct	474 ms	7748 KB	Correct.
5	Correct	376 ms	7096 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	7248 KB	Correct.
2	Correct	29 ms	7248 KB	Correct.
3	Correct	29 ms	7248 KB	Correct.
4	Correct	30 ms	17416 KB	Correct.
5	Correct	31 ms	6736 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	7248 KB	Correct.
2	Correct	24 ms	7316 KB	Correct.
3	Correct	56 ms	79944 KB	Correct.
4	Correct	25 ms	12784 KB	Correct.
5	Correct	27 ms	6736 KB	Correct.
6	Correct	27 ms	7248 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	506 ms	8976 KB	Correct.
2	Correct	69 ms	10680 KB	Correct.
3	Correct	1018 ms	102292 KB	Correct.
4	Correct	885 ms	27952 KB	Correct.
5	Correct	1891 ms	113564 KB	Correct.
6	Correct	822 ms	92320 KB	Correct.
7	Correct	825 ms	29776 KB	Correct.
8	Correct	858 ms	9988 KB	Correct.
9	Correct	432 ms	11060 KB	Correct.
10	Correct	450 ms	9204 KB	Correct.
11	Correct	843 ms	7504 KB	Correct.
12	Correct	473 ms	9128 KB	Correct.
13	Correct	495 ms	9168 KB	Correct.
14	Correct	698 ms	55732 KB	Correct.
15	Correct	797 ms	20328 KB	Correct.
16	Correct	459 ms	9020 KB	Correct.
17	Correct	551 ms	8860 KB	Correct.
18	Correct	555 ms	8888 KB	Correct.
19	Correct	1278 ms	8844 KB	Correct.
20	Correct	36 ms	7452 KB	Correct.
21	Correct	36 ms	7784 KB	Correct.
22	Correct	59 ms	14016 KB	Correct.

Subtask #8
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1252 ms	16276 KB	Correct.
2	Correct	168 ms	15028 KB	Correct.
3	Incorrect	1018 ms	104420 KB	Wrong Answer.
4	Halted	0 ms	0 KB	-

Submission #1113951

Compilation message