Submission #1080685

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1080685	2024-08-29T12:40:37 Z	KasymK	Cyberland (APIO23_cyberland)	C++17	97 / 100	3000 ms	168356 KB

cyberland

#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second   
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i)
#define wr puts("----------------")
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}

double solve(int n, int m, int k, int h, vector<int> u, vector<int> v, vector<int> w, vector<int> a){
    vector<pii> adj[n];
    for(int i = 0; i < m; ++i){
        adj[u[i]].pb({v[i], w[i]});
        adj[v[i]].pb({u[i], w[i]});
    }
    queue<int> q;
    vector<bool> vis0(n);
    q.push(0);
    vis0[0] = 1;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        if(x == h)
            continue;
        for(auto [i, w] : adj[x])
            if(!vis0[i]){
                q.push(i);
                vis0[i] = 1;
            }
    }
 
    if(!vis0[h])
        return -1;
    k = min(k, (int)1e2);
    vector<vector<double>> dis(n, vector<double>(k+1, 1e18));
    priority_queue<pair<double, pii>> pq;
    for(int i = 0; i < n; ++i){
        if(i == 0 or (a[i] == 0 and vis0[i])){
            dis[i][0] = 0;
            pq.push({0,{i, 0}});
        }
    }
    while(!pq.empty()){
        double d = pq.top().ff; d = -d;
        auto [x, y] = pq.top().ss; pq.pop();
    
        if(d != dis[x][y]) continue;
 
        if(x == h) continue;
    
        for(auto [i, w] : adj[x]){
            if(a[i] == 0) continue;
            if(d+w < dis[i][y]){
                dis[i][y] = d+w;
                pq.push({-dis[i][y],{i, y}});
            }
            if(a[i] == 2 and y < k and (d+w)/2 < dis[i][y+1]){
                dis[i][y+1] = (d+w)/2;
                pq.push({-dis[i][y+1],{i, y+1}});
            }
        }
    }
 
    return *min_element(dis[h].begin(), dis[h].end());
}

// int main(){
//     double kk = solve(3, 2, 30, 2,{1, 2},{2, 0},{12, 4},{1, 2, 1});
//     double kk1 = solve(4, 4, 30, 3,{0, 0, 1, 2},{1, 2, 3, 3},{5, 4, 2, 4},{1, 0, 2, 1});
//     return 0;
// }

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	856 KB	Correct.
2	Correct	17 ms	856 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	1628 KB	Correct.
2	Correct	24 ms	1880 KB	Correct.
3	Correct	22 ms	1828 KB	Correct.
4	Correct	25 ms	1716 KB	Correct.
5	Correct	24 ms	1880 KB	Correct.
6	Correct	23 ms	4936 KB	Correct.
7	Correct	28 ms	4700 KB	Correct.
8	Correct	14 ms	8024 KB	Correct.
9	Correct	20 ms	1224 KB	Correct.
10	Correct	28 ms	1416 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	1628 KB	Correct.
2	Correct	24 ms	1708 KB	Correct.
3	Correct	22 ms	1756 KB	Correct.
4	Correct	22 ms	1372 KB	Correct.
5	Correct	24 ms	1420 KB	Correct.
6	Correct	6 ms	3676 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	156 ms	24964 KB	Correct.
2	Correct	188 ms	1952 KB	Correct.
3	Correct	161 ms	1944 KB	Correct.
4	Correct	170 ms	1908 KB	Correct.
5	Correct	156 ms	1364 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	1628 KB	Correct.
2	Correct	20 ms	1884 KB	Correct.
3	Correct	20 ms	1796 KB	Correct.
4	Correct	20 ms	4444 KB	Correct.
5	Correct	17 ms	1116 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	1624 KB	Correct.
2	Correct	19 ms	1684 KB	Correct.
3	Correct	33 ms	9196 KB	Correct.
4	Correct	14 ms	3268 KB	Correct.
5	Correct	19 ms	1368 KB	Correct.
6	Correct	19 ms	1724 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	169 ms	2164 KB	Correct.
2	Correct	25 ms	1700 KB	Correct.
3	Correct	584 ms	30664 KB	Correct.
4	Correct	472 ms	9940 KB	Correct.
5	Correct	662 ms	50332 KB	Correct.
6	Correct	317 ms	25404 KB	Correct.
7	Correct	447 ms	8548 KB	Correct.
8	Correct	452 ms	3200 KB	Correct.
9	Correct	151 ms	2140 KB	Correct.
10	Correct	142 ms	2372 KB	Correct.
11	Correct	436 ms	2660 KB	Correct.
12	Correct	162 ms	2300 KB	Correct.
13	Correct	178 ms	2420 KB	Correct.
14	Correct	399 ms	11036 KB	Correct.
15	Correct	442 ms	5264 KB	Correct.
16	Correct	148 ms	2156 KB	Correct.
17	Correct	186 ms	2200 KB	Correct.
18	Correct	170 ms	2132 KB	Correct.
19	Correct	387 ms	3224 KB	Correct.
20	Correct	12 ms	604 KB	Correct.
21	Correct	11 ms	1048 KB	Correct.
22	Correct	27 ms	3284 KB	Correct.

Subtask #8
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	928 ms	5672 KB	Correct.
2	Correct	130 ms	7740 KB	Correct.
3	Correct	855 ms	93644 KB	Correct.
4	Correct	1385 ms	9164 KB	Correct.
5	Execution timed out	3063 ms	168356 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Submission #1080685

Compilation message