oj.uz

Submission #548376

# Submission time Handle Problem Language Result Execution time Memory
548376 2022-04-13T07:39:56 Z cig32 Werewolf (IOI18_werewolf) C++17
100 / 100
 1447 ms 221760 KB 
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <iostream>
#include <bits/stdc++.h>
//#include "werewolf.h"

using namespace std;


std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R);



struct edge {
  int f, t, w;
};
class cmp1 { // MST for wolf
  public:
  bool operator() (edge x, edge y) {
    return x.w > y.w;
  }
};
class cmp2 { // MST for human
  public:
  bool operator() (edge x, edge y) {
    return x.w < y.w;
  }
};

std::priority_queue<edge, std::vector<edge>, cmp1> wolf;
std::priority_queue<edge, std::vector<edge>, cmp2> human;

const int MAXN = 2e5 + 12;
int dsu1[MAXN], dsu2[MAXN];

int set_of1(int u) {
  if(dsu1[u] == u) return u;
  return dsu1[u] = set_of1(dsu1[u]);
}
int set_of2(int u) {
  if(dsu2[u] == u) return u;
  return dsu2[u] = set_of2(dsu2[u]);
}
void union1(int u, int v) {
  dsu1[set_of1(u)] = set_of1(v);
}
void union2(int u, int v) {
  dsu2[set_of2(u)] = set_of2(v);
}

int rep1[MAXN];
int rep2[MAXN];

std::vector<int> krt_wolf[2 * MAXN];
std::vector<int> krt_human[2 * MAXN];

int wlim_wolf[2 * MAXN];
int wlim_human[2 * MAXN];

int assigned[MAXN];
int stoN;
int q;
int mi[2 * MAXN], ma[2 * MAXN];

int par_wolf[19][2 * MAXN];
int wolfdepth[2 * MAXN];
std::pair<int, int> dfs1(int node, int curdepth) {
  wolfdepth[node] = curdepth;
  if(node < stoN) {
    assigned[node] = q++; 
    mi[node] = ma[node] = assigned[node];
    return {assigned[node], assigned[node]};
  }
  mi[node] = 1e9, ma[node] = -1;
  for(int x: krt_wolf[node]) {
    std::pair<int, int> res = dfs1(x, curdepth + 1);
    mi[node] = std::min(mi[node], res.first);
    ma[node] = std::max(ma[node], res.second);
    par_wolf[0][x] = node;
  }
  return {mi[node], ma[node]};
}

int par_human[19][2 * MAXN];

int A[MAXN];
int humandepth[2 * MAXN];

int rangel[2 * MAXN], ranger[2 * MAXN];

std::pair<int, int> dfs2(int node, int curdepth) {
  humandepth[node] = curdepth;
  if(node < stoN) {
    A[q] = assigned[node]; 
    rangel[node] = ranger[node] = q;
    q++;
    return {rangel[node], ranger[node]};
  }
  rangel[node] = 1e9, ranger[node] = -1;
  for(int x: krt_human[node]) {
    std::pair<int, int> res = dfs2(x, curdepth + 1);
    rangel[node] = std::min(rangel[node], res.first);
    ranger[node] = std::max(ranger[node], res.second);
    par_human[0][x] = node;
  }
  return {rangel[node], ranger[node]};
}

struct wavelet_tree {
  int lo, hi;
  wavelet_tree *l, *r;
  int *b, *c, bsz, csz; // c holds the prefix sum of elements
 
  wavelet_tree() {
    lo = 1;
    hi = 0;
    bsz = 0;
    csz = 0, l = NULL;
    r = NULL;
  }
 
  void init(int *from, int *to, int x, int y) {
    lo = x, hi = y;
    if(from >= to) return;
    int mid = (lo + hi) >> 1;
    auto f = [mid](int x) {
      return x <= mid;
    };
    b = (int*)malloc((to - from + 2) * sizeof(int));
    bsz = 0;
    b[bsz++] = 0;
    c = (int*)malloc((to - from + 2) * sizeof(int));
    csz = 0;
    c[csz++] = 0;
    for(auto it = from; it != to; it++) {
      b[bsz] = (b[bsz - 1] + f(*it));
      c[csz] = (c[csz - 1] + (*it));
      bsz++;
      csz++;
    }
    if(hi == lo) return;
    auto pivot = stable_partition(from, to, f);
    l = new wavelet_tree();
    l->init(from, pivot, lo, mid);
    r = new wavelet_tree();
    r->init(pivot, to, mid + 1, hi);
  }
  //kth smallest element in [l, r]
  //for array [1,2,1,3,5] 2nd smallest is 1 and 3rd smallest is 2
  int kth(int l, int r, int k) {
    if(l > r) return 0;
    if(lo == hi) return lo;
    int inLeft = b[r] - b[l - 1], lb = b[l - 1], rb = b[r];
    if(k <= inLeft) return this->l->kth(lb + 1, rb, k);
    return this->r->kth(l - lb, r - rb, k - inLeft);
  }
  //count of numbers in [l, r] Less than or equal to k
  int LTE(int l, int r, int k) {
    if(l > r || k < lo) return 0;
    if(hi <= k) return r - l + 1;
    int lb = b[l - 1], rb = b[r];
    return this->l->LTE(lb + 1, rb, k) + this->r->LTE(l - lb, r - rb, k);
  }
  //count of numbers in [l, r] equal to k
  int count(int l, int r, int k) {
    if(l > r || k < lo || k > hi) return 0;
    if(lo == hi) return r - l + 1;
    int lb = b[l - 1], rb = b[r];
    int mid = (lo + hi) >> 1;
    if(k <= mid) return this->l->count(lb + 1, rb, k);
    return this->r->count(l - lb, r - rb, k);
  }
  //sum of numbers in [l ,r] less than or equal to k
  int sum(int l, int r, int k) {
    if(l > r or k < lo) return 0;
    if(hi <= k) return c[r] - c[l - 1];
    int lb = b[l - 1], rb = b[r];
    return this->l->sum(lb + 1, rb, k) + this->r->sum(l - lb, r - rb, k);
  }
  //count max element in [l, r] stricly smaller than k
  int upper_bound(int l, int r, int k) {
    if(l > r) return -1;
    int uwu = LTE(l, r, k - 1);
    if(uwu == 0) return -1;
    return kth(l, r, uwu);
  }
  ~wavelet_tree() {
    delete l;
    delete r;
  }
};

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
  stoN = N;
  for(int i=0; i<N; i++) {
    dsu1[i] = dsu2[i] = i;
    rep1[i] = rep2[i] = i;
    wlim_wolf[i] = wlim_human[i] = i; //idk anymore
  }
  int Q = S.size();
  std::vector<int> Answer(Q);
  int M = X.size();
  for(int i=0; i<M; i++) {
    wolf.push({X[i], Y[i], std::max(X[i], Y[i])});
    human.push({X[i], Y[i], std::min(X[i], Y[i])});
  }
  int newnode = N;
  while(wolf.size()) {
    if(set_of1(wolf.top().f) != set_of1(wolf.top().t)) {
      int ff = rep1[set_of1(wolf.top().f)];
      int tt = rep1[set_of1(wolf.top().t)];
      union1(wolf.top().f, wolf.top().t);
      krt_wolf[newnode].push_back(ff);
      krt_wolf[newnode].push_back(tt);
      wlim_wolf[newnode] = wolf.top().w;
      rep1[set_of1(wolf.top().f)] = newnode;
      newnode++;
    }
    wolf.pop();
  }
  int wolfrt = newnode - 1;
  newnode = N;
  while(human.size()) {
    if(set_of2(human.top().f) != set_of2(human.top().t)) {
      int ff = rep2[set_of2(human.top().f)];
      int tt = rep2[set_of2(human.top().t)];
      union2(human.top().f, human.top().t);
      krt_human[newnode].push_back(ff);
      krt_human[newnode].push_back(tt);
      wlim_human[newnode] = human.top().w;
      rep2[set_of2(human.top().f)] = newnode;
      newnode++;
    }
    human.pop();
  }
  int humanrt = newnode - 1;
  
  
  dfs1(wolfrt, 0);
  par_wolf[0][wolfrt] = wolfrt;
  for(int i=1; i<19; i++) {
    for(int j=0; j<=wolfrt; j++) {
      par_wolf[i][j] = par_wolf[i-1][par_wolf[i-1][j]];
    }
  }
  q = 0;
  dfs2(humanrt, 0);
  par_human[0][humanrt] = humanrt;
  for(int i=1; i<19; i++) {
    for(int j=0; j<=humanrt; j++) {
      par_human[i][j] = par_human[i-1][par_human[i-1][j]];
    }
  }

  /*
  std::cout << "wolf\n";
  for(int i=wolfrt; i >= 0; i--) {
    std::cout << "node "<<i<<". weight limit = "<<wlim_wolf[i]<<", node new ids range = [" << mi[i] << ", " << ma[i] << "]\n";
    for(int x: krt_wolf[i]) std::cout << i << ' ' << x << '\n';
  }
  std::cout << "human\n";
  for(int i=humanrt; i >= 0; i--) {
    std::cout << "node " <<i<<". weight limit = "<<wlim_human[i]<<"\n";
    for(int x: krt_human[i]) std::cout << i << ' ' << x << '\n';
  }

  
  for(int i=0; i<N; i++) {
    for(int j=0; j<N; j++) {
      if(assigned[j] == i) {
        std::cout << "order " << i <<": " << j <<"\n";
      }
    }
  }
  */
  wavelet_tree wlt;
  int B[N + 1];
  for(int i=0; i<N; i++) B[i + 1] = A[i];
  wlt.init(B + 1, B + N + 1, 0, N - 1);
  /*
  std::cout << "A array:";
  for(int i=0; i<N; i++) std::cout << " " << A[i];
  std::cout << "\n"; 
  cout << wlt.LTE(0, 0, 5) << "\n";
  cout << wlt.kth(1, 1, 1) <<"\n";
  cout << wlt.upper_bound(0, 0, 6) << " uss\n";
  */
  for(int i=0; i<Q; i++) {
    for(int j=18; j>=0; j--) {
      if(humandepth[S[i]] >= (1 << j) && wlim_human[par_human[j][S[i]]] >= L[i]) S[i] = par_human[j][S[i]];
      if(wolfdepth[E[i]] >= (1 << j) && wlim_wolf[par_wolf[j][E[i]]] <= R[i]) E[i] = par_wolf[j][E[i]];
    }
    int l = mi[E[i]];
    int r = ma[E[i]];
    int humanl = rangel[S[i]];
    int humanr = ranger[S[i]];
    /*
    std::cout << "query "<<i<<": ";
    std::cout<<S[i]<<" "<<E[i]<<" ";
    std::cout << "human array range [" << humanl << ", " << humanr << "] see see if any element in [" << l << ", " << r << "], ";
    */
    int res = wlt.upper_bound(humanl + 1, humanr + 1, r + 1);
    /*
    int res = -1;
    for(int i = humanl; i <= humanr; i++) {
      if(A[i] <= r) res = std::max(res, A[i]);
    }
    */
    /*
    std::cout << "res=" << res<<"\n";
    */
    if(res != -1 && l <= res && res <= r) {
      Answer[i] = 1;
    }
    else {
      Answer[i] = 0;
    }
    
  }
  return Answer;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19540 KB Output is correct
2 Correct 10 ms 19456 KB Output is correct
3 Correct 10 ms 19412 KB Output is correct
4 Correct 14 ms 19412 KB Output is correct
5 Correct 14 ms 19540 KB Output is correct
6 Correct 10 ms 19520 KB Output is correct
7 Correct 9 ms 19540 KB Output is correct
8 Correct 11 ms 19488 KB Output is correct
9 Correct 13 ms 19508 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19540 KB Output is correct
2 Correct 10 ms 19456 KB Output is correct
3 Correct 10 ms 19412 KB Output is correct
4 Correct 14 ms 19412 KB Output is correct
5 Correct 14 ms 19540 KB Output is correct
6 Correct 10 ms 19520 KB Output is correct
7 Correct 9 ms 19540 KB Output is correct
8 Correct 11 ms 19488 KB Output is correct
9 Correct 13 ms 19508 KB Output is correct
10 Correct 16 ms 22192 KB Output is correct
11 Correct 18 ms 22068 KB Output is correct
12 Correct 18 ms 22064 KB Output is correct
13 Correct 18 ms 22316 KB Output is correct
14 Correct 24 ms 22288 KB Output is correct
15 Correct 18 ms 22220 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1064 ms 203564 KB Output is correct
2 Correct 1192 ms 213040 KB Output is correct
3 Correct 1237 ms 208364 KB Output is correct
4 Correct 1116 ms 206356 KB Output is correct
5 Correct 1042 ms 206348 KB Output is correct
6 Correct 1056 ms 206348 KB Output is correct
7 Correct 774 ms 206320 KB Output is correct
8 Correct 1184 ms 213360 KB Output is correct
9 Correct 874 ms 208352 KB Output is correct
10 Correct 635 ms 206304 KB Output is correct
11 Correct 686 ms 206452 KB Output is correct
12 Correct 695 ms 206360 KB Output is correct
13 Correct 1142 ms 213376 KB Output is correct
14 Correct 1148 ms 213500 KB Output is correct
15 Correct 1126 ms 213388 KB Output is correct
16 Correct 1230 ms 213416 KB Output is correct
17 Correct 823 ms 206320 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19540 KB Output is correct
2 Correct 10 ms 19456 KB Output is correct
3 Correct 10 ms 19412 KB Output is correct
4 Correct 14 ms 19412 KB Output is correct
5 Correct 14 ms 19540 KB Output is correct
6 Correct 10 ms 19520 KB Output is correct
7 Correct 9 ms 19540 KB Output is correct
8 Correct 11 ms 19488 KB Output is correct
9 Correct 13 ms 19508 KB Output is correct
10 Correct 16 ms 22192 KB Output is correct
11 Correct 18 ms 22068 KB Output is correct
12 Correct 18 ms 22064 KB Output is correct
13 Correct 18 ms 22316 KB Output is correct
14 Correct 24 ms 22288 KB Output is correct
15 Correct 18 ms 22220 KB Output is correct
16 Correct 1064 ms 203564 KB Output is correct
17 Correct 1192 ms 213040 KB Output is correct
18 Correct 1237 ms 208364 KB Output is correct
19 Correct 1116 ms 206356 KB Output is correct
20 Correct 1042 ms 206348 KB Output is correct
21 Correct 1056 ms 206348 KB Output is correct
22 Correct 774 ms 206320 KB Output is correct
23 Correct 1184 ms 213360 KB Output is correct
24 Correct 874 ms 208352 KB Output is correct
25 Correct 635 ms 206304 KB Output is correct
26 Correct 686 ms 206452 KB Output is correct
27 Correct 695 ms 206360 KB Output is correct
28 Correct 1142 ms 213376 KB Output is correct
29 Correct 1148 ms 213500 KB Output is correct
30 Correct 1126 ms 213388 KB Output is correct
31 Correct 1230 ms 213416 KB Output is correct
32 Correct 823 ms 206320 KB Output is correct
33 Correct 1263 ms 207580 KB Output is correct
34 Correct 541 ms 54972 KB Output is correct
35 Correct 1407 ms 213000 KB Output is correct
36 Correct 1190 ms 206908 KB Output is correct
37 Correct 1330 ms 211592 KB Output is correct
38 Correct 1223 ms 208056 KB Output is correct
39 Correct 1336 ms 221248 KB Output is correct
40 Correct 1123 ms 220412 KB Output is correct
41 Correct 995 ms 210472 KB Output is correct
42 Correct 770 ms 206916 KB Output is correct
43 Correct 1447 ms 219412 KB Output is correct
44 Correct 1226 ms 211540 KB Output is correct
45 Correct 940 ms 221760 KB Output is correct
46 Correct 1181 ms 221268 KB Output is correct
47 Correct 1120 ms 213628 KB Output is correct
48 Correct 1174 ms 213420 KB Output is correct
49 Correct 1145 ms 213724 KB Output is correct
50 Correct 1111 ms 213416 KB Output is correct
51 Correct 978 ms 221036 KB Output is correct
52 Correct 1000 ms 221040 KB Output is correct