oj.uz

답안 #496631

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
496631 2021-12-21T17:03:05 Z Homichki 악어의 지하 도시 (IOI11_crocodile) C++14
0 / 100
 3 ms 4940 KB 
#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[]);
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(dp[z1.first]<1e10)
                {
                    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);
                    }
                }
                else
                {
                    kol[z1.first]++;
                    if(kol[z1.first]>1)
                    {
                        q.push(z1.first);
                    }
                }
            }
            if(w==1)
            {
                dp[x]=0;
            }
        }
    }
    if(dp[0]>1e9)
    {
        return -1;
    }
    else
    {
        return dp[0];
    }
}

Compilation message

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

Subtask #1
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -