oj.uz

Submission #1074185

# Submission time Handle Problem Language Result Execution time Memory
1074185 2024-08-25T08:39:48 Z mindiyak Tropical Garden (IOI11_garden) C++17
49 / 100
 5000 ms 6236 KB 
#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

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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 3 ms 5164 KB Output is correct
4 Correct 2 ms 5160 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 5264 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 4 ms 5468 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 3 ms 5164 KB Output is correct
4 Correct 2 ms 5160 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 5264 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 4 ms 5468 KB Output is correct
10 Correct 6 ms 5096 KB Output is correct
11 Execution timed out 5047 ms 6236 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 3 ms 5164 KB Output is correct
4 Correct 2 ms 5160 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 5264 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 4 ms 5468 KB Output is correct
10 Correct 6 ms 5096 KB Output is correct
11 Execution timed out 5047 ms 6236 KB Time limit exceeded
12 Halted 0 ms 0 KB -