oj.uz

Submission #79924

# Submission time Handle Problem Language Result Execution time Memory
79924 2018-10-17T10:46:34 Z antimirage Tropical Garden (IOI11_garden) C++17
0 / 100
 3 ms 376 KB 
#include "garden.h"
#include "gardenlib.h"
//#include "grader.cpp"

#include <bits/stdc++.h>

#define fr first
#define sc second
#define mk make_pair
#define pb emplace_back
#define all(s) s.begin(), s.end()

using namespace std;

const int sz = 1005;

vector < vector < pair <int, int> > > g;

int u[sz];

bool fl;

void dfs (int v, int k, int en)
{
      u[v] = 1;
      if (k == 0){
            if (v == en) fl = 1;
            return;
      }
      pair <int, int> mn = mk(1e9, 1e9);

      for (auto to : g[v])
      {
            if (u[to.fr]) continue;
            mn = min( mn, mk( to.sc, to.fr ) );
      }
      if (mn.fr < 1e9)
            dfs(mn.sc, k - 1, en);
      else
      {
            for (auto to : g[v])
                  mn = min( mn, mk( to.sc, to.fr ) );

            if (mn.fr < 1e9)
                  dfs(mn.sc, k - 1, en);
      }
}

bool check (int st, int k, int en)
{
      memset(u, 0, sizeof(u));

      fl = false;
      dfs( st, k, en );

      return fl;
}

void count_routes(int n, int m, int p, int edges[][2], int q, int k[])
{
      g.resize(n);
      for (int i = 0; i < m; i++)
      {
            g[ edges[i][0] ].pb( mk( edges[i][1], i) );
            g[ edges[i][1] ].pb( mk( edges[i][0], i) );
      }
      for (int i = 0; i < q; i++)
      {
            int ans = 0;

            for (int j = 0; j < n; j++)
            {
                  if ( check( j, k[i], p ) )
                  {
                        ans++;
                  }
            }
            answer(ans);
      }
}
/**
6 6 0
1 2
0 1
0 3
3 4
4 5
1 5
1
3
2


5 5 2
1 0
1 2
3 2
1 3
4 2
2
3 1
1 2

**/

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -