oj.uz

Submission #825475

# Submission time Handle Problem Language Result Execution time Memory
825475 2023-08-14T22:11:48 Z thimote75 Werewolf (IOI18_werewolf) C++14
0 / 100
 4000 ms 38556 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);
  }

  int next (int a) {
    return x == a ? y : x;
  }

  bool operator< (const Road &other) {
    if (x == other.x)
      return y < other.y;
    return x > other.x;
  }
};

struct UFD {
  idata parents;

  UFD (int size) {
    parents.resize(size);
    iota(parents.begin(), parents.end(), 0);
  }
  int boss (int x) {
    if (parents[x] != x)
      parents[x] = boss(parents[x]);
    return parents[x];
  }
  bool merge (int a, int b) {
    a = boss(a); b = boss(b);
    if (a == b) return false;

    parents[a] = b;
    return true;
  }
};

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

t_Graph roads;

int dfs (int source, int target, int parent, int left, int vdepth) {
  if (source == target) return vdepth;

  int res = 0;
  for (Road &road : roads[source]) {
    int next = road.next(source);
    if (next == parent) continue ;

    int cost = (road.x >= left ? 0 : road.y);
    res = max(
      res, 
      dfs(next, target, source, left, max(vdepth, cost))
    );
  }

  return res;
}

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();
  
  t_Roads road_array;
  for (int i = 0; i < M; i ++)
    road_array.push_back(Road(X[i], Y[i]));
  
  sort(road_array.begin(), road_array.end());
  roads.resize(N);

  UFD ufd(N);
  for (Road &road : road_array) {
    if (!ufd.merge(road.x, road.y)) continue ;

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

  idata A(Q);
  //return A;
  for (int i = 0; i < Q; i ++)
    A[i] = dfs(S[i], E[i], -1, L[i], 0) <= R[i] ? 1 : 0;

  return A;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

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