Submission #116295

#	Time	Username	Problem	Language	Result	Execution time	Memory
116295		mirbek01	Werewolf (IOI18_werewolf)	C++11	49 / 100	1086 ms	66732 KiB

werewolf

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

using namespace std;

const int N = 4e5 + 2;

int ver[N], pos[N], n, t[2][18][N], lg[N];
vector <int> g[N];

int get(int l, int r, int tp){
      int curlog = lg[r - l + 1];
      if(tp)
            return max(t[1][curlog][l], t[1][curlog][r - (1 << curlog) + 1]);
      else
            return min(t[0][curlog][l], t[0][curlog][r - (1 << curlog) + 1]);
}

void dfs(int v, int par = -1){
      ver[++ n] = v;
      for(int to : g[v]){
            if(to == par)
                  continue;
            dfs(to, v);
      }
}
int used[N], d[N];

void dfs(int v, int tp, int x){
      used[v] = 1;
      d[v] ++;
      for(int to : g[v]){
            if(used[to])
                  continue;
            if(tp == 1){
                  if(to < x)
                        continue;
                  dfs(to, tp, x);
            } else {
                  if(to > x)
                        continue;
                  dfs(to, tp, x);
            }
      }
}

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();
      int m = X.size();
      vector <int> A(q);

      for(int i = 0; i < m; i ++){
            g[X[i]].push_back(Y[i]);
            g[Y[i]].push_back(X[i]);
      }
      if(N <= 3000 && X.size() <= 6000 && S.size() <= 3000){
            for(int i = 0; i < q; i ++){
                  dfs(S[i], 1, L[i]);
                  for(int j = 0; j < N; j ++)
                        used[j] = 0;
                  dfs(E[i], 2, R[i]);
                  for(int j = 0; j < N; j ++){
                        if(d[j] == 2)
                              A[i] = 1;
                        used[j] = 0, d[j] = 0;
                  }
            }
      } else {
            for(int i = 0; i < N; i ++){
                  if(g[i].size() == 1){
                        dfs(i);
                        break;
                  }
            }

            for(int i = 1; i <= n; i ++){
                  pos[ver[i]] = i;
            }

            for(int i = 2; i <= n; i ++)
                  lg[i] = lg[i / 2] + 1;

            for(int i = 0; i <= lg[n]; i ++){
                  if(!i){
                        for(int j = 1; j <= n; j ++)
                              t[0][i][j] = ver[j],
                              t[1][i][j] = ver[j];
                  } else {
                        int curlen = 1 << (i - 1);
                        for(int j = 1; j <= n; j ++){
                              t[0][i][j] = min(t[0][i - 1][j], t[0][i - 1][min(n, j + curlen)]),
                              t[1][i][j] = max(t[1][i - 1][j], t[1][i - 1][min(n, j + curlen)]);
                        }
                  }
            }

            for(int i = 0; i < q; i ++){
                  int l1, l2, r1, r2;
                  l1 = pos[S[i]], r1 = pos[S[i]];
                  l2 = pos[E[i]], r2 = pos[E[i]];
                  int lo = 1, hi = l1, ret = l1;
                  while(lo <= hi){
                        int md = (lo + hi) >> 1;
                        if(get(md, l1, 0) >= L[i])
                              hi = md - 1, ret = md;
                        else
                              lo = md + 1;
                  }
                  l1 = ret;
                  lo = r1, hi = n;
                  while(lo <= hi){
                        int md = (lo + hi) >> 1;
                        if(get(r1, md, 0) >= L[i])
                              lo = md + 1, ret = md;
                        else
                              hi = md - 1;
                  }
                  r1 = ret;
                  lo = 1, hi = l2, ret = l2;
                  while(lo <= hi){
                        int md = (lo + hi) >> 1;
                        if(get(md, l2, 1) <= R[i])
                              hi = md - 1, ret = md;
                        else
                              lo = md + 1;
                  }
                  l2 = ret;
                  lo = r2, hi = n;
                  while(lo <= hi){
                        int md = (lo + hi) >> 1;
                        if(get(r2, md, 1) <= R[i])
                              lo = md + 1, ret = md;
                        else
                              hi = md - 1;
                  }
                  r2 = ret;
                  if(max(l1, l2) <= min(r1, r2))
                        A[i] = 1;
            }
      }

      return A;
}

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