답안 #116570

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
116570 2019-06-13T00:25:22 Z andremfq 악어의 지하 도시 (IOI11_crocodile) C++17
46 / 100
8 ms 5504 KB
```#include<bits/stdc++.h>
#define debug(args...) //fprintf(stderr,args)
#include "crocodile.h"
using namespace std;
const int MAXN=100010,INF=2123456789;
vector<int> grf[MAXN],ps[MAXN];
int d1[MAXN],d2[MAXN],marc[MAXN];
void dfs1(int v)
{
debug("at=%d\n",v);
if(d1[v]==0)return;
for(int i=0;i<grf[v].size();i++)
{
int viz=grf[v][i],p=ps[v][i];
if(marc[viz]==1)continue;
marc[viz]=1;
dfs1(viz);
if(d1[viz]==0)marc[viz]=0;
d2[v]=min(d2[viz]+p,d2[v]);
if(d2[v]<d1[v])swap(d1[v],d2[v]);
}
}
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
for(int i=0;i<m;i++)
{
int a=r[i][0],b=r[i][1],pe=l[i];
grf[a].push_back(b);grf[b].push_back(a);
ps[a].push_back(pe);ps[b].push_back(pe);
}
for(int i=0;i<n;i++)
{
d1[i]=INF;d2[i]=INF;
}
for(int i=0;i<k;i++)
{
d1[p[i]]=0;d2[p[i]]=0;
}
marc[0]=1;
dfs1(0);
for(int i=0;i<n;i++)
{
debug("dist= %d %d\n",d1[i],d2[i]);
}
int resp=d2[0];
if(resp>=INF)resp=-1;
return resp;
}
/*int r[MAXN][2],l[MAXN],p[MAXN];
int main()
{
int n,m,k;
scanf("%d %d %d",&n,&m,&k);
for(int i=0;i<m;i++)
{
int a,b,P;
scanf("%d %d %d",&a,&b,&P);
r[i][0]=a;r[i][1]=b;l[i]=P;
}
for(int i=0;i<k;i++)
{
scanf("%d",&p[i]);
}
printf("%d\n",travel_plan(n,m,r,l,k,p));
return 0;
}*/```

Compilation message

```crocodile.cpp: In function 'void dfs1(int)':
crocodile.cpp:12:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<grf[v].size();i++)
~^~~~~~~~~~~~~~```

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 8 ms 5232 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 7 ms 5248 KB Output is correct
8 Correct 7 ms 5120 KB Output is correct

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 8 ms 5232 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 7 ms 5248 KB Output is correct
8 Correct 7 ms 5120 KB Output is correct
9 Incorrect 8 ms 5504 KB Output isn't correct
10 Halted 0 ms 0 KB -