oj.uz

Submission #825472

# Submission time Handle Problem Language Result Execution time Memory
825472 2023-08-14T22:00:57 Z thimote75 Werewolf (IOI18_werewolf) C++14
0 / 100
 4000 ms 33680 KB 
#include "werewolf.h"

#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;

struct Road {
  int x, y;

  Road (int _x, int _y) {
    x = min(_x, _y);
    y = max(_x, _y);
  }
};

using t_Roads = vector<Road>;
using t_Graph = vector<t_Roads>;

t_Graph roads;
idata visited; int stage = 0;

bool dfs (int source, int target, int left, int right) {
    if (source == target) return true;

    if (visited[source] == stage) return false;
    visited[source] = stage;

    for (Road &road : roads[source]) {
        int next = road.x == source ? road.y : road.x;

        if (road.x < left && right < road.y) continue ;
        
        if (dfs(next, target, left, right))
            return true;
    }

    return false;
}

idata check_validity(int N, idata X, idata Y,
                            idata S, idata E,
                            idata L, idata R) {
  int M = X.size(); int Q = S.size();

  roads.resize(N);

  for (int i = 0; i < M; i ++) {
    Road road (X[i], Y[i]);

    roads[road.x].push_back(road);
    roads[road.y].push_back(road);
  }

  idata A(Q);
  visited.resize(N);

  for (int i = 0; i < Q; i ++) {
    stage ++;
    A[i] = dfs(S[i], E[i], L[i], R[i]);
  }

  return A;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -