Submission #930485

# Submission time Handle Problem Language Result Execution time Memory
930485 2024-02-20T02:27:04 Z beaboss Werewolf (IOI18_werewolf) C++14
0 / 100
322 ms 101564 KB
#include "werewolf.h"

// Source: https://oj.uz/problem/view/IOI18_werewolf
// 

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i<b; i++)

bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }

bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }


const int N = 4e5 + 10;

vpii adj[N];

vi p(N + 1, -1), id(N + 1);
int cnt = 0;
vector<vi> kadj(2 * N);


int get(int x) {
  return (p[x] > 0) ? x = get(p[x]) : x;
}

void unite(int x, int y) {
  x = get(x);
  y = get(y);

  if (x == y) return;

  if (-p[x] < -p[y]) swap(x, y);

  int here = cnt++;
  kadj[here].pb(id[x]);
  kadj[here].pb(id[y]);

  // cout << x << y << ' ' << here << ' ' << id[x] << ' ' << id[y] << endl;

  p[x] += p[y];
  p[y] = x;

  id[x] = here;
}
int tin = 0;
void dfs(int cur, vi &rep, vpii &range) {
  // cout << cur << endl;
  range[cur] = {5 * N, 0};
  if (kadj[cur].size() == 0) {
    rep[cur] = tin++;
    range[cur] = {rep[cur], rep[cur]};
    return;
  }
  for (auto val: kadj[cur]) {
    dfs(val, rep, range);
    ckmin(range[cur].f, range[val].f);
    ckmax(range[cur].s, range[val].s);
  }
}

void reorder(vi &rep, vpii &range, vector<vpii> &merge, vector<vpii> &need, vi &finalid) {
  // need is what we need to update at each stage of merge
  // final is the range for each
  FOR(i, 0, N) {
    p[i]=-1;
    id[i]=i;

  }

  FOR(i, 0, 2 * N) kadj[i].clear();

  cnt = N;

  FOR(i, 0, merge.size()) {
    

    for (auto val: merge[i]) {
      // pii val = merge[i];
      unite(val.f, val.s);
      // cout <<i << ' ' << val.f << ' ' << val.s << endl;
    }


    for (auto val: need[i]) {
      // cout << i << val.f << endl;
      finalid[val.s] = id[get(val.f)];
    }

    
  }

  tin = 0;
  dfs(cnt-1, rep, range);

  // FOR(i, 0, rep.size()) cout << rep[i] << endl;


}

vi bit(N + 1);

void update(int ind, int val) {
  ind++;
  for (; ind < N; ind += ind & -ind) bit[ind] += val;
}

int pref(int l) {
  if (l < 0) return 0;
  l++;
  int res = 0;
  for (; l > 0; l -= l & -l) res += bit[l];
  return res;
}

int query(int l, int r) {
  return pref(r) - pref(l - 1);
}

vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r) {

  FOR(i, 0, x.size()) {
    adj[max(x[i], y[i])].pb({x[i], y[i]});
  }

  vector<vpii> merge(n);
  vector<vpii> need(n);

  FOR(i, 0, r.size()) {
    need[r[i]].pb({e[i], i});
  }

  FOR(i, 0, N) {
    for (auto j: adj[i]) merge[i].pb(j);

  }

  vi rep1(n);
  vpii range(2 * N + 1);
  vi finalid(r.size());

  reorder(rep1, range, merge, need, finalid);

  vpii r1;
  FOR(i, 0, finalid.size()) r1.pb(range[finalid[i]]);

  vi rep2(n);

  FOR(i, 0, n) merge[i].clear();
  FOR(i, 0, n) merge[min(x[i], y[i])].pb({x[i], y[i]});


  reverse(merge.begin(), merge.end());
  FOR(i, 0, n) need[i].clear();

  FOR(i, 0, l.size()) {
    need[n-l[i]-1].pb({s[i], i});
  }

  reorder(rep2, range, merge, need, finalid);

  vpii r2;
  FOR(i, 0, finalid.size()) r2.pb(range[finalid[i]]);

  vi in_range(e.size(), 0);

  vector<vi> add(n);
  vector<vpii> sweep(n);


  FOR(i, 0, n) add[rep1[i]].pb(i);

  FOR(i, 0, e.size()) {
    if (r1[i].f) sweep[r1[i].f-1].pb({i, -1});
    sweep[r1[i].s].pb({i, 1});
  }

  FOR(i, 0, n) {
    for (auto val: add[i]) {
      // cout << rep2[val] << endl;
      update(rep2[val], 1);
    }
    for (auto val: sweep[i]) {

      // cout << r2[val.f].f << ' ' << r2[val.f].s << ' ' << query(r2[val.f].f, r2[val.f].s) << endl;
      in_range[val.f] += query(r2[val.f].f, r2[val.f].s) * val.s;
    }
  }
  
  vi res;
  FOR(i, 0, e.size()) res.pb(in_range[i] > 0);

  // FOR(i, 0, n) cout << rep1[i] << ' ' << rep2[i] << endl;
  // FOR(i, 0, e.size()) cout << r1[i].f << r1[i].s << ' ' << r2[i].f << r2[i].s << endl;

  return res;
  
  
}

