oj.uz

Submission #822732

# Submission time Handle Problem Language Result Execution time Memory
822732 2023-08-12T04:30:46 Z Hanksburger Cyberland (APIO23_cyberland) C++17
100 / 100
 1294 ms 65300 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
priority_queue<pair<double, int> > pq;
vector<pair<int, int> > adj[100005];
int ok[100005], final[100005];
double dist[75][100005];
queue<int> q;
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> a)
{
    k=min(k, 70);
    for (int i=0; i<n; i++)
    {
        adj[i].clear();
        ok[i]=0;
    }
    for (int i=0; i<m; i++)
    {
        adj[x[i]].push_back({y[i], c[i]});
        adj[y[i]].push_back({x[i], c[i]});
    }
    ok[0]=1;
    q.push(0);
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        if (u==h)
            continue;
        for (int i=0; i<adj[u].size(); i++)
        {
            int v=adj[u][i].first;
            if (!ok[v])
            {
                ok[v]=1;
                q.push(v);
            }
        }
    }
    for (int i=0; i<=k; i++)
        for (int j=0; j<n; j++)
            dist[i][j]=1e18;
    dist[0][0]=0;
    pq.push({0, 0});
    for (int i=0; i<=k; i++)
    {
        for (int j=0; j<n; j++)
        {
            if (ok[j] && !a[j])
            {
                dist[i][j]=0;
                pq.push({0, j});
            }
        }
        if (i)
        {
            for (int j=0; j<n; j++)
            {
                if (ok[j] && a[j]==2)
                {
                    for (int l=0; l<adj[j].size(); l++)
                    {
                        int v=adj[j][l].first, w=adj[j][l].second;
                        if (ok[v])
                        {
                            dist[i][v]=min(dist[i][v], dist[i-1][j]/2+w);
                            pq.push({-dist[i][v], v});
                        }
                        
                    }
                }
            }
        }
        for (int j=0; j<n; j++)
            final[j]=0;
        while (!pq.empty())
        {
            int u=pq.top().second;
            pq.pop();
            if (final[u])
                continue;
            final[u]=1;
            if (u==h)
                continue;
            for (int j=0; j<adj[u].size(); j++)
            {
                int v=adj[u][j].first, w=adj[u][j].second;
                if (ok[v] && dist[i][u]+w<dist[i][v])
                {
                    dist[i][v]=dist[i][u]+w;
                    pq.push({-dist[i][v], v});
                }
            }
        }
    }
    double mn=1e18;
    for (int i=0; i<=k; i++)
        mn=min(mn, dist[i][h]);
    if (mn<5e17)
        return mn;
    else
        return -1;
}

Compilation message

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:30:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for (int i=0; i<adj[u].size(); i++)
      |                       ~^~~~~~~~~~~~~~
cyberland.cpp:61:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |                     for (int l=0; l<adj[j].size(); l++)
      |                                   ~^~~~~~~~~~~~~~
cyberland.cpp:85:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             for (int j=0; j<adj[u].size(); j++)
      |                           ~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2984 KB Correct.
2 Correct 23 ms 3000 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3288 KB Correct.
2 Correct 25 ms 3156 KB Correct.
3 Correct 27 ms 3248 KB Correct.
4 Correct 27 ms 3244 KB Correct.
5 Correct 30 ms 3228 KB Correct.
6 Correct 26 ms 5976 KB Correct.
7 Correct 31 ms 5900 KB Correct.
8 Correct 14 ms 9172 KB Correct.
9 Correct 35 ms 2928 KB Correct.
10 Correct 27 ms 2932 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 3200 KB Correct.
2 Correct 151 ms 3184 KB Correct.
3 Correct 148 ms 3260 KB Correct.
4 Correct 94 ms 2916 KB Correct.
5 Correct 84 ms 2920 KB Correct.
6 Correct 51 ms 5516 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 21404 KB Correct.
2 Correct 141 ms 3220 KB Correct.
3 Correct 121 ms 3184 KB Correct.
4 Correct 116 ms 3172 KB Correct.
5 Correct 76 ms 2920 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3316 KB Correct.
2 Correct 25 ms 3284 KB Correct.
3 Correct 28 ms 3208 KB Correct.
4 Correct 37 ms 6128 KB Correct.
5 Correct 22 ms 2944 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 3252 KB Correct.
2 Correct 58 ms 3264 KB Correct.
3 Correct 48 ms 26800 KB Correct.
4 Correct 67 ms 5344 KB Correct.
5 Correct 55 ms 2908 KB Correct.
6 Correct 80 ms 3288 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 3232 KB Correct.
2 Correct 30 ms 3476 KB Correct.
3 Correct 378 ms 23552 KB Correct.
4 Correct 277 ms 8564 KB Correct.
5 Correct 593 ms 17440 KB Correct.
6 Correct 388 ms 10464 KB Correct.
7 Correct 257 ms 8736 KB Correct.
8 Correct 193 ms 4052 KB Correct.
9 Correct 139 ms 3232 KB Correct.
10 Correct 137 ms 3220 KB Correct.
11 Correct 186 ms 3360 KB Correct.
12 Correct 159 ms 3264 KB Correct.
13 Correct 132 ms 3276 KB Correct.
14 Correct 229 ms 10808 KB Correct.
15 Correct 210 ms 5424 KB Correct.
16 Correct 138 ms 3220 KB Correct.
17 Correct 176 ms 3220 KB Correct.
18 Correct 146 ms 3176 KB Correct.
19 Correct 429 ms 3292 KB Correct.
20 Correct 10 ms 2900 KB Correct.
21 Correct 10 ms 3156 KB Correct.
22 Correct 32 ms 3668 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 3760 KB Correct.
2 Correct 56 ms 4216 KB Correct.
3 Correct 234 ms 65300 KB Correct.
4 Correct 285 ms 8260 KB Correct.
5 Correct 1294 ms 30624 KB Correct.
6 Correct 796 ms 15336 KB Correct.
7 Correct 432 ms 19192 KB Correct.
8 Correct 213 ms 6168 KB Correct.
9 Correct 244 ms 4684 KB Correct.
10 Correct 249 ms 4752 KB Correct.
11 Correct 142 ms 4360 KB Correct.
12 Correct 318 ms 4732 KB Correct.
13 Correct 292 ms 4836 KB Correct.
14 Correct 1082 ms 30340 KB Correct.
15 Correct 972 ms 36328 KB Correct.
16 Correct 417 ms 15908 KB Correct.
17 Correct 284 ms 7356 KB Correct.
18 Correct 271 ms 4820 KB Correct.
19 Correct 312 ms 4856 KB Correct.
20 Correct 303 ms 4816 KB Correct.
21 Correct 912 ms 5736 KB Correct.
22 Correct 12 ms 3156 KB Correct.
23 Correct 19 ms 3708 KB Correct.
24 Correct 69 ms 4436 KB Correct.