oj.uz

Submission #113265

# Submission time Handle Problem Language Result Execution time Memory
113265 2019-05-24T13:51:21 Z IOrtroiii Werewolf (IOI18_werewolf) C++14
49 / 100
 1447 ms 104540 KB 
#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 < 17; ++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 = 16; i >= 0; --i) {
         if (par[i][u] >= l) u = par[i][u];
      }
      return u;
   }
   int getR(int u,int r) {
      for (int i = 16; 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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9984 KB Output is correct
2 Correct 10 ms 9984 KB Output is correct
3 Correct 9 ms 9984 KB Output is correct
4 Correct 9 ms 9984 KB Output is correct
5 Correct 10 ms 9984 KB Output is correct
6 Correct 9 ms 9984 KB Output is correct
7 Correct 10 ms 9968 KB Output is correct
8 Correct 9 ms 9984 KB Output is correct
9 Correct 10 ms 9924 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9984 KB Output is correct
2 Correct 10 ms 9984 KB Output is correct
3 Correct 9 ms 9984 KB Output is correct
4 Correct 9 ms 9984 KB Output is correct
5 Correct 10 ms 9984 KB Output is correct
6 Correct 9 ms 9984 KB Output is correct
7 Correct 10 ms 9968 KB Output is correct
8 Correct 9 ms 9984 KB Output is correct
9 Correct 10 ms 9924 KB Output is correct
10 Correct 17 ms 11264 KB Output is correct
11 Correct 16 ms 11136 KB Output is correct
12 Correct 16 ms 11136 KB Output is correct
13 Correct 15 ms 11264 KB Output is correct
14 Correct 16 ms 11264 KB Output is correct
15 Correct 16 ms 11264 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1396 ms 89900 KB Output is correct
2 Correct 1038 ms 100520 KB Output is correct
3 Correct 1008 ms 98884 KB Output is correct
4 Correct 1070 ms 97728 KB Output is correct
5 Correct 1061 ms 97716 KB Output is correct
6 Correct 1211 ms 97808 KB Output is correct
7 Correct 1113 ms 96576 KB Output is correct
8 Correct 929 ms 100444 KB Output is correct
9 Correct 648 ms 98644 KB Output is correct
10 Correct 523 ms 96640 KB Output is correct
11 Correct 568 ms 97552 KB Output is correct
12 Correct 549 ms 97280 KB Output is correct
13 Correct 1052 ms 104400 KB Output is correct
14 Correct 1065 ms 104540 KB Output is correct
15 Correct 1092 ms 104416 KB Output is correct
16 Correct 1037 ms 104524 KB Output is correct
17 Correct 1138 ms 96884 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9984 KB Output is correct
2 Correct 10 ms 9984 KB Output is correct
3 Correct 9 ms 9984 KB Output is correct
4 Correct 9 ms 9984 KB Output is correct
5 Correct 10 ms 9984 KB Output is correct
6 Correct 9 ms 9984 KB Output is correct
7 Correct 10 ms 9968 KB Output is correct
8 Correct 9 ms 9984 KB Output is correct
9 Correct 10 ms 9924 KB Output is correct
10 Correct 17 ms 11264 KB Output is correct
11 Correct 16 ms 11136 KB Output is correct
12 Correct 16 ms 11136 KB Output is correct
13 Correct 15 ms 11264 KB Output is correct
14 Correct 16 ms 11264 KB Output is correct
15 Correct 16 ms 11264 KB Output is correct
16 Correct 1396 ms 89900 KB Output is correct
17 Correct 1038 ms 100520 KB Output is correct
18 Correct 1008 ms 98884 KB Output is correct
19 Correct 1070 ms 97728 KB Output is correct
20 Correct 1061 ms 97716 KB Output is correct
21 Correct 1211 ms 97808 KB Output is correct
22 Correct 1113 ms 96576 KB Output is correct
23 Correct 929 ms 100444 KB Output is correct
24 Correct 648 ms 98644 KB Output is correct
25 Correct 523 ms 96640 KB Output is correct
26 Correct 568 ms 97552 KB Output is correct
27 Correct 549 ms 97280 KB Output is correct
28 Correct 1052 ms 104400 KB Output is correct
29 Correct 1065 ms 104540 KB Output is correct
30 Correct 1092 ms 104416 KB Output is correct
31 Correct 1037 ms 104524 KB Output is correct
32 Correct 1138 ms 96884 KB Output is correct
33 Correct 1447 ms 98320 KB Output is correct
34 Correct 426 ms 50700 KB Output is correct
35 Correct 1280 ms 100616 KB Output is correct
36 Correct 1363 ms 98884 KB Output is correct
37 Correct 1260 ms 99932 KB Output is correct
38 Correct 1326 ms 99540 KB Output is correct
39 Incorrect 1277 ms 104184 KB Output isn't correct
40 Halted 0 ms 0 KB -