제출 #101197

#제출 시각아이디문제언어결과실행 시간메모리
101197tinjyu악어의 지하 도시 (IOI11_crocodile)C++14
89 / 100
2066 ms135844 KiB
#include "crocodile.h" #include <iostream> using namespace std; long long int fin[100005],t[20000005],c[100005],road[5000005][3],map[100005],mi[100005][4],tag[100005]; int dfs(int x){ //cout<<x<<endl; int q=map[x]; tag[x]=1; while(q!=-1) { //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; return 0; } int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) { for(int i=0;i<n;i++)map[i]=-1; 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++) { mi[i][0]=9999999999; mi[i][1]=9999999999; mi[i][2]=-1; mi[i][3]=-1; } for(int i=0;i<k;i++) { c[p[i]]=2; mi[p[i]][0]=0; mi[p[i]][1]=0; } int pp=0,qq=k-1; for(int i=0;i<k;i++)t[i]=p[i]; while(pp<=qq) { if(c[t[pp]]>=2&& fin[t[pp]]==0) { //cout<<t[pp]<<" "; int q=map[t[pp]]; while(q!=-1) { //cout<<q<<" "<<road[q][0]<<" "; //system("pause"); if(fin[road[q][0]]==0) { qq++; c[road[q][0]]++; t[qq]=road[q][0]; } q=road[q][1]; } //cout<<endl; fin[t[pp]]=1; } pp++; } for(int i=0;i<k;i++)t[i]=p[i]; pp=0; qq=k-1; for(int i=0;i<n;i++)fin[i]=0; while(pp<=qq) { while((fin[t[pp]]==1 || mi[t[pp]][1]==9999999999) && pp<=qq)pp++; if(pp>qq)break; int q=map[t[pp]]; //cout<<t[pp]<<" "<<mi[t[pp]][1]<<" "; while(q!=-1) { //cout<<road[q][0]<<" "<<mi[road[q][0]][0]<<" "<<mi[road[q][0]][2]<<" "<<mi[road[q][0]][1]<<" "<<mi[road[q][0]][3]<<" "; //if(road[q][0]==0)system("pause"); if(c[road[q][0]]>=2) { qq++; t[qq]=road[q][0]; if(mi[t[pp]][1]+road[q][2]<mi[road[q][0]][0]) { if(t[pp]==mi[road[q][0]][2])mi[road[q][0]][0]=mi[t[pp]][1]+road[q][2]; else { fin[road[q][0]]=0; mi[road[q][0]][1]=mi[road[q][0]][0]; mi[road[q][0]][3]=mi[road[q][0]][2]; mi[road[q][0]][0]=mi[t[pp]][1]+road[q][2]; mi[road[q][0]][2]=t[pp]; } } else if(mi[t[pp]][1]+road[q][2]<mi[road[q][0]][1]) { fin[road[q][0]]=0; mi[road[q][0]][1]=mi[t[pp]][1]+road[q][2]; mi[road[q][0]][3]=t[pp]; } } q=road[q][1]; } //cout<<endl; //cout<<mi[0][0]<<" "<<mi[0][1]<<endl; fin[t[pp]]=1; pp++; } //cout<<mi[0][0]<<" "<<mi[0][1]<<endl; //for(int i=0;i<n;i++)cout<<c[i]<<" "; //cout<<endl; //dfs(0); //for(int i=0;i<n;i++)cout<<mi[i][0]<<" "<<mi[i][1]<<endl;; //cout<<endl; return mi[0][1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...