oj.uz

Submission #101009

# Submission time Handle Problem Language Result Execution time Memory
101009 2019-03-16T03:31:03 Z tinjyu Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 276 ms 263168 KB 
#include "crocodile.h"
#include <iostream>
using namespace std;
long long int c[100005],road[2000005][3],map[100005],mi[100005][2],tag[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;
	return 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;
	return 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++)
	{
		c[p[i]]=2;
		mi[p[i]][0]=0;
		mi[p[i]][1]=0;
	}
	int pp=1,qq=1;
	
	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];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:70:6: warning: unused variable 'pp' [-Wunused-variable]
  int pp=1,qq=1;
      ^~
crocodile.cpp:70:11: warning: unused variable 'qq' [-Wunused-variable]
  int pp=1,qq=1;
           ^~

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Runtime error 276 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Runtime error 276 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Runtime error 276 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -