oj.uz

Submission #644055

# Submission time Handle Problem Language Result Execution time Memory
644055 2022-09-23T16:47:44 Z ToroTN Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 2 ms 2644 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define X first
#define Y second
vector<pair<ll,ll> > g[100005];
ll n,m,u_i,v_i,w_i,d[100005],u,y,cost,k,p[100005],pin,ans;
priority_queue<pair<ll,ll> > pq;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    n=N;
    m=M;
    k=K;
    for(int i=0;i<k;i++)
    {
        p[i+1]=P[i]+1;
    }
    for(int i=0;i<m;i++)
    {
        u_i=R[i][0]+1;
        v_i=R[i][1]+1;
        w_i=L[i];
        g[u_i].pb({w_i,v_i});
        g[v_i].pb({w_i,u_i});
    }
    for(int i=1;i<=n;i++)
    {
        sort(g[i].begin(),g[i].end());
        d[i]=2e9;
    }
    d[1]=0;
    pq.push({0,1});
    while(!pq.empty())
    {
        u=pq.top().second;
        pq.pop();
        pin=0;
        for(int i=0;i<g[u].size();i++)
        {
            cost=g[u][i].X;
            y=g[u][i].Y;
            if(d[u]+cost<d[y])
            {
                if(pin==0)
                {
                    pin=1;
                }else
                {
                    d[y]=d[u]+cost;
                    pq.push({-d[y],y});
                }
            }
        }
    }
    ans=2e9;
    for(int i=1;i<=k;i++)
    {
        ans=min(ans,d[p[i]]);
    }
    return ans;
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int i=0;i<g[u].size();i++)
      |                     ~^~~~~~~~~~~~

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -