제출 #29478

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
29478		ozaslan	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	0 / 100	10 ms	8232 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;
}*/



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;
  kul[dugum][dugumNo] = 1;
  gec1[dugum] = 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;
  kul[dugum][dugumNo] = 1;
  gec2[dugum] = 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) {

  int sonuc = 0;

  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[j] % dongu1) sonuc++;
        else if(G[i] == uzak1[j]) sonuc++; 
      }

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

    answer(sonuc);
  }
}

  /*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]);
*/

 /* 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);
  */

컴파일 시 표준 에러 (stderr) 메시지

garden.cpp: In function 'void sudoTreeOlustur(int)':
garden.cpp:118:9: warning: unused variable 'enGuzel' [-Wunused-variable]
     int enGuzel = oo, dugum;
         ^~~~~~~
garden.cpp:118:23: warning: unused variable 'dugum' [-Wunused-variable]
     int enGuzel = oo, dugum;
                       ^~~~~
garden.cpp: In function 'void tersDFS1(int, int, int)':
garden.cpp:134: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:151: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 uzaklikBul(int)':
garden.cpp:165:7: warning: unused variable 'sonuc' [-Wunused-variable]
   int sonuc = 0;
       ^~~~~

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