oj.uz

답안 #335511

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
335511 2020-12-12T22:53:04 Z couplefire 늑대인간 (IOI18_werewolf) C++17
100 / 100
 1545 ms 90124 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define REP(i,n) for(int i=0;i<(n);++i)


struct tree_2d_t {
  vector<pair<int,int> > pts;
  vector<vector<int> > nodes;
  int base;
  int n;

  tree_2d_t(const vector<pair<int,int> >& points) {
    pts = points;
    sort(pts.begin(), pts.end());
    n = pts.size();
    base = 1;
    while (base < n) { base *= 2; }
    nodes.resize(2*base);
    REP(i, n) {
      nodes[base + i].push_back(pts[i].second);
    }
    for (int i = base-1; i >= 1; --i) {
      merge(nodes[2*i].begin(), nodes[2*i].end(),
          nodes[2*i+1].begin(), nodes[2*i+1].end(),
          back_inserter(nodes[i]));
    }
  }

  int query(int x, int yl, int yr) {
    yl = lower_bound(nodes[x].begin(), nodes[x].end(), yl) - nodes[x].begin();
    yr = lower_bound(nodes[x].begin(), nodes[x].end(), yr+1) - nodes[x].begin();
    return yr - yl;
  }

  int query(int xl, int xr, int yl, int yr) {
    // Returns number of points in rectangle [xl, xr) x [yl, yr)
    xl = lower_bound(pts.begin(), pts.end(), make_pair(xl, -1)) - pts.begin();
    xr = lower_bound(pts.begin(), pts.end(), make_pair(xr+1, -1)) - pts.begin();
    int cnt = 0;
    xl += base;
    xr += base-1;
    cnt += query(xl, yl, yr);
    if (xl != xr) {
      cnt += query(xr, yl, yr);
    }
    while (xl/2 != xr/2) {
      if (~xl&1) { cnt += query(xl+1, yl, yr); }
      if (xr&1) { cnt += query(xr-1, yl, yr); }
      xl /= 2;
      xr /= 2;
    }
    return cnt;
  }
};


int fufind(vector<int>& fu, int x) {
  return fu[x] < 0 ? x : fu[x] = fufind(fu, fu[x]);
}

void fujoin(vector<int>& fu, vector<pair<int,int> >& tree, int x, int y) {
  x = fufind(fu, x);
  y = fufind(fu, y);
  if (x != y) {
    int p = fu.size();
    fu[y] = p;
    fu[x] = p;
    fu.push_back(-1);
    tree.push_back(make_pair(y, x));
  }
}


pair<int,int> dfs(vector<pair<int,int> >& tree, int v, int N, int& k) {
  if (v < N) {
    tree[v].first = tree[v].second = k;
    k++;
  } else {
    pair<int,int> A = dfs(tree, tree[v].first, N, k);
    pair<int,int> B = dfs(tree, tree[v].second, N, k);
    tree[v].first = min(A.first, B.first);
    tree[v].second = max(A.second, B.second);
  }
  return make_pair(tree[v].first, tree[v].second);
}


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();
  vector<int> A(Q);

  // Construct the graph
  vector<vector<int> > adj(N);
  int M = X.size();
  REP(i, M) {
    adj[X[i]].push_back(Y[i]);
    adj[Y[i]].push_back(X[i]);
  }

  // Inits
  vector<int> idx(Q+1);
  vector<int> fu(N);
  vector<pair<int,int> > tree(N);
  vector<int> leads(Q+1);
  vector<pair<int,int> > points(N);
  vector<pair<int,int> > Lrange(Q), Rrange(Q);

  // Sentinels
  L.push_back(0);
  R.push_back(N-1);
  S.push_back(0);
  E.push_back(0);

  REP(i, Q+1) {
    idx[i] = i;
  }

  // Process left
  REP(i, N) {
    fu[i] = -1;
  }
  sort(idx.begin(), idx.end(), [&L](int i, int j) { return L[i] > L[j]; });
  int next = N-1;

  REP(i, Q+1) {
    int limit = L[idx[i]];
    for ( ; next >= limit; next--) {
      // Try to join vertex next
      for (int u : adj[next]) {
        if (u >= limit) {
          fujoin(fu, tree, next, u);
        }
      }
    }
    int lead = fufind(fu, S[idx[i]]);
    leads[idx[i]] = lead;
  }

  int k = 0;
  dfs(tree, tree.size()-1, N, k);

  REP(i, Q) {
    Lrange[i] = tree[leads[i]];
  }
  REP(i, N) {
    points[i].first = tree[i].first;
  }

  // Process right
  REP(i, N) {
    fu[i] = -1;
  }
  fu.resize(N);
  tree.resize(N);
  sort(idx.begin(), idx.end(), [&R](int i, int j) { return R[i] < R[j]; });
  next = 0;

  REP(i, Q+1) {
    int limit = R[idx[i]];
    for ( ; next <= limit; next++) {
      // Try to join vertex next
      for (int u : adj[next]) {
        if (u <= limit) {
          fujoin(fu, tree, next, u);
        }
      }
    }
    int lead = fufind(fu, E[idx[i]]);
    leads[idx[i]] = lead;
  }

  k = 0;
  dfs(tree, tree.size()-1, N, k);

  REP(i, Q) {
    Rrange[i] = tree[leads[i]];
  }
  REP(i, N) {
    points[i].second = tree[i].first;
  }

  tree_2d_t tree_2d(points);

  // Answers
  REP(i, Q) {
    A[i] = tree_2d.query(Lrange[i].first, Lrange[i].second,
        Rrange[i].first, Rrange[i].second) > 0;
  }

  return A;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 9 ms 1516 KB Output is correct
11 Correct 8 ms 1516 KB Output is correct
12 Correct 7 ms 1388 KB Output is correct
13 Correct 8 ms 1644 KB Output is correct
14 Correct 8 ms 1644 KB Output is correct
15 Correct 9 ms 1516 KB Output is correct

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 726 ms 80124 KB Output is correct
2 Correct 1227 ms 84480 KB Output is correct
3 Correct 1058 ms 81916 KB Output is correct
4 Correct 866 ms 80636 KB Output is correct
5 Correct 844 ms 80604 KB Output is correct
6 Correct 776 ms 80344 KB Output is correct
7 Correct 677 ms 80124 KB Output is correct
8 Correct 1119 ms 84604 KB Output is correct
9 Correct 732 ms 81788 KB Output is correct
10 Correct 708 ms 80124 KB Output is correct
11 Correct 740 ms 80216 KB Output is correct
12 Correct 553 ms 80252 KB Output is correct
13 Correct 1061 ms 84732 KB Output is correct
14 Correct 1073 ms 84476 KB Output is correct
15 Correct 1077 ms 84560 KB Output is correct
16 Correct 1074 ms 84476 KB Output is correct
17 Correct 692 ms 80124 KB Output is correct

Subtask #4
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 9 ms 1516 KB Output is correct
11 Correct 8 ms 1516 KB Output is correct
12 Correct 7 ms 1388 KB Output is correct
13 Correct 8 ms 1644 KB Output is correct
14 Correct 8 ms 1644 KB Output is correct
15 Correct 9 ms 1516 KB Output is correct
16 Correct 726 ms 80124 KB Output is correct
17 Correct 1227 ms 84480 KB Output is correct
18 Correct 1058 ms 81916 KB Output is correct
19 Correct 866 ms 80636 KB Output is correct
20 Correct 844 ms 80604 KB Output is correct
21 Correct 776 ms 80344 KB Output is correct
22 Correct 677 ms 80124 KB Output is correct
23 Correct 1119 ms 84604 KB Output is correct
24 Correct 732 ms 81788 KB Output is correct
25 Correct 708 ms 80124 KB Output is correct
26 Correct 740 ms 80216 KB Output is correct
27 Correct 553 ms 80252 KB Output is correct
28 Correct 1061 ms 84732 KB Output is correct
29 Correct 1073 ms 84476 KB Output is correct
30 Correct 1077 ms 84560 KB Output is correct
31 Correct 1074 ms 84476 KB Output is correct
32 Correct 692 ms 80124 KB Output is correct
33 Correct 1073 ms 81692 KB Output is correct
34 Correct 428 ms 37100 KB Output is correct
35 Correct 1316 ms 84808 KB Output is correct
36 Correct 946 ms 81024 KB Output is correct
37 Correct 1231 ms 84096 KB Output is correct
38 Correct 1049 ms 81724 KB Output is correct
39 Correct 769 ms 89892 KB Output is correct
40 Correct 996 ms 89904 KB Output is correct
41 Correct 1082 ms 83540 KB Output is correct
42 Correct 932 ms 81188 KB Output is correct
43 Correct 1545 ms 88732 KB Output is correct
44 Correct 1204 ms 84012 KB Output is correct
45 Correct 817 ms 90072 KB Output is correct
46 Correct 1107 ms 89796 KB Output is correct
47 Correct 1069 ms 84972 KB Output is correct
48 Correct 1064 ms 84616 KB Output is correct
49 Correct 1072 ms 84792 KB Output is correct
50 Correct 1082 ms 84568 KB Output is correct
51 Correct 878 ms 90124 KB Output is correct
52 Correct 902 ms 90088 KB Output is correct