Submission #168691

#	Time	Username	Problem	Language	Result	Execution time	Memory
168691		AlexLuchianov	Werewolf (IOI18_werewolf)	C++14	34 / 100	817 ms	70776 KiB

werewolf

#include "werewolf.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <cassert>

int const nmax = 400000;

namespace Tree{
  int level[1 + nmax];
  std::vector<int> g[1 + nmax];
  void addEdge(int x, int y){
    g[x].push_back(y);
    g[y].push_back(x);
  }
  void dfs(int node, int parent, int acc){
    level[node] = acc;
    for(int h = 0; h < g[node].size(); h++){
      int to = g[node][h];
      if(to != parent)
        dfs(to, node, acc + 1);
    }
  }
}

namespace Dsu{
  std::vector<int> mult;
  std::vector<int> sz;
  std::vector<int> marker;///marker is the marker with the minimal level

  void initialize(int n){
    mult.resize(n);
    sz.resize(n);
    marker.resize(n);
    for(int i = 0;i < n; i++) {
      mult[i] = marker[i] = i;
      sz[i] = 1;
    }
  }
  int jump(int x){
    if(x != mult[x])
      mult[x] = jump(mult[x]);
    return mult[x];
  }
  void unite(int gala, int galb){
    gala = jump(gala);
    galb = jump(galb);
    if(sz[galb] < sz[gala])
      std::swap(gala, galb);

    if(gala != galb){
      mult[gala] = galb;
      sz[galb] += sz[gala];
      sz[gala] = 0;
      //assert(Tree::level[marker[gala]] != Tree::level[marker[galb]]);
      if(Tree::level[marker[gala]] < Tree::level[marker[galb]])
        marker[galb] = marker[gala];
    }
  }
}

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) {
  std::vector<int> sol(S.size());
  Dsu::initialize(N);
  std::vector<std::vector<int>> initialgraph(N);

  for(int i = 0; i < X.size(); i++) {
    initialgraph[X[i]].push_back(Y[i]);
    initialgraph[Y[i]].push_back(X[i]);
  }

  for(int i = 0; i < N; i++){
    std::sort(initialgraph[i].begin(), initialgraph[i].end());
    std::reverse(initialgraph[i].begin(), initialgraph[i].end());
    for(int h = 0; h < initialgraph[i].size(); h++){
      int x = i, y = initialgraph[i][h];

      if(y <= i){
        if(Dsu::jump(x) != Dsu::jump(y)) {
          Tree::addEdge(x, y);
          Dsu::unite(x, y);
        }
      }
    }
  }

  Tree::dfs(0, -1, 1);
  Dsu::initialize(N);
  int Q = S.size();
  std::vector<std::vector<int>> queryl(N), queryr(N);
  std::vector<int> repl(Q), repr(Q);

  for(int i = 0; i < Q; i++){
    queryl[L[i]].push_back(i);
    queryr[R[i]].push_back(i);
  }

  for(int i = N - 1;0 <= i; i--){
    for(int h = 0; h < Tree::g[i].size(); h++){
      int to = Tree::g[i][h];
      if(i <= to)
        Dsu::unite(i, to);
    }
    for(int h = 0; h < queryl[i].size(); h++){
      int id = queryl[i][h];
      repl[id] = Dsu::marker[Dsu::jump(S[id])];
    }
  }

  //return sol;

  Dsu::initialize(N);
  for(int i = 0; i < N; i++){
    for(int h = 0; h < Tree::g[i].size(); h++){
      int to = Tree::g[i][h];
      if(to <= i)
        Dsu::unite(i, to);
    }
    for(int h = 0; h < queryr[i].size(); h++){
      int id = queryr[i][h];
      repr[id] = Dsu::marker[Dsu::jump(E[id])];
    }
  }

  Dsu::initialize(N);

  for(int i = N - 1;0 <= i; i--){
    for(int h = 0; h < Tree::g[i].size(); h++){
      int to = Tree::g[i][h];
      if(i <= to)
        Dsu::unite(i, to);
    }
    for(int h = 0; h < queryl[i].size(); h++){
      int id = queryl[i][h];
      sol[id] |= (Dsu::jump(S[id]) == Dsu::jump(repr[id]));
    }
  }
  Dsu::initialize(N);

  for(int i = 0; i < N; i++){
    for(int h = 0; h < Tree::g[i].size(); h++){
      int to = Tree::g[i][h];
      if(to <= i)
        Dsu::unite(i, to);
    }
    for(int h = 0; h < queryr[i].size(); h++){
      int id = queryr[i][h];
      sol[id] |= (Dsu::jump(E[id]) == Dsu::jump(repl[id]));
    }
  }

  return sol;
}

Compilation message (stderr)

werewolf.cpp: In function 'void Tree::dfs(int, int, int)':
werewolf.cpp:18:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[node].size(); h++){
                    ~~^~~~~~~~~~~~~~~~
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:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < X.size(); i++) {
                  ~~^~~~~~~~~~
werewolf.cpp:77:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < initialgraph[i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:101:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < Tree::g[i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~~
werewolf.cpp:106:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < queryl[i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~
werewolf.cpp:116:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < Tree::g[i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~~
werewolf.cpp:121:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < queryr[i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~
werewolf.cpp:130:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < Tree::g[i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~~
werewolf.cpp:135:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < queryl[i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~
werewolf.cpp:143:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < Tree::g[i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~~
werewolf.cpp:148:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < queryr[i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51