oj.uz

Submission #208846

# Submission time Handle Problem Language Result Execution time Memory
208846 2020-03-12T09:50:14 Z anonymous Werewolf (IOI18_werewolf) C++14
100 / 100
 1656 ms 131044 KB 
#include "werewolf.h"
#include <vector>
#include <utility>
#include <algorithm>
#define MAXN 200005
using namespace std;

class DSU { //1 indexed
    int par[MAXN], sz;
    vector<int> T[MAXN];
public:
    int anc[MAXN][20], ID[MAXN][2], seq = 1;
    int Find(int x) {
        return(par[x] == x ? x : par[x] = Find(par[x]));
    }
    void Union(int x, int y) {
        int p1 = Find(x), p2 = Find(y);
        if (p1 == p2) {return;}
        if (!anc[p1][0]) {
            anc[p1][0]=p2;
            T[p2].push_back(p1);
        }
        par[p1]=p2;
    }
    void Init(int n) {
        sz = n;
        for (int i=1; i <= n; i++) {
            par[i]=i;
        }
    }
    void makeJump() {
        for (int i=1; i<20; i++) {
            for (int j=1; j<=sz; j++) {
                anc[j][i] = anc[anc[j][i-1]][i-1];
            }
        }
    }
    void ET(int u) {
        ID[u][0] = seq;
        seq++;
        for (auto v: T[u]) {ET(v);}
        ID[u][1] = seq - 1;
    }
    int range(int v, int cap, bool t) { //t = 1 means all values at most cap
        for (int i=19; i>=0; i--) { //t = 0 means all values at least cap
            if (t && anc[v][i] && anc[v][i] <= cap) {
                v = anc[v][i];
            } else if ((!t) && anc[v][i] && anc[v][i] >= cap) {
                v = anc[v][i];
            }
        }
        if (t && anc[v][0] && anc[v][0] <= cap) {
            v = anc[v][0];
        } else if ((!t) && anc[v][0] && anc[v][0] >= cap) {
            v = anc[v][0];
        }
        return(v);
    }
} Tmin, Tmax; //semi-Kruskal reconstruction trees: doesn't need to add new node

class PersistentSegtree {
    int ST[MAXN * 30][3];
    int R[MAXN], X[MAXN], pt = 1, ver = 1;
public:
    int upd(int ind, int l, int r, int cur) {
        if (ind < l || ind > r) {return(cur);}
        if (l == r) {
            ST[pt][0] = ST[cur][0] + 1, pt++;
            return(pt-1);
        } else {
            int tmp = pt, mid = (l + r) >> 1;
            pt++;
            ST[tmp][1] = upd(ind, l, mid, ST[cur][1]);
            ST[tmp][2] = upd(ind, mid+1, r, ST[cur][2]);
            ST[tmp][0] = ST[ST[tmp][1]][0] + ST[ST[tmp][2]][0];
            return(tmp);
        }
    }
    int ask(int lo, int hi, int l, int r, int cur) {
        if (hi < l || lo > r || !cur) {return(0);}
        if (lo <= l && hi >= r) {return(ST[cur][0]);}
        else {
            int mid = (l + r) >> 1;
            return(ask(lo, hi, l, mid, ST[cur][1]) +
                   ask(lo, hi, mid+1, r, ST[cur][2]));
        }
    }
    void add(int x, int y) {
        X[ver] = x;
        R[ver] = upd(y, 1, MAXN, R[ver-1]);
        ver++;
    }
    int get(int x) { //find largest index i that X[i] not exceeding x
        int lo = 0, hi = ver;
        while (lo + 1 != hi) {
            int mid = (lo + hi) >> 1;
            if (X[mid] <= x) {lo = mid;}
            else {hi = mid;}
        }
        return(lo);
    }
    int Sum(int xlo, int ylo, int xhi, int yhi) {
        int ql = get(xlo) - 1, qr = get(xhi);
        return(ask(ylo, yhi, 1, MAXN, R[qr]) - ask(ylo, yhi, 1, MAXN, R[ql]));
    }
} PST;

vector<int> adj[MAXN];
vector<pair<int,int> > pts;

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();
  Tmin.Init(N), Tmax.Init(N);
  for (int i=0; i<M; i++) {
    adj[X[i]+1].push_back(Y[i]+1);
    adj[Y[i]+1].push_back(X[i]+1);
  }
  for (int i=1; i<=N; i++) { //min bottleneck (minimise max wt)
    for (auto v: adj[i]) {
        if (i > v) {
            Tmin.Union(v,i);
        }
    }
  }
  for (int i=N; i>=1; i--) { //max bottleneck (max min wt)
    for (auto v: adj[i]) {
        if (i < v) {
            Tmax.Union(v,i);
        }
    }
  }
  Tmin.ET(N), Tmax.ET(1);
  Tmin.makeJump(), Tmax.makeJump();
  for (int i=1; i<=N; i++) {
    pts.push_back({Tmin.ID[i][0], Tmax.ID[i][0]});
  }
  sort(pts.begin(), pts.end());
  for (auto P: pts) {
    PST.add(P.first, P.second);
  }
  vector<int> A;
  for (int i = 0; i < Q; ++i) {
    int s = S[i] + 1, e = E[i] + 1, l = L[i] + 1, r = R[i] + 1;
    int s2 = Tmax.range(s, l, false), e2 = Tmin.range(e, r, true);
    int xl = Tmin.ID[e2][0], xr = Tmin.ID[e2][1];
    int yl = Tmax.ID[s2][0], yr = Tmax.ID[s2][1];
    if (PST.Sum(xl, yl, xr, yr)) {A.push_back(1);}
    else {A.push_back(0);}

  }
  return A;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14456 KB Output is correct
2 Correct 13 ms 14456 KB Output is correct
3 Correct 14 ms 14456 KB Output is correct
4 Correct 13 ms 14456 KB Output is correct
5 Correct 13 ms 14456 KB Output is correct
6 Correct 13 ms 14456 KB Output is correct
7 Correct 14 ms 14456 KB Output is correct
8 Correct 13 ms 14456 KB Output is correct
9 Correct 13 ms 14456 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14456 KB Output is correct
2 Correct 13 ms 14456 KB Output is correct
3 Correct 14 ms 14456 KB Output is correct
4 Correct 13 ms 14456 KB Output is correct
5 Correct 13 ms 14456 KB Output is correct
6 Correct 13 ms 14456 KB Output is correct
7 Correct 14 ms 14456 KB Output is correct
8 Correct 13 ms 14456 KB Output is correct
9 Correct 13 ms 14456 KB Output is correct
10 Correct 22 ms 16248 KB Output is correct
11 Correct 22 ms 16248 KB Output is correct
12 Correct 20 ms 16248 KB Output is correct
13 Correct 22 ms 16248 KB Output is correct
14 Correct 21 ms 16248 KB Output is correct
15 Correct 22 ms 16376 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 977 ms 124764 KB Output is correct
2 Correct 1147 ms 126188 KB Output is correct
3 Correct 1014 ms 124812 KB Output is correct
4 Correct 903 ms 124268 KB Output is correct
5 Correct 915 ms 124268 KB Output is correct
6 Correct 938 ms 124392 KB Output is correct
7 Correct 866 ms 124392 KB Output is correct
8 Correct 1092 ms 126188 KB Output is correct
9 Correct 876 ms 124840 KB Output is correct
10 Correct 678 ms 124392 KB Output is correct
11 Correct 744 ms 124268 KB Output is correct
12 Correct 752 ms 124396 KB Output is correct
13 Correct 1105 ms 131044 KB Output is correct
14 Correct 1120 ms 130916 KB Output is correct
15 Correct 1092 ms 130788 KB Output is correct
16 Correct 1089 ms 130916 KB Output is correct
17 Correct 845 ms 124008 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14456 KB Output is correct
2 Correct 13 ms 14456 KB Output is correct
3 Correct 14 ms 14456 KB Output is correct
4 Correct 13 ms 14456 KB Output is correct
5 Correct 13 ms 14456 KB Output is correct
6 Correct 13 ms 14456 KB Output is correct
7 Correct 14 ms 14456 KB Output is correct
8 Correct 13 ms 14456 KB Output is correct
9 Correct 13 ms 14456 KB Output is correct
10 Correct 22 ms 16248 KB Output is correct
11 Correct 22 ms 16248 KB Output is correct
12 Correct 20 ms 16248 KB Output is correct
13 Correct 22 ms 16248 KB Output is correct
14 Correct 21 ms 16248 KB Output is correct
15 Correct 22 ms 16376 KB Output is correct
16 Correct 977 ms 124764 KB Output is correct
17 Correct 1147 ms 126188 KB Output is correct
18 Correct 1014 ms 124812 KB Output is correct
19 Correct 903 ms 124268 KB Output is correct
20 Correct 915 ms 124268 KB Output is correct
21 Correct 938 ms 124392 KB Output is correct
22 Correct 866 ms 124392 KB Output is correct
23 Correct 1092 ms 126188 KB Output is correct
24 Correct 876 ms 124840 KB Output is correct
25 Correct 678 ms 124392 KB Output is correct
26 Correct 744 ms 124268 KB Output is correct
27 Correct 752 ms 124396 KB Output is correct
28 Correct 1105 ms 131044 KB Output is correct
29 Correct 1120 ms 130916 KB Output is correct
30 Correct 1092 ms 130788 KB Output is correct
31 Correct 1089 ms 130916 KB Output is correct
32 Correct 845 ms 124008 KB Output is correct
33 Correct 1302 ms 124172 KB Output is correct
34 Correct 477 ms 35728 KB Output is correct
35 Correct 1567 ms 125512 KB Output is correct
36 Correct 1220 ms 124524 KB Output is correct
37 Correct 1522 ms 125160 KB Output is correct
38 Correct 1330 ms 125032 KB Output is correct
39 Correct 1303 ms 130428 KB Output is correct
40 Correct 1153 ms 130564 KB Output is correct
41 Correct 1169 ms 124652 KB Output is correct
42 Correct 835 ms 124264 KB Output is correct
43 Correct 1656 ms 128840 KB Output is correct
44 Correct 1446 ms 124776 KB Output is correct
45 Correct 1131 ms 130540 KB Output is correct
46 Correct 1308 ms 130268 KB Output is correct
47 Correct 1102 ms 130612 KB Output is correct
48 Correct 1149 ms 130404 KB Output is correct
49 Correct 1197 ms 130792 KB Output is correct
50 Correct 1232 ms 130908 KB Output is correct
51 Correct 1125 ms 130804 KB Output is correct
52 Correct 1094 ms 130824 KB Output is correct