| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 101006 | tinjyu | Crocodile's Underground City (IOI11_crocodile) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "crocodile.h"
#include <iostream>
using namespace std;
long long int c[100005],t[20000005],road[2000005][3],map[100005],mi[100005][2],tag[100005],end[100005];
int find(int x){
int q=map[x];
while(q!=0)
{
if(c[road[q][0]]==-1)find(road[q][0]);
if(c[road[q][0]]>=2)c[x]++;
q=road[q][1];
}
if(c[x]==-1)c[x]=0;
}
int dfs(int x){
//cout<<x<<endl;
int q=map[x];
tag[x]=1;
while(q!=0)
{
//cout<<c[road[q][0]]<<" "<<tag[road[q][0]]<<endl;
if(c[road[q][0]]>=2 && tag[road[q][0]]==0)
{
if(mi[road[q][0]][1]==9999999999)dfs(road[q][0]);
if(mi[road[q][0]][1]+road[q][2]<mi[x][0])
{
mi[x][1]=mi[x][0];
mi[x][0]=mi[road[q][0]][1]+road[q][2];
}
else if(mi[road[q][0]][1]+road[q][2]<mi[x][1])
{
mi[x][1]=mi[road[q][0]][1]+road[q][2];
}
}
q=road[q][1];
}
tag[x]=0;
}
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
for(int i=0;i<m;i++)
{
road[i*2][0]=r[i][0];
road[i*2][1]=map[r[i][1]];
road[i*2][2]=l[i];
map[r[i][1]]=i*2;
road[i*2+1][0]=r[i][1];
road[i*2+1][1]=map[r[i][0]];
road[i*2+1][2]=l[i];
map[r[i][0]]=i*2+1;
}
//for(int i=0;i<n;i++)cout<<map[i]<<" ";
//cout<<endl;
//for(int i=0;i<=(m-1)*2;i++)
// cout<<i<<" "<<road[i][0]<<" "<<road[i][1]<<" "<<road[i][2]<<endl;
for(int i=0;i<n;i++)c[i]=-1;
for(int i=0;i<n;i++)
{
mi[i][0]=9999999999;
mi[i][1]=9999999999;
}
for(int i=0;i<k;i++)
{
end[p[i]]=1;
c[p[i]]=2;
mi[p[i]][0]=0;
mi[p[i]][1]=0;
}
int pp=1,qq=1;
t[1]=0;
for(int i=0;i<n;i++)
{
find(i);
}
//for(int i=0;i<=n;i++)cout<<c[i]<<" ";
dfs(0);
//for(int i=0;i<n;i++)cout<<mi[i][0]<<" "<<mi[i][1]<<endl;;
//cout<<endl;
return mi[0][1];
}