oj.uz

Submission #28806

# Submission time Handle Problem Language Result Execution time Memory
28806 2017-07-17T08:40:03 Z kavun Tropical Garden (IOI11_garden) C++14
49 / 100
 11 ms 1272 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;
vector <pair<int,int> > adj[2000];

int dfs(int v, int d, int k, int par)
{
    if(d == k)
        return v;

    if(adj[v].size() == 1)
        return dfs(adj[v][0].first,d+1,k,v);
    else
    {
        int mx = 0;
        int mxver;
        for(int i = 0; i < adj[v].size(); i++)
        {
            int u = adj[v][i].first;
            int bt = adj[v][i].second;
            if(u != par)
            {
                if(bt > mx)
                {
                    mx = bt;
                    mxver = u;
                }
            }
        }
        return dfs(mxver,d+1,k,v);
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
  for(int i = 0; i < M; i++)
  {
      int v = R[i][0], u = R[i][1], beauty = M - i;
      adj[v].push_back(make_pair(u,beauty));
      adj[u].push_back(make_pair(v,beauty));
  }
  int res = 0;
  for(int i = 0; i < N; i++)
  {
      if(dfs(i,0,G[0],-1) == P)
        res++;
  }

  for(int i=0; i<Q; i++)
    answer(res);
}

Compilation message

garden.cpp: In function 'int dfs(int, int, int, int)':
garden.cpp:19:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < adj[v].size(); i++)
                        ~~^~~~~~~~~~~~~~~
garden.cpp:8:13: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
 int dfs(int v, int d, int k, int par)
             ^

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 8 ms 604 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 8 ms 604 KB Output is correct
10 Correct 8 ms 376 KB Output is correct
11 Runtime error 11 ms 1272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 8 ms 604 KB Output is correct
10 Correct 8 ms 376 KB Output is correct
11 Runtime error 11 ms 1272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -