Submission #117048

#	Time	Username	Problem	Language	Result	Execution time	Memory
117048		mirbek01	Werewolf (IOI18_werewolf)	C++11	0 / 100	1263 ms	80084 KiB

werewolf

# include <bits/stdc++.h>
# include "werewolf.h"

using namespace std;

const int maxn = 2e5 + 2;

int p[2][maxn], timer, tin[3][maxn], tout[3][maxn], up[3][19][maxn], pos[maxn], fen[maxn];
vector <int> g[3][maxn];

int f_s(int tp, int v){
      return p[tp][v] == v?v:p[tp][v] = f_s(tp, p[tp][v]);
}

void dfs(int tp, int v, int pr){
      tin[tp][v] = ++ timer;
      up[tp][0][v] = pr;
      for(int i = 1; i <= 18; i ++)
            up[tp][i][v] = up[tp][i - 1][ up[tp][i - 1][v] ];
      for(int to : g[tp][v]){
            if(to == pr)
                  continue;
            dfs(tp, to, v);
      }
      tout[tp][v] = timer;
}

void upd(int pos){
      for(; pos < maxn; pos |= pos + 1)
            fen[pos] ++;
}

int get(int r){
      int ret = 0;
      for(; r > 0; r = (r & (r + 1)) - 1)
            ret += fen[r];
      return ret;
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
      int Q = S.size(), M = X.size();
      vector<int> A(Q);

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

      for(int i = 0; i < N; i ++)
            p[0][i] = p[1][i] = i;

      for(int i = N - 1; i >= 0; i --){
            for(int to : g[0][i]){
                  if(to < i || f_s(0, i) == f_s(0, to))
                        continue;
                  int a = f_s(0, i), b = f_s(0, to);
                  g[1][a].push_back(b);
                  p[0][b] = a;
            }
      }

      for(int i = 0; i < N; i ++){
            for(int to : g[0][i]){
                  if(to > i || f_s(1, i) == f_s(1, to))
                        continue;
                  int a = f_s(1, i), b = f_s(1, to);
                  g[2][a].push_back(b);
                  p[1][b] = a;
            }
      }

      dfs(1, f_s(0, 0), f_s(0, 0));
      timer = 0;
      dfs(2, f_s(1, 0), f_s(1, 0));

      vector < pair <int, pair <int, int> > > qe;

      for(int i = 0; i < Q; i ++){
            int s = S[i], e = E[i], l = L[i], r = R[i];
            for(int j = 18; j >= 0; j --){
                  if(up[1][j][s] >= l)
                        s = up[1][j][s];
            }
            for(int j = 18; j >= 0; j --){
                  if(up[2][j][e] <= r)
                        e = up[2][j][e];
            }
            qe.push_back({tin[1][s] - 1, {-(i + 1), e}});
            qe.push_back({tout[1][s], {i + 1, e}});
      }

      sort(qe.begin(), qe.end());

      for(int i = 0; i < N; i ++)
            pos[ tin[1][i] - 1 ] = tin[2][i];

      int pt = 0;

      for(int i = 0; i < qe.size(); i ++){
            int p = qe[i].first, id = qe[i].second.first, v = qe[i].second.second;
            while(pt < p)
                  upd(pos[pt ++]);
            if(id < 0)
                  A[abs(id) - 1] -= get(tout[2][v]) - get(tin[2][v]);
            else
                  A[abs(id) - 1] += get(tout[2][v]) - get(tin[2][v]);
      }

      for(int i = 0; i < Q; i ++)
            A[i] = (A[i] > 0);

      return A;
}

Compilation message (stderr)

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:99:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < qe.size(); i ++){
                      ~~^~~~~~~~~~~

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