Submission #29408

#	Time	Username	Problem	Language	Result	Execution time	Memory
29408		ozaslan	Tropical Garden (IOI11_garden)	C++14	0 / 100	5 ms	2936 KiB

garden

//#include<bits/stdc++.h>
#include<vector>
#include<map>
#include<set>
#include<stdio.h>
#include "garden.h"
#include "gardenlib.h"
#define MAX_N 100005
#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;
}*/



//int N;
vector< pair<int, int> > E[MAX_N];
//map< pair<int, int>, pair<int, int> > sudoTree;
map< pair<int, int>, vector< pair<int, int> > > donus;
map< pair<int, int>, pair<int, int> >::iterator mapit;
map< pair<int, int>, vector< pair<int, int> > >::iterator mapvit;
set< pair<int, int> > kul;

void sudoDFS(int dugum, int gelenYol, int ata, int ataNo) {

//  printf("Dugum: %d, gelenYol: %d, ata:%d, ataNo:%d, ", dugum, gelenYol, ata, ataNo);
  int enGuzel = oo, dugum1;
  int enGuzel2 = oo, dugum2;

  for(int i = 0; i < E[dugum].size(); i++) {
    int yol = E[dugum][i].first;
    if(yol < enGuzel) {
      enGuzel2 = enGuzel;
      dugum2 = dugum1;
      enGuzel = yol;
      dugum1 = E[dugum][i].second;
    }
    else if(yol < enGuzel2) {
      enGuzel2 = yol;
      dugum2 = E[dugum][i].second;
    }
  }

//  printf("enGuzel: %d\n", enGuzel);
  if (enGuzel == gelenYol) {
 //   sudoTree[ mp(ata, ataNo) ] = mp(dugum, 1);
    donus[ mp(dugum, 1) ].pb( mp(ata, ataNo) );

    if (kul.count( mp(dugum, 1) ) ) return;
    kul.insert( mp(dugum, 1) );

    if (enGuzel2 != oo) sudoDFS(dugum2, enGuzel2, dugum, 1);
    else sudoDFS(ata, gelenYol, dugum, 1);
  }
  else {

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

    if (kul.count( mp(dugum, 0) ) ) return;
    kul.insert( mp(dugum, 0) );

    sudoDFS(dugum1, enGuzel, dugum, 0);
  }
}

void sudoTreeOlustur(int N) {

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

    if(!kul.count(mp(i, 0) ) ) {
      for (int j = 0; j < E[i].size(); j++) {
        int yol = E[i][j].first;
        if (yol < enGuzel) {
          enGuzel = yol;
          dugum = E[i][j].second;
        }
      }


      kul.insert( mp(i, 0) );
      sudoDFS(dugum, enGuzel, i, 0);
    }
  }

 /* for (mapit = sudoTree.begin(); mapit != sudoTree.end(); ++mapit) {
    printf("%d-%d -> %d-%d\n", mapit->first.first, mapit->first.second, mapit->second.first, mapit->second.second);
  }

  for (mapvit = donus.begin(); mapvit != donus.end(); ++mapvit) {
    printf("\n%d-%d -> ", mapvit->first.first, mapvit->first.second);

    for(int i=0; i< mapvit->second.size(); i++)
      printf("%d-%d ", mapvit->second[i].first, mapvit->second[i].second);
  */
}

int uzak1[MAX_N], uzak2[MAX_N], dongu1, dongu2;

void tersDFS1(pair<int, int> dugum, int derinlik) {
//  printf("%d-%d %d\n", dugum.first, dugum.second, derinlik);
  if (dugum.second == 0) uzak1[derinlik]++;
  kul.insert(dugum);

  for(int i = 0; i < donus[dugum].size(); i++) {
    if (kul.count(donus[dugum][i]) ) {
      dongu1 = derinlik +1;
      continue; 
    }

    tersDFS1(donus[dugum][i], derinlik+1);
  }
//    printf("Deneme\n");
}

void tersDFS2(pair<int, int> dugum, int derinlik) {
//  printf("%d-%d %d\n", dugum.first, dugum.second, derinlik);
  if(dugum.second == 0) uzak2[derinlik]++;
  kul.insert(dugum);

  for(int i = 0; i < donus[dugum].size(); i++) {
    if (kul.count(donus[dugum][i]) ) {
      dongu2 = derinlik +1;
      continue; 
    }

    tersDFS2(donus[dugum][i], derinlik+1);
  }
//    printf("Deneme\n");
}

void uzaklikBul(int P) {

  int sonuc = 0;

  kul.clear();
  if (donus.count( mp(P, 0) ) ) tersDFS1( mp(P, 0), 0);

  kul.clear();
  if (donus.count( mp(P, 1) ) ) tersDFS2( mp(P, 1), 0);
}

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

  //N = n;
	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);

  /*for(int i=0; i<MAX_N; i++)
    if(uzak1[i]) printf("%d %d\n", i, uzak1[i]);

  printf("\n");
  for(int i=0; i<MAX_N; i++)
    if(uzak2[i]) printf("%d %d\n", i, uzak2[i]);
*/
  int sonuc;
  for (int i = 0; i < Q; i++) {
    sonuc = 0;
    if (dongu1) sonuc += uzak1[ G[i] % dongu1];
    else sonuc += uzak1[ G[i] ];

    if (dongu2) sonuc += uzak2[ G[i] % dongu2];
    else sonuc += uzak2[ G[i] ];

    answer(sonuc);
  }
}

Compilation message (stderr)

garden.cpp: In function 'void sudoDFS(int, int, int, int)':
garden.cpp:99:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < E[dugum].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~
garden.cpp: In function 'void sudoTreeOlustur(int)':
garden.cpp:143:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j < E[i].size(); j++) {
                       ~~^~~~~~~~~~~~~
garden.cpp: In function 'void tersDFS1(std::pair<int, int>, int)':
garden.cpp:176:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < donus[dugum].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~~~~~
garden.cpp: In function 'void tersDFS2(std::pair<int, int>, int)':
garden.cpp:192:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < donus[dugum].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~~~~~
garden.cpp: In function 'void uzaklikBul(int)':
garden.cpp:205:7: warning: unused variable 'sonuc' [-Wunused-variable]
   int sonuc = 0;
       ^~~~~
garden.cpp: In function 'void sudoDFS(int, int, int, int)':
garden.cpp:132:12: warning: 'dugum1' may be used uninitialized in this function [-Wmaybe-uninitialized]
     sudoDFS(dugum1, enGuzel, dugum, 0);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp: In function 'void sudoTreeOlustur(int)':
garden.cpp:153:14: warning: 'dugum' may be used uninitialized in this function [-Wmaybe-uninitialized]
       sudoDFS(dugum, enGuzel, i, 0);
       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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