oj.uz

Submission #29486

# Submission time Handle Problem Language Result Execution time Memory
29486 2017-07-19T13:13:30 Z ozaslan Tropical Garden (IOI11_garden) C++14
100 / 100
 4529 ms 39128 KB 
#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

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 27 ms 12120 KB Output is correct
2 Correct 13 ms 12152 KB Output is correct
3 Correct 27 ms 12196 KB Output is correct
4 Correct 16 ms 12024 KB Output is correct
5 Correct 19 ms 12152 KB Output is correct
6 Correct 12 ms 12280 KB Output is correct
7 Correct 13 ms 12028 KB Output is correct
8 Correct 30 ms 12128 KB Output is correct
9 Correct 16 ms 12408 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 12120 KB Output is correct
2 Correct 13 ms 12152 KB Output is correct
3 Correct 27 ms 12196 KB Output is correct
4 Correct 16 ms 12024 KB Output is correct
5 Correct 19 ms 12152 KB Output is correct
6 Correct 12 ms 12280 KB Output is correct
7 Correct 13 ms 12028 KB Output is correct
8 Correct 30 ms 12128 KB Output is correct
9 Correct 16 ms 12408 KB Output is correct
10 Correct 13 ms 12024 KB Output is correct
11 Correct 26 ms 14328 KB Output is correct
12 Correct 58 ms 15648 KB Output is correct
13 Correct 78 ms 32764 KB Output is correct
14 Correct 180 ms 22288 KB Output is correct
15 Correct 214 ms 23212 KB Output is correct
16 Correct 132 ms 20212 KB Output is correct
17 Correct 145 ms 19968 KB Output is correct
18 Correct 46 ms 15352 KB Output is correct
19 Correct 146 ms 22908 KB Output is correct
20 Correct 165 ms 23316 KB Output is correct
21 Correct 140 ms 20484 KB Output is correct
22 Correct 137 ms 20584 KB Output is correct
23 Correct 151 ms 23520 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 12120 KB Output is correct
2 Correct 13 ms 12152 KB Output is correct
3 Correct 27 ms 12196 KB Output is correct
4 Correct 16 ms 12024 KB Output is correct
5 Correct 19 ms 12152 KB Output is correct
6 Correct 12 ms 12280 KB Output is correct
7 Correct 13 ms 12028 KB Output is correct
8 Correct 30 ms 12128 KB Output is correct
9 Correct 16 ms 12408 KB Output is correct
10 Correct 13 ms 12024 KB Output is correct
11 Correct 26 ms 14328 KB Output is correct
12 Correct 58 ms 15648 KB Output is correct
13 Correct 78 ms 32764 KB Output is correct
14 Correct 180 ms 22288 KB Output is correct
15 Correct 214 ms 23212 KB Output is correct
16 Correct 132 ms 20212 KB Output is correct
17 Correct 145 ms 19968 KB Output is correct
18 Correct 46 ms 15352 KB Output is correct
19 Correct 146 ms 22908 KB Output is correct
20 Correct 165 ms 23316 KB Output is correct
21 Correct 140 ms 20484 KB Output is correct
22 Correct 137 ms 20584 KB Output is correct
23 Correct 151 ms 23520 KB Output is correct
24 Correct 14 ms 12152 KB Output is correct
25 Correct 150 ms 14384 KB Output is correct
26 Correct 183 ms 15716 KB Output is correct
27 Correct 3072 ms 32824 KB Output is correct
28 Correct 1660 ms 23060 KB Output is correct
29 Correct 3244 ms 23272 KB Output is correct
30 Correct 1934 ms 21388 KB Output is correct
31 Correct 1862 ms 20948 KB Output is correct
32 Correct 181 ms 15992 KB Output is correct
33 Correct 1674 ms 24044 KB Output is correct
34 Correct 3135 ms 24484 KB Output is correct
35 Correct 1926 ms 21932 KB Output is correct
36 Correct 2493 ms 21740 KB Output is correct
37 Correct 1144 ms 24728 KB Output is correct
38 Correct 4529 ms 39128 KB Output is correct