oj.uz

Submission #28855

# Submission time Handle Problem Language Result Execution time Memory
28855 2017-07-17T10:58:34 Z ozaslan Tropical Garden (IOI11_garden) C++14
0 / 100
 6 ms 2808 KB 
#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define MAX_N 100005
using namespace std;



/*
#define MAX_M  1000000
#define MAX_Q  2000

static int N, M, P, Q;
static int R[MAX_M][2];
static int G[MAX_Q];
static int solutions[MAX_Q];
static int answers[MAX_Q];
static int answer_count;

inline
void my_assert(int e) {if (!e) abort();}
void read_input()
{
  int i;
  my_assert(3==scanf("%d %d %d",&N,&M,&P));
  for(i=0; i<M; i++)
    my_assert(2==scanf("%d %d",&R[i][0],&R[i][1]));
  my_assert(1==scanf("%d",&Q));
  for(i=0; i<Q; i++)
    my_assert(1==scanf("%d",&G[i]));
  for(i=0; i<Q; i++)
    my_assert(1==scanf("%d",&solutions[i]));
}

void answer(int x)
{
  if(answer_count>=Q) {
    printf("Incorrect.  Too many answers.\n");
    exit(0);
  }
  answers[answer_count] = x;
  answer_count++;
}

int main()
{
    freopen("grader.in.2", "r", stdin);
  int correct, i;

  read_input();
  answer_count = 0;
  count_routes(N,M,P,R,Q,G);

  if(answer_count!=Q) {
    printf("Incorrect.  Too few answers.\n");
    exit(0);
  }

  correct = 1;
  for(i=0; i<Q; i++)
    if(answers[i]!=solutions[i])
      correct = 0;
  if(correct)
    printf("Correct.\n");
  else {
    printf("Incorrect.\n");
    printf("Expected: ");
    for(i=0; i<Q; i++)
      printf("%d ",solutions[i]);
    printf("\nReturned: ");
    for(i=0; i<Q; i++)
      printf("%d ",answers[i]);
  }
  return 0;
}

*/


vector< pair<int, int> > E[MAX_N];
vector< pair<int, int> >::iterator it;
int sonuc = 0;

int DFS(int dugum, int K, int P, int ata) {
	if (!K) {
		if(dugum == P) sonuc++;
		return -1;
	}

    sort(E[dugum].begin(), E[dugum].end());

    int s = E[dugum].size();
	for(int i = 0; i < s; i++) {
		if(E[dugum][i].second != ata) {
            K--;
			K = DFS(E[dugum][i].second , K, P, dugum);

            if (!K) {
                if(dugum == P) sonuc++;
                return -1;
            }

            if (K == -1) return -1;
        }
	}

    K--;
	return K;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{

	for (int i = 0; i < M; i++) {
		E[ R[i][0] ].push_back( make_pair(i, R[i][1]) );
		E[ R[i][1] ].push_back( make_pair(i, R[i][0]) );
	}

	for (int i = 0; i < N; i++){
		DFS(i, G[0], P, -1);
	//	printf("Kontrol\n");
	}
    answer(sonuc);
}

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 6 ms 2808 KB Output is correct
4 Incorrect 4 ms 2680 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 6 ms 2808 KB Output is correct
4 Incorrect 4 ms 2680 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 6 ms 2808 KB Output is correct
4 Incorrect 4 ms 2680 KB Output isn't correct
5 Halted 0 ms 0 KB -