Submission #496618

#	Time	Username	Problem	Language	Result	Execution time	Memory
496618		Homichki	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	2 ms	4940 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"

using namespace std;
typedef long long ll;
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //ifstream cin("lightson.in");
    //ofstream cout("lightson.out");
    vector<pair<ll,ll> > graph[100000];
    ll dp[100001],kol[100001],u[100001];
    ll ma,qqq,i,kot,j,z,x,y,kry,w,sum,t,h,ot,mi;
    pair<ll,ll> z1,x1;
    for(i=0;i<m;i++)
    {
        r[i][0]--;
        r[i][1]--;
        graph[r[i][0]].push_back({r[i][1],l[i]});
        graph[r[i][1]].push_back({r[i][0],l[i]});
    }
    for(i=0;i<n;i++)
    {
        dp[i]=1e15;
        kol[i]=0;
    }
    queue<ll> q;
    for(i=0;i<k;i++)
    {
        q.push(p[i]-1);
        dp[p[i]-1]=0;
    }
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        if(u[x]==0)
        {
            u[x]=1;
            y=graph[x].size();
            mi=1e15;
            w=0;
            if(dp[x]==0)
            {
                w++;
            }
            for(i=0;i<y;i++)
            {
                z1=graph[x][i];
                if(mi>dp[z1.first]+z1.second)
                {
                    dp[x]=mi;
                    mi=dp[z1.first]+z1.second;
                }
                else
                {
                    dp[x]=min(dp[x],dp[z1.first]+z1.second);
                }
                kol[z1.first]++;
                if(kol[z1.first]>1)
                {
                    q.push(z1.first);
                }
            }
            if(w==1)
            {
                dp[x]=0;
            }
        }
    }
    if(dp[0]>1e9)
    {
        cout<<-1;
    }
    else
    {
        cout<<dp[0]<<"\n";
    }
    return 0;
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:14:8: warning: unused variable 'ma' [-Wunused-variable]
   14 |     ll ma,qqq,i,kot,j,z,x,y,kry,w,sum,t,h,ot,mi;
      |        ^~
crocodile.cpp:14:11: warning: unused variable 'qqq' [-Wunused-variable]
   14 |     ll ma,qqq,i,kot,j,z,x,y,kry,w,sum,t,h,ot,mi;
      |           ^~~
crocodile.cpp:14:17: warning: unused variable 'kot' [-Wunused-variable]
   14 |     ll ma,qqq,i,kot,j,z,x,y,kry,w,sum,t,h,ot,mi;
      |                 ^~~
crocodile.cpp:14:21: warning: unused variable 'j' [-Wunused-variable]
   14 |     ll ma,qqq,i,kot,j,z,x,y,kry,w,sum,t,h,ot,mi;
      |                     ^
crocodile.cpp:14:23: warning: unused variable 'z' [-Wunused-variable]
   14 |     ll ma,qqq,i,kot,j,z,x,y,kry,w,sum,t,h,ot,mi;
      |                       ^
crocodile.cpp:14:29: warning: unused variable 'kry' [-Wunused-variable]
   14 |     ll ma,qqq,i,kot,j,z,x,y,kry,w,sum,t,h,ot,mi;
      |                             ^~~
crocodile.cpp:14:35: warning: unused variable 'sum' [-Wunused-variable]
   14 |     ll ma,qqq,i,kot,j,z,x,y,kry,w,sum,t,h,ot,mi;
      |                                   ^~~
crocodile.cpp:14:39: warning: unused variable 't' [-Wunused-variable]
   14 |     ll ma,qqq,i,kot,j,z,x,y,kry,w,sum,t,h,ot,mi;
      |                                       ^
crocodile.cpp:14:41: warning: unused variable 'h' [-Wunused-variable]
   14 |     ll ma,qqq,i,kot,j,z,x,y,kry,w,sum,t,h,ot,mi;
      |                                         ^
crocodile.cpp:14:43: warning: unused variable 'ot' [-Wunused-variable]
   14 |     ll ma,qqq,i,kot,j,z,x,y,kry,w,sum,t,h,ot,mi;
      |                                           ^~

• Subtask 1: 0 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11