제출 #79924

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
79924		antimirage	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	0 / 100	3 ms	376 KiB

garden

#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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31