Submission #85654

#	Time	Username	Problem	Language	Result	Execution time	Memory
85654		mirbek01	Tropical Garden (IOI11_garden)	C++17	0 / 100	38 ms	3548 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 2;

int k, ans, p, cnt[MAXN], used[MAXN], fl;
vector < pair <int, int> > g[MAXN];

void dfs(int v){
      if(fl) return ;
      if(cnt[v] == k){
            fl = 1;
            if(v == p)
                  ans ++;
            return ;
      }
      used[v] = 1;
      for(int i = 0; i < g[v].size(); i ++){
            int to = g[v][i].second;
            if(used[to]) continue;
            cnt[to] = cnt[v] + 1;
            dfs(to);
            cnt[v] = cnt[to] + 1;
            if(cnt[v] == k){
                  fl = 1;
                  if(v == p)
                        ans ++;
                  return ;
            }
      }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
      for(int i = 0; i < M; i ++){
            int u = R[i][0], v = R[i][1];
        	if(g[u].size() < 2)
            g[u].push_back({i, v});
        	if(g[v].size() < 2)
            g[v].push_back({i, u});
      }
      for(int i = 0; i < N; i ++)
            sort(g[i].begin(), g[i].end());
      p = P;
      for(int i = 0; i < Q; i ++){
            k = G[i];
            ans = 0;
            for(int i = 0; i < N; i ++){
                  memset(cnt, 0, sizeof(cnt));
                  memset(used, 0, sizeof(used));
                  fl = 0;
                  dfs(i);
            }
            answer(ans);
      }
}

Compilation message (stderr)

garden.cpp: In function 'void dfs(int)':
garden.cpp:21:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < g[v].size(); i ++){
                      ~~^~~~~~~~~~~~~

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