oj.uz

Submission #38891

# Submission time Handle Problem Language Result Execution time Memory
38891 2018-01-07T15:47:39 Z faustaadp Crocodile's Underground City (IOI11_crocodile) C++14
46 / 100
 853 ms 175356 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,i,b[101010],d[101010];
vector<pair<ll,ll> > v[101010];
ll rmt(ll aa)
{
//	cout<<aa<<"aa\n";
	if(b[aa])
		return 0;
	if(d[aa]==-1)
	{
		d[aa]=10e17;
		ll ii,mi=10e17;
		for(ii=0;ii<v[aa].size();ii++)
		{
			if(v[aa][ii].se+rmt(v[aa][ii].fi)<mi)
			{
				d[aa]=mi;
				mi=v[aa][ii].se+rmt(v[aa][ii].fi);
			}
			else
			if(v[aa][ii].se+rmt(v[aa][ii].fi)<d[aa])
				d[aa]=v[aa][ii].se+rmt(v[aa][ii].fi);
		}
//		cout<<aa<<" "<<d[aa]<<"\n";
	}
	return d[aa];
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	n=N;
	for(i=0;i<M;i++)
	{
		v[R[i][0]].pb(mp(R[i][1],L[i]));
		v[R[i][1]].pb(mp(R[i][0],L[i]));
	}
	for(i=0;i<K;i++)
		b[P[i]]=1;
	memset(d,-1,sizeof(d));
//	cout<<v[0].size()<<"v0\n";
//	cout<<v[0][0].fi<<" "<<v[0][1].fi<<" "<<v[0][2].fi<<"\n";
  	return rmt(0);
}

/*
//#include "crocodile.h"
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 50000
#define MAX_M 10000000

static int N, M;
static int R[MAX_M][2];
static int L[MAX_M];
static int K;
static int P[MAX_N];
static int solution;

inline 
void my_assert(int e) {if (!e) abort();}

void read_input()
{
  int i;
  my_assert(3==scanf("%d %d %d",&N,&M,&K));
  for(i=0; i<M; i++)
    my_assert(3==scanf("%d %d %d",&R[i][0],&R[i][1],&L[i]));
  for(i=0; i<K; i++)
    my_assert(1==scanf("%d",&P[i]));
  my_assert(1==scanf("%d",&solution));
}

int main()
{
  int ans;
  read_input();
  ans = travel_plan(N,M,R,L,K,P);
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

  return 0;
}
*/

Compilation message

crocodile.cpp: In function 'long long int rmt(long long int)':
crocodile.cpp:20:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ii=0;ii<v[aa].size();ii++)
              ^

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 123344 KB Output is correct
2 Correct 3 ms 123344 KB Output is correct
3 Correct 0 ms 123344 KB Output is correct
4 Correct 3 ms 123476 KB Output is correct
5 Correct 0 ms 123476 KB Output is correct
6 Correct 0 ms 123344 KB Output is correct
7 Correct 0 ms 123480 KB Output is correct
8 Correct 3 ms 123476 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 123608 KB Output is correct
2 Incorrect 3 ms 123344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 853 ms 175356 KB Output isn't correct
2 Halted 0 ms 0 KB -