oj.uz

Submission #756956

# Submission time Handle Problem Language Result Execution time Memory
756956 2023-06-12T11:42:24 Z Valters07 Cyberland (APIO23_cyberland) C++17
100 / 100
 1751 ms 79140 KB 
#include <bits/stdc++.h>
#include "cyberland.h"
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const int N = 1e5+5;
const int K = 70+2;
vector<pair<int,int> > g[N];
double dist[N][K];
bool vis[N][K], vis2[N];
vector<int> starts, arr2;
void dfs(int u, int h)
{
    vis2[u]=1;
    if(arr2[u]==0)
        starts.pb(u);
    for(auto v:g[u])
        if(!vis2[v.fi]&&v.fi!=h)
            dfs(v.fi,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,70);
    arr2=arr;
    for(int i = 0;i<m;i++)
        g[x[i]].pb({y[i],c[i]}),
        g[y[i]].pb({x[i],c[i]});
    for(int i = 0;i<n;i++)
        for(int j = 0;j<=k;j++)
            dist[i][j]=1e15,
            vis[i][j]=0;
    priority_queue<pair<double,pair<int,int> >,vector<pair<double,pair<int,int> > >,greater<pair<double,pair<int,int> > > > q[k+1];
    dist[0][0]=0;
    q[0].push({0,{0,0}});
    for(int i = 0;i<n;i++)
        vis2[i]=0;
    dfs(0,h);
    for(auto x:starts)
        q[0].push({0,{x,0}}),
        dist[x][0]=0;
    starts.clear();
    for(int i = 0;i<=k;i++)
        vis[h][i]=1;
    for(int qi = 0;qi<=k;qi++)
    {
        while(!q[qi].empty())
        {
            int u = q[qi].top().se.fi, dv = q[qi].top().se.se;
            q[qi].pop();
            if(vis[u][dv])
                continue;
            vis[u][dv]=1;
            for(auto v:g[u])
            {
                double nwc = dist[u][dv]+v.se;
                if(dist[v.fi][dv]>nwc)
                    dist[v.fi][dv]=nwc,
                    q[qi].push({nwc,{v.fi,dv}});
                if(arr[v.fi]==2&&dv<k)
                {
                    nwc/=2;
                    if(dist[v.fi][dv+1]>nwc)
                        dist[v.fi][dv+1]=nwc,
                        q[qi+1].push({nwc,{v.fi,dv+1}});
                }
            }
        }
    }
    double best = 1e15;
    for(int i = 0;i<=k;i++)
        best=min(best,dist[h][i]);
    for(int i = 0;i<n;i++)
        g[i].clear();
    if(best>=2e14)
        return -1;
    return best;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2760 KB Correct.
2 Correct 25 ms 2800 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3412 KB Correct.
2 Correct 27 ms 3412 KB Correct.
3 Correct 26 ms 3464 KB Correct.
4 Correct 27 ms 3436 KB Correct.
5 Correct 27 ms 3400 KB Correct.
6 Correct 30 ms 9684 KB Correct.
7 Correct 37 ms 9452 KB Correct.
8 Correct 27 ms 16516 KB Correct.
9 Correct 23 ms 2772 KB Correct.
10 Correct 26 ms 2820 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3440 KB Correct.
2 Correct 27 ms 3460 KB Correct.
3 Correct 26 ms 3412 KB Correct.
4 Correct 26 ms 2772 KB Correct.
5 Correct 28 ms 2796 KB Correct.
6 Correct 9 ms 8532 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 47080 KB Correct.
2 Correct 119 ms 3668 KB Correct.
3 Correct 111 ms 3720 KB Correct.
4 Correct 109 ms 3688 KB Correct.
5 Correct 73 ms 2832 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3512 KB Correct.
2 Correct 32 ms 3472 KB Correct.
3 Correct 24 ms 3460 KB Correct.
4 Correct 29 ms 9812 KB Correct.
5 Correct 21 ms 2788 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3464 KB Correct.
2 Correct 21 ms 3540 KB Correct.
3 Correct 61 ms 56100 KB Correct.
4 Correct 21 ms 8020 KB Correct.
5 Correct 25 ms 2800 KB Correct.
6 Correct 24 ms 3540 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 3724 KB Correct.
2 Correct 22 ms 4324 KB Correct.
3 Correct 789 ms 71760 KB Correct.
4 Correct 305 ms 18320 KB Correct.
5 Correct 731 ms 45912 KB Correct.
6 Correct 265 ms 23388 KB Correct.
7 Correct 311 ms 20096 KB Correct.
8 Correct 223 ms 5356 KB Correct.
9 Correct 118 ms 3724 KB Correct.
10 Correct 109 ms 3772 KB Correct.
11 Correct 219 ms 3812 KB Correct.
12 Correct 121 ms 3768 KB Correct.
13 Correct 125 ms 3808 KB Correct.
14 Correct 413 ms 36388 KB Correct.
15 Correct 255 ms 11844 KB Correct.
16 Correct 120 ms 3776 KB Correct.
17 Correct 158 ms 3792 KB Correct.
18 Correct 130 ms 3768 KB Correct.
19 Correct 343 ms 3800 KB Correct.
20 Correct 9 ms 2812 KB Correct.
21 Correct 12 ms 3592 KB Correct.
22 Correct 20 ms 4736 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 4076 KB Correct.
2 Correct 42 ms 4844 KB Correct.
3 Correct 921 ms 79140 KB Correct.
4 Correct 307 ms 7704 KB Correct.
5 Correct 1702 ms 64292 KB Correct.
6 Correct 668 ms 35152 KB Correct.
7 Correct 737 ms 29252 KB Correct.
8 Correct 288 ms 4112 KB Correct.
9 Correct 244 ms 4112 KB Correct.
10 Correct 220 ms 4100 KB Correct.
11 Correct 199 ms 2852 KB Correct.
12 Correct 265 ms 4072 KB Correct.
13 Correct 257 ms 4132 KB Correct.
14 Correct 1751 ms 46720 KB Correct.
15 Correct 1476 ms 40096 KB Correct.
16 Correct 508 ms 17040 KB Correct.
17 Correct 295 ms 5612 KB Correct.
18 Correct 249 ms 4096 KB Correct.
19 Correct 268 ms 4112 KB Correct.
20 Correct 274 ms 4104 KB Correct.
21 Correct 745 ms 4008 KB Correct.
22 Correct 14 ms 2900 KB Correct.
23 Correct 19 ms 3856 KB Correct.
24 Correct 39 ms 5916 KB Correct.