oj.uz

Submission #29485

# Submission time Handle Problem Language Result Execution time Memory
29485 2017-07-19T13:12:04 Z ozaslan Tropical Garden (IOI11_garden) C++14
49 / 100
 76 ms 28792 KB 
#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, 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

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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8284 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct
3 Correct 9 ms 8284 KB Output is correct
4 Correct 9 ms 8184 KB Output is correct
5 Correct 10 ms 8184 KB Output is correct
6 Correct 10 ms 8312 KB Output is correct
7 Correct 9 ms 8204 KB Output is correct
8 Correct 11 ms 8268 KB Output is correct
9 Correct 12 ms 8472 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8284 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct
3 Correct 9 ms 8284 KB Output is correct
4 Correct 9 ms 8184 KB Output is correct
5 Correct 10 ms 8184 KB Output is correct
6 Correct 10 ms 8312 KB Output is correct
7 Correct 9 ms 8204 KB Output is correct
8 Correct 11 ms 8268 KB Output is correct
9 Correct 12 ms 8472 KB Output is correct
10 Correct 9 ms 8184 KB Output is correct
11 Correct 23 ms 10488 KB Output is correct
12 Correct 42 ms 11640 KB Output is correct
13 Correct 71 ms 28792 KB Output is correct
14 Runtime error 76 ms 24760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8284 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct
3 Correct 9 ms 8284 KB Output is correct
4 Correct 9 ms 8184 KB Output is correct
5 Correct 10 ms 8184 KB Output is correct
6 Correct 10 ms 8312 KB Output is correct
7 Correct 9 ms 8204 KB Output is correct
8 Correct 11 ms 8268 KB Output is correct
9 Correct 12 ms 8472 KB Output is correct
10 Correct 9 ms 8184 KB Output is correct
11 Correct 23 ms 10488 KB Output is correct
12 Correct 42 ms 11640 KB Output is correct
13 Correct 71 ms 28792 KB Output is correct
14 Runtime error 76 ms 24760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -