oj.uz

Submission #852877

# Submission time Handle Problem Language Result Execution time Memory
852877 2023-09-23T03:22:14 Z 12345678 Werewolf (IOI18_werewolf) C++17
0 / 100
 134 ms 30816 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=3e3+5;
int dsu[nx];
vector<tuple<int, int, int>> dmn, dmx;

int find(int x)
{
  if (dsu[x]==x) return x;
  return dsu[x]=find(dsu[x]);
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
  for (int i=0; i<X.size(); i++) dmn.push_back({max(X[i], Y[i]), X[i], Y[i]}), dmx.push_back({min(X[i], Y[i]), X[i], Y[i]});
  sort(dmn.begin(), dmn.end());
  sort(dmx.begin(), dmx.end());
  reverse(dmx.begin(), dmx.end());
  int Q = S.size();
  vector<int> A(Q);
  for (int i=0; i<Q; i++)
  {
    for (int j=0; j<N; j++) dsu[j]=j;
    for (int j=0; j<dmx.size(); j++)
    {
      auto [w, u, v]=dmx[j];
      if (w<L[i]) break;
      int pu=find(u), pv=find(v);
      if (pu!=pv) dsu[pu]=pv;
    }
    for (int j=0; j<dmn.size(); j++)
    {
      auto [w, u, v]=dmn[j];
      if (w>R[i]) break;
      int pu=find(u), pv=find(v);
      if (pu!=pv) dsu[pu]=pv;
    }
    A[i]=find(S[i])==find(E[i]);
  }
  return A;
}

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:19:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   for (int i=0; i<X.size(); i++) dmn.push_back({max(X[i], Y[i]), X[i], Y[i]}), dmx.push_back({min(X[i], Y[i]), X[i], Y[i]});
      |                 ~^~~~~~~~~
werewolf.cpp:28:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int j=0; j<dmx.size(); j++)
      |                   ~^~~~~~~~~~~
werewolf.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int j=0; j<dmn.size(); j++)
      |                   ~^~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 348 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 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 134 ms 30816 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

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