oj.uz

Submission #1038868

# Submission time Handle Problem Language Result Execution time Memory
1038868 2024-07-30T08:31:08 Z Mr_Husanboy Werewolf (IOI18_werewolf) C++17
34 / 100
 599 ms 524288 KB 
#include "werewolf.h"
#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
#define ll long long

template<typename T>
int len(T &a){return a.size();}

const int inf = 1e9 + 10;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

struct DSU{
  vector<int> par, sz; int n;
  DSU (int _n){
    n = _n;
    par.resize(n);
    iota(all(par), 0);
    sz.assign(n, 1);
  }
  DSU (){}
  int get(int a){
    return (par[a] == a ? a : par[a] = get(par[a]));
  }

  void init(int _n){
    n = _n;
    par.resize(n);
    iota(all(par), 0);
    sz.assign(n, 1);
  }

  void unite(int a, int b){
    a = get(a);
    b = get(b);
    if(a == b) return;
    if(sz[a] < sz[b]) swap(a,b);
    sz[a] += sz[b];
    par[b] = a;
  }

  void link(int a, int b){
    a = get(a); b = get(b);
    if(a == b) return;
    sz[b] += sz[a];
    par[a] = b;
  }
};

int n, m, q;
vector<vector<int>> g;
vector<int> line;

void dfs(int i, int p = -1){
  line.push_back(i);
  for(auto u : g[i]){
    if(u != p) dfs(u, i);
  }
}

struct Sparsemin{
  int n, logn;
  vector<vector<int>> t;
  Sparsemin (){}
  void init(int _n){
    n = _n;
    logn = 32 - __builtin_clz(n);
    t.assign(logn, vector<int> (n));
  }

  int merge(int a, int b){
    return min(a, b);
  }

  void build(vector<int> &a){    
    init(len(a));
    //cout << n << endl;
    for(int i = 0; i < n; i ++) t[0][i] = a[i];
    for(int j = 1; j < logn; j ++){
      for(int i = 0; i + (1 << j) - 1 < n; i ++){
        t[j][i] = merge(t[j - 1][i], t[j - 1][i + (1 << (j - 1))]);
      }
    }
  }

  int get(int l, int r){
    if(l > r) return inf;
    int k = 31 - __builtin_clz(r - l + 1);
    return merge(t[k][l], t[k][r - (1 << k) + 1]);
  }
};


struct Sparsemax{
  int n, logn;
  vector<vector<int>> t;
  Sparsemax (){}
  void init(int _n){
    n = _n;
    logn = 32 - __builtin_clz(n);
    t.assign(logn, vector<int> (n));
  }

  int merge(int a, int b){
    return max(a, b);
  }

  void build(vector<int> &a){
    init(len(a));
    //cout<< n << endl;
    for(int i = 0; i < n; i ++) t[0][i] = a[i];
    for(int j = 1; j < logn; j ++){
      for(int i = 0; i + (1 << j) - 1 < n; i ++){
        t[j][i] = merge(t[j - 1][i], t[j - 1][i + (1 << (j - 1))]);
      }
    }
  }

  int get(int l, int r){
    if(l > r) return -inf;
    int k = 31 - __builtin_clz(r - l + 1);
    return merge(t[k][l], t[k][r - (1 << k) + 1]);
  }
};



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) {
  n = N;
  q = len(s);
  m = len(x);
  vector<int> res(q);
  g.resize(n);
  for(int i = 0; i < m; i ++){
    g[x[i]].push_back(y[i]);
    g[y[i]].push_back(x[i]);
  }

  int mn = 0;
  for(int i = 0; i < n; i++) if(len(g[i]) == 1) {mn = i; break;}
  dfs(mn);

  Sparsemin hum; Sparsemax wolf;  
  hum.build(line); wolf.build(line);
  vector<int> pos(n);
  for(int i = 0; i < n; i++) pos[line[i]] = i;
  for(int i = 0; i < q; i ++){
    s[i] = pos[s[i]];
    e[i] = pos[e[i]];
    int lb = -1, rb = s[i];
    while(rb - lb > 1){
      int mid = (lb + rb) / 2;
      if(hum.get(mid, s[i]) < l[i]){
        lb = mid;
      }else rb = mid;
    }
    int hl = rb;
    lb = s[i], rb = n;
    while(rb - lb > 1){
      int mid = (lb + rb) / 2;
      if(hum.get(s[i], mid) < l[i]){
        rb = mid;
      }else lb = mid;
    }
    int hr = lb;

    lb = -1, rb = e[i];

    while(rb - lb > 1){
      int mid = (lb + rb) / 2;
      if(wolf.get(mid, e[i]) > r[i]){
        lb = mid;
      }else rb = mid;
    }
    int wl = rb;
    lb = e[i], rb = n;
    while(rb - lb > 1){
      int mid = (lb + rb) / 2;
      if(wolf.get(e[i], mid) > r[i]){
        rb = mid;
      }else lb = mid;
    }
    int wr = lb;
    //cout << hl << '-' << hr << ' ' << wl << ' ' << wr << endl;
    res[i] = not(wl > hr || hl > wr);
  }
  return res;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 306 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 306 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 599 ms 64900 KB Output is correct
2 Correct 387 ms 69344 KB Output is correct
3 Correct 397 ms 69048 KB Output is correct
4 Correct 411 ms 69044 KB Output is correct
5 Correct 453 ms 69044 KB Output is correct
6 Correct 474 ms 69048 KB Output is correct
7 Correct 447 ms 69044 KB Output is correct
8 Correct 385 ms 69092 KB Output is correct
9 Correct 241 ms 68980 KB Output is correct
10 Correct 278 ms 69048 KB Output is correct
11 Correct 308 ms 69044 KB Output is correct
12 Correct 277 ms 69092 KB Output is correct
13 Correct 396 ms 69044 KB Output is correct
14 Correct 414 ms 69048 KB Output is correct
15 Correct 390 ms 69044 KB Output is correct
16 Correct 405 ms 69044 KB Output is correct
17 Correct 437 ms 68956 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 306 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -