oj.uz

Submission #76581

# Submission time Handle Problem Language Result Execution time Memory
76581 2018-09-15T00:50:35 Z Xylofo Werewolf (IOI18_werewolf) C++14
100 / 100
 1886 ms 235564 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i < b; ++i)
using vi = vector<int>;
using graph = vector<vi>;

const int LG = 28;

struct Tree {
  graph t;
  vi p;
  vector<vi> fastUp;
  int fd(int a) { return p[a] == a ? a : p[a] = fd(p[a]); }
  int n;
  vi start, end, fromP;
  int root;
  Tree(int rev, const graph &g) {
    n = g.size();
    t.resize(n);
    fastUp.assign(n, vi(LG,-1));
    p.resize(n);
    fromP = start = end = p;
    rep(i,0,n) p[i] = i;
    for(int i = rev*(n-1); i >= 0 && i < n; i += 1 - 2*rev) {
      for(int j:g[i]) if(rev ^ (j < i)) {
        int jj = fd(j);
        if(jj != i) {
          p[jj] = i;
          t[i].push_back(jj);
        }
      }
    }
    root = (1-rev)*(n-1);
    int T = 0;
    dfs(root, root, T);
  }
  void dfs(int x, int p, int&T) {
    fastUp[x][0] = p;
    rep(k,0,LG-1) fastUp[x][k+1] = fastUp[fastUp[x][k]][k];

    start[x] = T;
    fromP[T] = x;
    ++T;
    for(int y:t[x]) if(y != p) dfs(y, x, T);
    end[x] = T;
  }
};

namespace ST {
  struct node {
    int mx;
    node *l;
    node *r;
  } nil{-1,nullptr,nullptr};
  int query(int l, int r, int L, int R, node *cur) {
    if(!cur) return -1;
    if(r <= L || R <= l) return -1;
    if(l <= L && R <= r) return cur->mx;
    int M = (L+R)/2;
    return max(query(l,r,L,M,cur->l), query(l,r,M,R,cur->r));
  }
  node* update(int pos, int x, int L, int R, node *cur) {
    if(pos < L || R <= pos) return cur;
    if(!cur) cur = &nil;
    if(L+1 == R) return new node{x,nullptr,nullptr};
    int M = (L+R)/2;
    assert(cur);
    node *l = update(pos,x,L,M,cur->l);
    node *r = update(pos,x,M,R,cur->r);
    return new node{max(l ? l->mx : -1, r ? r->mx : -1), l, r};
  }
}

struct P {
  vi f;
  int n;
  vector<ST::node*> pst;
  P(const vi& p1, const vi& p2) {
    // f(x) = p2^{-1}(p1(x)))
    // (x in [l1,r1] and f(x) in [l2,r2]) => (p1[x] == p2[f(x)] satisfies stuff)
    n = p1.size();
    f.resize(n);
    pst.resize(n+1,nullptr);
    vi p2inv(n), finv(n);
    rep(i,0,n) p2inv[p2[i]] = i;
    rep(i,0,n) f[i] = p2inv[p1[i]];
    rep(i,0,n) finv[f[i]] = i;
    rep(i,0,n) pst[i+1] = update(finv[i], i, 0, n, pst[i]);
  }
  // p1[l1..r1) intersect p2[l2..r2)
  bool slv(int l1, int r1, int l2, int r2) {
    int mx = query(l1,r1,0,n,pst[r2]);
    return mx >= l2;
  }
};

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
  int n = N;
  int q = S.size();
  vi A(q);

  graph g(n);
  rep(i,0,X.size()) {
    g[X[i]].push_back(Y[i]);
    g[Y[i]].push_back(X[i]);
  }
  Tree up(0, g), dw(1, g);
  P perm(up.fromP, dw.fromP);
  rep(i,0,q) {
    int s = S[i];
    int e = E[i];
    int l = L[i];
    int r = R[i];
    // ----------------|
    // ... e ... l ... r ... s ...
    //           |----------------
    // find representatives of subtrees
    for(int k = LG-1; k >= 0; --k) {
      if(dw.fastUp[s][k] >= l) s = dw.fastUp[s][k];
      if(up.fastUp[e][k] <= r) e = up.fastUp[e][k];
    }
    int l1 = up.start[e], r1 = up.end[e];
    int l2 = dw.start[s], r2 = dw.end[s];
    A[i] = perm.slv(l1, r1, l2, r2);
  }
  return A;
}

Compilation message

werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:4:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a; i < b; ++i)
werewolf.cpp:104:7:
   rep(i,0,X.size()) {
       ~~~~~~~~~~~~                   
werewolf.cpp:104:3: note: in expansion of macro 'rep'
   rep(i,0,X.size()) {
   ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 3 ms 508 KB Output is correct
7 Correct 3 ms 564 KB Output is correct
8 Correct 2 ms 564 KB Output is correct
9 Correct 2 ms 564 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 3 ms 508 KB Output is correct
7 Correct 3 ms 564 KB Output is correct
8 Correct 2 ms 564 KB Output is correct
9 Correct 2 ms 564 KB Output is correct
10 Correct 13 ms 3320 KB Output is correct
11 Correct 12 ms 3320 KB Output is correct
12 Correct 12 ms 3376 KB Output is correct
13 Correct 12 ms 3540 KB Output is correct
14 Correct 12 ms 3572 KB Output is correct
15 Correct 14 ms 3572 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1173 ms 226252 KB Output is correct
2 Correct 1558 ms 229172 KB Output is correct
3 Correct 1281 ms 229172 KB Output is correct
4 Correct 1171 ms 229172 KB Output is correct
5 Correct 1093 ms 229172 KB Output is correct
6 Correct 1130 ms 229172 KB Output is correct
7 Correct 1060 ms 229172 KB Output is correct
8 Correct 1446 ms 229172 KB Output is correct
9 Correct 1113 ms 229172 KB Output is correct
10 Correct 879 ms 229172 KB Output is correct
11 Correct 942 ms 229172 KB Output is correct
12 Correct 937 ms 229172 KB Output is correct
13 Correct 1416 ms 234152 KB Output is correct
14 Correct 1393 ms 234252 KB Output is correct
15 Correct 1453 ms 234252 KB Output is correct
16 Correct 1629 ms 234252 KB Output is correct
17 Correct 1073 ms 234252 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 3 ms 508 KB Output is correct
7 Correct 3 ms 564 KB Output is correct
8 Correct 2 ms 564 KB Output is correct
9 Correct 2 ms 564 KB Output is correct
10 Correct 13 ms 3320 KB Output is correct
11 Correct 12 ms 3320 KB Output is correct
12 Correct 12 ms 3376 KB Output is correct
13 Correct 12 ms 3540 KB Output is correct
14 Correct 12 ms 3572 KB Output is correct
15 Correct 14 ms 3572 KB Output is correct
16 Correct 1173 ms 226252 KB Output is correct
17 Correct 1558 ms 229172 KB Output is correct
18 Correct 1281 ms 229172 KB Output is correct
19 Correct 1171 ms 229172 KB Output is correct
20 Correct 1093 ms 229172 KB Output is correct
21 Correct 1130 ms 229172 KB Output is correct
22 Correct 1060 ms 229172 KB Output is correct
23 Correct 1446 ms 229172 KB Output is correct
24 Correct 1113 ms 229172 KB Output is correct
25 Correct 879 ms 229172 KB Output is correct
26 Correct 942 ms 229172 KB Output is correct
27 Correct 937 ms 229172 KB Output is correct
28 Correct 1416 ms 234152 KB Output is correct
29 Correct 1393 ms 234252 KB Output is correct
30 Correct 1453 ms 234252 KB Output is correct
31 Correct 1629 ms 234252 KB Output is correct
32 Correct 1073 ms 234252 KB Output is correct
33 Correct 1620 ms 234252 KB Output is correct
34 Correct 390 ms 234252 KB Output is correct
35 Correct 1816 ms 234252 KB Output is correct
36 Correct 1416 ms 234252 KB Output is correct
37 Correct 1792 ms 234252 KB Output is correct
38 Correct 1637 ms 234252 KB Output is correct
39 Correct 1752 ms 235120 KB Output is correct
40 Correct 1670 ms 235120 KB Output is correct
41 Correct 1445 ms 235120 KB Output is correct
42 Correct 1020 ms 235120 KB Output is correct
43 Correct 1871 ms 235120 KB Output is correct
44 Correct 1886 ms 235120 KB Output is correct
45 Correct 1457 ms 235564 KB Output is correct
46 Correct 1507 ms 235564 KB Output is correct
47 Correct 1399 ms 235564 KB Output is correct
48 Correct 1321 ms 235564 KB Output is correct
49 Correct 1338 ms 235564 KB Output is correct
50 Correct 1382 ms 235564 KB Output is correct
51 Correct 1336 ms 235564 KB Output is correct
52 Correct 1363 ms 235564 KB Output is correct