Submission #1074185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074185		mindiyak	Tropical Garden (IOI11_garden)	C++17	49 / 100	5047 ms	6236 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <iostream>
#include <vector>

using namespace std;

#define F first
#define S second

int cnt = 0, g = 0, p = 0;

vector<vector<pair<int,int>>> paths(2e5);

void dfs(int pos,int dis,int prev){
  // cerr << pos << " " << dis << " " << prev << endl;
  if(dis>g)return;
  if(dis==g){
    if(pos==p)cnt++;
    return;
  }
  int cur = -1,val = 1e9;
  for(int i=0;i<paths[pos].size();i++){
    auto node = paths[pos][i];
    if(node.F == prev)continue;
    if(node.S < val)cur = node.F;
    val = min(val,node.S);
  }

  if(cur == -1)dfs(prev,dis+1,pos);
  else dfs(cur,dis+1,pos);
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
  for(int i=0;i<M;i++){
    paths[R[i][0]].push_back({R[i][1],i});
    paths[R[i][1]].push_back({R[i][0],i});
  }
  p = P;

  for(int k=0;k<Q;k++){
    cnt = 0;
    g = G[k];
    for(int i=0;i<N;i++){
      dfs(i,0,i);
    } 
    // cerr << "ans " << k << " " << cnt << endl;
    answer(cnt);
  }
}

Compilation message (stderr)

garden.cpp: In function 'void dfs(int, int, int)':
garden.cpp:23:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   for(int i=0;i<paths[pos].size();i++){
      |               ~^~~~~~~~~~~~~~~~~~

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