Submission #1326635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326635		SmuggingSpun	Werewolf (IOI18_werewolf)	C++20	100 / 100	2709 ms	79440 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int lim = 2e5 + 5;
int n, m, q;
vector<int>X, Y, S, E, L, R, g[lim];
namespace sub12{
  vector<int>solve(){
    vector<int>ans(q);
    for(int i = 0; i < q; i++){
			vector<vector<bool>>f(n + 1, vector<bool>(2, false));
			queue<pair<int, int>>q;
			q.emplace(S[i], 0);
			f[S[i]][0] = true;
			while(!q.empty()){
				auto [s, c] = q.front();
				q.pop();
				if(c == 0 && L[i] <= s && R[i] >= s){
					f[s][1] = true;
					q.emplace(s, 1);
				}
				for(int& j : g[s]){
					int d = s ^ X[j] ^ Y[j];
					if(((c == 0 & d >= L[i]) || (c == 1 && d <= R[i])) && !f[d][c]){
						f[d][c] = true;
						q.emplace(d, c);
					}
				}
			}
			ans[i] = f[E[i]][1];
		}
    return ans;
  }
}
namespace sub3{
  bool check_subtask(){
    if(m != n - 1){
      return false;
    }
    for(int i = 1; i <= n; i++){
      if(g[i].size() > 2){
        return false;
      }
    }
    return true;
  }
  vector<int>solve(){
    int tdfs = 0;
    vector<int>low(n + 1), low2v(n + 1), ans(q);
    function<void(int, int)>dfs;
    dfs = [&] (int s, int p){
      low2v[low[s] = ++tdfs] = s;
      for(int& i : g[s]){
        int d = X[i] ^ Y[i] ^ s;
        if(d != p){
          dfs(d, s);
        }
      }
    };
    for(int i = 1; i <= n; i++){
      if(g[i].size() == 1){
        dfs(i, -1);
        break;
      }
    }
    vector<pair<int, int>>st(n << 2 | 3);
    auto merge = [&] (pair<int, int>a, pair<int, int>b){
      return make_pair(min(a.first, b.first), max(a.second, b.second));
    };
    function<void(int, int, int)>build;
    build = [&] (int id, int l, int r){
      if(l == r){
        st[id] = make_pair(low2v[l], low2v[l]);
        return;
      }
      int m = (l + r) >> 1;
      build(id << 1, l, m);
      build(id << 1 | 1, m + 1, r);
      st[id] = merge(st[id << 1], st[id << 1 | 1]);
    };
    build(1, 1, n);
    function<int(int, int, int, int, int, const bool)>get;
    get = [&] (int id, int l, int r, int u, int v, const bool is_min){
      if(l > v || r < u){
        return is_min ? INF : -INF;
      }
      if(u <= l && v >= r){
        return is_min ? st[id].first : st[id].second;
      }
      int m = (l + r) >> 1, left = get(id << 1, l, m, u, v, is_min), right = get(id << 1 | 1, m + 1, r, u, v, is_min);
      return is_min ? min(left, right) : max(left, right);
    };
    for(int i = 0; i < q; i++){
      int s = low[S[i]], e = low[E[i]];
      if(s < e){
        int low = s + 1, high = e, ps = s, pe = e;
        while(low <= high){
          int mid = (low + high) >> 1;
          if(get(1, 1, n, s, mid, true) >= L[i]){
            low = (ps = mid) + 1;
          }
          else{
            high = mid - 1;
          }
        }
        low = s;
        high = e - 1;
        while(low <= high){
          int mid = (low + high) >> 1;
          if(get(1, 1, n, mid, e, false) <= R[i]){
            high = (pe = mid) - 1;
          }
          else{
            low = mid + 1;
          }
        }
        ans[i] = pe <= ps;
      }
      else{
        int low = e, high = s - 1, ps = s, pe = e;
        while(low <= high){
          int mid = (low + high) >> 1;
          if(get(1, 1, n, mid, s, true) >= L[i]){
            high = (ps = mid) - 1;
          }
          else{
            low = mid + 1;
          }
        }
        low = e + 1;
        high = s;
        while(low <= high){
          int mid = (low + high) >> 1;
          if(get(1, 1, n, e, mid, false) <= R[i]){
            low = (pe = mid) + 1;
          }
          else{
            high = mid - 1;
          }
        }
        ans[i] = pe >= ps;
      }
    }
    return ans;
  }
}
namespace sub4{
  int tdfs = 0, lab[lim], low[lim], tail[lim], bit[lim], up[18][lim];
  vector<array<int, 3>>query[lim];
  int find_set(int i){
    while(i != lab[i]){
      i = lab[i] = lab[lab[i]];
    }
    return i;
  }
  vector<int>krt[lim];
  void dfs(int s){
    low[s] = ++tdfs;
    for(int& d : krt[s]){
      if(d != up[0][s]){
        up[0][d] = s;
        dfs(d);
      }
    }
    tail[s] = tdfs;
  }
  void update(int p){
    for(; p <= n; p += p & -p){
      bit[p]++;
    }
  }
  int get(int p){
    int ans = 0;
    for(; p > 0; p -= p & -p){
      ans += bit[p];
    }
    return ans;
  }
  vector<int>solve(){
    iota(lab + 1, lab + n + 1, 1);
    for(int i = n; i > 0; i--){
      for(int& ie : g[i]){
        int j = find_set(X[ie] ^ Y[ie] ^ i);
        if(j > i){
          krt[lab[j] = i].push_back(j);
        } 
      }
    }
    memset(up[0], 0, sizeof(up[0]));
    dfs(1);
    for(int i = 1; i < 18; i++){
      for(int j = 0; j <= n; j++){
        up[i][j] = up[i - 1][up[i - 1][j]];
      }
    }
    vector<pair<int, int>>tq1(q);
    for(int i = 0; i < q; i++){
      int x = S[i];
      for(int j = 17; j > -1; j--){
        int nx = up[j][x];
        if(nx >= L[i]){
          x = nx;
        }
      }
      tq1[i] = make_pair(low[x], tail[x]);
    }
    vector<int>p1(n + 1);
    for(int i = 1; i <= n; krt[i++].clear()){
      p1[i] = low[i];
    }
    iota(lab + 1, lab + n + 1, 1);
    for(int i = 1; i <= n; i++){
      for(int& ie : g[i]){
        int j = find_set(X[ie] ^ Y[ie] ^ i);
        if(j < i){
          krt[lab[j] = i].push_back(j);
        } 
      }
    }
    memset(up[0], tdfs = 0, sizeof(up[0]));
    dfs(n);
    for(int i = 1; i < 18; i++){
      for(int j = 1; j <= n; j++){
        up[i][j] = up[i - 1][up[i - 1][j]];
      }
    }
    for(int i = 1; i <= n; i++){
      query[p1[i]].push_back({-1, low[i], -1});
    }
    for(int i = 0; i < q; i++){
      int x = E[i];
      for(int j = 17; j > -1; j--){
        int nx = up[j][x];
        if(nx != 0 && nx <= R[i]){
          x = nx;
        }
      }
      query[tq1[i].first - 1].push_back({low[x], tail[x], -i - 1});
      query[tq1[i].second].push_back({low[x], tail[x], i});
    }
    vector<int>ans(q, 0);
    memset(bit, 0, sizeof(bit));
    for(int i = 1; i <= n; i++){
      for(auto& [l, r, id] : query[i]){
        if(l == -1){
          update(r);
        }
        else if(id < 0){
          ans[-id - 1] = get(r) - get(l - 1);
        }
        else{
          ans[id] = get(r) - get(l - 1) > ans[id];
        }
      }
    }
    return ans;
  }
}
vector<int>check_validity(int _n, vector<int>_X, vector<int>_Y, vector<int>_S, vector<int>_E, vector<int>_L, vector<int>_R){
  swap(X, _X);
  swap(Y, _Y);
  swap(S, _S);
  swap(E, _E);
  swap(L, _L);
  swap(R, _R);
  m = X.size();
  q = S.size();
	for(int i = 0; i < m; i++){
		g[++X[i]].emplace_back(i);
		g[++Y[i]].emplace_back(i);
	}
  for(int i = 0; i < q; i++){
    S[i]++;
    E[i]++;
    L[i]++;
    R[i]++;
  }
	if((n = _n) <= 3000 && m <= 6000 && q <= 3000){
		return sub12::solve();
	}
  if(sub3::check_subtask()){
    return sub3::solve();
  }
  return sub4::solve();
}

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