Submission #113266

#	Time	Username	Problem	Language	Result	Execution time	Memory
113266		IOrtroiii	Werewolf (IOI18_werewolf)	C++14	100 / 100	1669 ms	110728 KiB

werewolf

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 200200;
 
int n;
 
struct Tree {
   int root[N];
   int par[18][N];
   vector<int> g[N];
   vector<pair<int, int>> edge;
   int tin[N], tout[N], tt;
   void add(int u,int v) {
      edge.emplace_back(u, v);
   }
 
   void dfs(int u, int p) {
      par[0][u] = p;
      tin[u] = ++tt;
      for (int i = 1; i < 18; ++i) par[i][u] = par[i - 1][par[i - 1][u]];
      for (int v : g[u]) {
         dfs(v, u);
      }
      tout[u] = tt;
   }
 
   int anc(int u) {
      return root[u] == u ? u : root[u] = anc(root[u]);
   }
 
   void build() {
      for (int i = 0; i < n; ++i) root[i] = i;
      sort(edge.begin(), edge.end());
      for (auto e : edge) {
         int u = abs(e.first), v = abs(e.second);
         u = anc(u), v = anc(v);
         if (u ^ v) {
            g[u].push_back(v);
            root[v] = u;
         }
      }
   }
   int getL(int u,int l) {
      for (int i = 17; i >= 0; --i) {
         if (par[i][u] >= l) u = par[i][u];
      }
      return u;
   }
   int getR(int u,int r) {
      for (int i = 17; i >= 0; --i) {
         if (par[i][u] <= r) u = par[i][u];
      }
      return u;
   }
} pre, suf;
 
int ft[N];
 
void add(int p) {
   for (; p <= n; p += p & -p) ft[p]++;
}
 
int get(int p) {
   int ans = 0;
   for (; p > 0; p -= p & -p) ans += ft[p];
   return ans;
}
 
int get(int l,int r) {
   return get(r) - get(l - 1);
}
 
struct Query {
   int l, r, id, sgn;
   Query(int l = 0,int r = 0,int id = 0,int sgn = 0) : l(l), r(r), id(id), sgn(sgn) {}
   bool operator < (const Query &q) const {
      return r < q.r;
   }
};
 
int ans[N];
 
vector<int> check_validity(int n,vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l,vector<int> r) {
   ::n = n;
   int m = x.size(), q = s.size();
   for (int i = 0; i < m; ++i) {
      if (x[i] < y[i]) swap(x[i], y[i]);
      pre.add(x[i], y[i]);
      suf.add(-y[i], -x[i]);
   }
 
   pre.build();
   suf.build();
   pre.dfs(n - 1, n - 1);
   suf.dfs(0, 0);
 
   vector<vector<int>> ps(n + 1);
   for (int i = 0; i < n; ++i) {
      ps[pre.tin[i]].push_back(suf.tin[i]);
   }
   vector<vector<Query>> qs(n + 1);
   for (int i = 0; i < q; ++i) {
      int u = pre.getR(e[i], r[i]), v = suf.getL(s[i], l[i]);
      qs[pre.tin[u] - 1].push_back(Query(suf.tin[v], suf.tout[v], i, -1));
      qs[pre.tout[u]].push_back(Query(suf.tin[v], suf.tout[v], i, 1));
   }
 
 
   for (int i = 0; i <= n; ++i) {
      for (int p : ps[i]) {
         add(p);
      }
      for (auto q : qs[i]) {
         ans[q.id] += q.sgn * get(q.l, q.r);
      }
   }
 
   for (int i = 0; i < q; ++i) ans[i] = ans[i] > 0;
   return vector<int>(ans, ans + q);
}

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