// int main() {
//  ios::sync_with_stdio(false);
//  cin.tie(nullptr);

//  vi ans = check_validity(6, {6, 1, 8, 2, 9, 2, 8, 6, 3}, {7, 5, 0, 9, 4, 7, 5, 0, 4},
// {3}, {2}, {2}, {2});

//  for (auto val: ans) cout << val << endl;

// }













Compilation message

werewolf.cpp: In function 'void reorder(vi&, vpii&, std::vector<std::vector<std::pair<int, int> > >&, std::vector<std::vector<std::pair<int, int> > >&, vi&)':
werewolf.cpp:21:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
   89 |   FOR(i, 0, merge.size()) {
      |       ~~~~~~~~~~~~~~~~~~                 
werewolf.cpp:89:3: note: in expansion of macro 'FOR'
   89 |   FOR(i, 0, merge.size()) {
      |   ^~~
werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:21:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
  136 |   FOR(i, 0, x.size()) {
      |       ~~~~~~~~~~~~~~                     
werewolf.cpp:136:3: note: in expansion of macro 'FOR'
  136 |   FOR(i, 0, x.size()) {
      |   ^~~
werewolf.cpp:21:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
  143 |   FOR(i, 0, r.size()) {
      |       ~~~~~~~~~~~~~~                     
werewolf.cpp:143:3: note: in expansion of macro 'FOR'
  143 |   FOR(i, 0, r.size()) {
      |   ^~~
werewolf.cpp:21:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
  159 |   FOR(i, 0, finalid.size()) r1.pb(range[finalid[i]]);
      |       ~~~~~~~~~~~~~~~~~~~~               
werewolf.cpp:159:3: note: in expansion of macro 'FOR'
  159 |   FOR(i, 0, finalid.size()) r1.pb(range[finalid[i]]);
      |   ^~~
werewolf.cpp:21:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
  170 |   FOR(i, 0, l.size()) {
      |       ~~~~~~~~~~~~~~                     
werewolf.cpp:170:3: note: in expansion of macro 'FOR'
  170 |   FOR(i, 0, l.size()) {
      |   ^~~
werewolf.cpp:21:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
  177 |   FOR(i, 0, finalid.size()) r2.pb(range[finalid[i]]);
      |       ~~~~~~~~~~~~~~~~~~~~               
werewolf.cpp:177:3: note: in expansion of macro 'FOR'
  177 |   FOR(i, 0, finalid.size()) r2.pb(range[finalid[i]]);
      |   ^~~
werewolf.cpp:21:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
  187 |   FOR(i, 0, e.size()) {
      |       ~~~~~~~~~~~~~~                     
werewolf.cpp:187:3: note: in expansion of macro 'FOR'
  187 |   FOR(i, 0, e.size()) {
      |   ^~~
werewolf.cpp:21:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
  205 |   FOR(i, 0, e.size()) res.pb(in_range[i] > 0);
      |       ~~~~~~~~~~~~~~                     
werewolf.cpp:205:3: note: in expansion of macro 'FOR'
  205 |   FOR(i, 0, e.size()) res.pb(in_range[i] > 0);
      |   ^~~
# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 39516 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 39516 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 322 ms 101564 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 39516 KB Output isn't correct
2 Halted 0 ms 0 KB -