제출 #101144

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
101144		tinjyu	악어의 지하 도시 (IOI11_crocodile)	C++14	0 / 100	2 ms	384 KiB

crocodile

#include "crocodile.h"
#include <iostream>
using namespace std;
long long int fin[100005],t[20000005],c[100005],road[5000005][3],map[100005],mi[100005][2],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;
	}
	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((t[pp]==-1 || 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]][1]<<"  ";
			//if(road[q][0]==0)system("pause");
			if(c[road[q][0]]>=2 && fin[road[q][0]]==0)
			{
				qq++;
				t[qq]=road[q][0];
				if(mi[t[pp]][1]+road[q][2]<mi[road[q][0]][0])
				{
					mi[road[q][0]][1]=mi[road[q][0]][0];
					mi[road[q][0]][0]=mi[t[pp]][1]+road[q][2];
				}
				else if(mi[t[pp]][1]+road[q][2]<mi[road[q][0]][1])
				{
					mi[road[q][0]][1]=mi[t[pp]][1]+road[q][2];
				}
			}
			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];
}

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