oj.uz

Submission #115319

# Submission time Handle Problem Language Result Execution time Memory
115319 2019-06-06T17:19:21 Z model_code Treasure Hunt (CEOI11_tre) C++14
20 / 100
 4000 ms 262148 KB 
/* Slow solution to the task Treasure hunt
 * Author: Jakub Radoszewski
 * Date: 9.06.2011
 * Time complexity: O(#nodes * #dig).
 * Description: DFS algorithm.
 */


#include <utility>
#include <vector>
#include <algorithm>

using namespace std;


#define INFTY 100000000

/* This node will be created if a path call appears */
int curr;
vector<vector<int> > edges;

inline void add_edge(int a, int b)
{
  edges[a].push_back(b);
  edges[b].push_back(a);
}


/*****************************************************************************/

void init()
{
  edges.push_back(vector<int>()); /* node 0 */
  edges.push_back(vector<int>()); /* node 1 */
  curr = 2;
}


/*****************************************************************************/

void path(int a, int s)
{
  int pop = a;
  for (int i = 0; i < s; i++)
  {
    edges.push_back(vector<int>()); /* node curr */
    add_edge(curr, pop);
    pop = curr;
    curr++;
  }
}


/*****************************************************************************/

int dig(int a, int b)
{
  vector<int> d, parent;
  d.resize(curr, INFTY);
  parent.resize(curr, -1);

  vector<int> queue;
  d[a] = 0;
  queue.push_back(a);
  for (int i = 0; i < (int)queue.size(); i++)
  {
    int v = queue[i];
    for (int j = 0; j < (int)edges[v].size(); j++)
    {
      int w = edges[v][j];
      if (d[w] == INFTY)
      {
        d[w] = d[v] + 1;
        parent[w] = v;
        queue.push_back(w);
        if (w == b)
        {
          /* recovering the path */
          int len = (d[w] + 1) / 2;
          while (len--)
            w = parent[w];
          return w;
        }
      }
    }
  }
  return -1;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 504 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 888 KB Output is correct
2 Correct 203 ms 924 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4010 ms 8224 KB Time limit exceeded

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4054 ms 5152 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4078 ms 4764 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 814 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3921 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 664 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 660 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 667 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)