Submission #29486

#	Time	Username	Problem	Language	Result	Execution time	Memory
29486		ozaslan	Tropical Garden (IOI11_garden)	C++14	100 / 100	4529 ms	39128 KiB

garden

#include<bits/stdc++.h>
#include<vector>
#include<map>
#include<set>
#include<stdio.h>
#include "garden.h"
#include "gardenlib.h"
#define MAX_N 150005
#define mp make_pair
#define pb push_back
#define oo (1<<28)
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> > donus[MAX_N][2];
map< pair<int, int>, pair<int, int> >::iterator mapit;
int kul[MAX_N][2], dongu1, dongu2;
int uzak1[MAX_N], uzak2[MAX_N], gec1[MAX_N], gec2[MAX_N];

void sudoDFS(int dugum, int ata, int ataNo) {
  int enGuzel = E[dugum][0].second;
  int enGuzel2 = E[dugum].size() == 1 ? E[dugum][0].second : E[dugum][1].second;


  if (enGuzel == ata) {
    donus[dugum][1].pb( mp(ata, ataNo) );

    if (kul[dugum][1]) return;
    kul[dugum][1] = 1;

    sudoDFS(enGuzel2, dugum, 1);
  }
  else {

    donus[dugum][0].pb( mp(ata, ataNo) );

    if (kul[dugum][0]) return;
    kul[dugum][0] = 1;

    sudoDFS(enGuzel, dugum, 0);
  }
}

void sudoTreeOlustur(int N) {

  for(int i = 0; i < N; i++) {
    int enGuzel = oo, dugum;

    if(kul[i][0]) continue;
    kul[i][0] = 1;

    sudoDFS(E[i][0].second, i, 0);
  }
}

void tersDFS1(int dugum, int dugumNo, int derinlik) {
  if (dugumNo == 0) uzak1[dugum] = derinlik, gec1[dugum] = 1;
  kul[dugum][dugumNo] = 1;
  

  for(int i = 0; i < donus[dugum][dugumNo].size(); i++) {
    int v = donus[dugum][dugumNo][i].first, m = donus[dugum][dugumNo][i].second;

    if (kul[v][m]) {
      dongu1 = derinlik +1;
      continue; 
    }

    tersDFS1(v, m, derinlik+1);
  }
}

void tersDFS2(int dugum, int dugumNo, int derinlik) {
  if(dugumNo == 0) uzak2[dugum] = derinlik,gec2[dugum] = 1;
  kul[dugum][dugumNo] = 1;
  

  for(int i = 0; i < donus[dugum][dugumNo].size(); i++) {
    int v = donus[dugum][dugumNo][i].first, m = donus[dugum][dugumNo][i].second;

    if (kul[v][m] ) {
      dongu2 = derinlik +1;
      continue; 
    }

    tersDFS2(v, m, derinlik+1);
  }
}

void uzaklikBul(int P) {

  memset(kul, 0, sizeof kul);  
  tersDFS1( P, 0, 0);

  memset(kul, 0, sizeof kul);
  tersDFS2( P, 1, 0);
}

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]) );
	}

  sudoTreeOlustur(N);
  uzaklikBul(P);

  int sonuc;
  for (int i = 0; i < Q; i++) {
    sonuc = 0;
    for(int j = 0; j < N; j++) {
      if(gec1[j] && uzak1[j] <= G[i]) {
        if(dongu1 && uzak1[j] % dongu1 == G[i] % dongu1) sonuc++;
        else if(G[i] == uzak1[j]) sonuc++; 
      }

      if(gec2[j] && uzak2[j] <= G[i]) {
        if(dongu2 && uzak2[j] % dongu2 == G[i] % dongu2) sonuc++;
        else if(G[i] == uzak2[j]) sonuc++; 
      }
    }

    answer(sonuc);
  }
}

Compilation message (stderr)

garden.cpp: In function 'void sudoTreeOlustur(int)':
garden.cpp:115:9: warning: unused variable 'enGuzel' [-Wunused-variable]
     int enGuzel = oo, dugum;
         ^~~~~~~
garden.cpp:115:23: warning: unused variable 'dugum' [-Wunused-variable]
     int enGuzel = oo, dugum;
                       ^~~~~
garden.cpp: In function 'void tersDFS1(int, int, int)':
garden.cpp:129:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < donus[dugum][dugumNo].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp: In function 'void tersDFS2(int, int, int)':
garden.cpp:146:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < donus[dugum][dugumNo].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31