Submission #1171888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171888		Zero_OP	Werewolf (IOI18_werewolf)	C++20	0 / 100	342 ms	55900 KiB

werewolf

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define compact(v) v.erase(unique(all(v)), end(v))

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

typedef long long ll;

using db = double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;

using vi = vector<int>;
using vl = vector<ll>;
using vc = vector<char>;
using vd = vector<db>;
using vb = vector<bool>;

using vpi = vector<pi>;
using vpl = vector<pl>;

void setIO(){
      ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
#endif
}

#ifndef LOCAL
      #include "werewolf.h"
#endif

struct DSU_Tree{
      vi lab, tin, tout;
      int timer_dfs, used;
      vector<vi> adj;

      DSU_Tree(int n, int m) : timer_dfs(0), used(n), lab(n + m, -1), tin(n + m, -1), tout(n + m, -1), adj(n + m) {}

      int root(int u){
            return lab[u] < 0 ? u : (lab[u] = root(lab[u]));
      }

      void join(int u, int v){
            u = root(u); v = root(v);
            adj[used].pb(u);
            if(u != v) adj[used].pb(v);

            lab[used] = lab[u] + lab[v];
            lab[u] = used; lab[v] = used;
            ++used;
      }

      void dfs(int u){
            tin[u] = ++timer_dfs;
            for(auto v : adj[u]){
                  dfs(v);
            }
            tout[u] = timer_dfs;
      }

      void process(){
            dfs(used-1);
      }
};

struct Fenwick{
      vi bit;
      Fenwick(int n) : bit(n + 1, 0) { }

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

      int query(int id){
            int sum = 0;
            for(; id > 0; id -= id & (-id)) sum += bit[id];
            return sum;
      }

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

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) {
      int Q = sz(S);
      int M = sz(X);

      vi result(Q, 1);

      vector<tuple<int, int, int>> events;
      FOR(i, 0, M){
            events.eb(min(X[i], Y[i]), X[i], Y[i]);
      }

      FOR(i, 0, Q){
            events.eb(L[i], -1, i);
      }

      sort(rall(events));

      vector<array<int, 2>> cover(Q, {-1, -1}), left(Q, {-1, -1}), right(Q, {-1, -1});
      vi x(N), y(N);

//      cout << "Human part : \n";

      DSU_Tree dsu(N, M);
      for(auto [w, i, j] : events){
            if(i == -1){ //query
//                  cout << "query : " << j << '\n';
                  int s = dsu.root(S[j]);
                  cover[j][0] = s;
            } else{ //edges
//                  cout << "edge : " << i << ' ' << j << '\n';
                  dsu.join(i, j);
            }
      }

      dsu.process();

      FOR(i, 0, Q){
            if(cover[i][0] != -1){
                  left[i][0] = dsu.tin[cover[i][0]];
                  right[i][0] = dsu.tout[cover[i][0]];
            }
      }

      FOR(i, 0, N) x[i] = dsu.tin[i];

//      exit(0);
//      return {};

      dsu = DSU_Tree(N, M);
      events.clear();


      FOR(i, 0, M){
            events.eb(max(X[i], Y[i]), X[i], Y[i]);
      }

      FOR(i, 0, Q) if(result[i]){
//            cout << dbg(R[i]) << '\n';
            events.eb(R[i], -1, i);
      }

      sort(all(events));

//      cout << "Werewolf part : \n";

      for(auto [w, i, j] : events){
            if(i == -1){ //query
//                  cout << "query : " << j << '\n';
                  int e = dsu.root(E[j]);
                  cover[j][1] = e;
            } else{ //edges
//                  cout << "edge : " << i << ' ' << j << '\n';
                  dsu.join(i, j);
            }
      }

      dsu.process();

      FOR(i, 0, Q){
            if(cover[i][1] != -1){
                  left[i][1] = dsu.tin[cover[i][1]];
                  right[i][1] = dsu.tout[cover[i][1]];
            }
      }

      FOR(i, 0, N){
            y[i] = dsu.tin[i];
      }

      events.clear();
      vi cnt(Q);
      FOR(i, 0, Q){
            if(result[i]){
                  //can transform ?
                  events.eb(left[i][0]-1, 0, i);
                  events.eb(right[i][0], +1, i);
            }
      }

      FOR(i, 0, N) events.eb(x[i], -1, y[i]);

      sort(all(events));

      Fenwick BIT(N + M);
      for(auto [x, type, y] : events){
            if(type == -1) BIT.update(y, +1);
            else if(type == 0) cnt[y] -= BIT.query(left[y][1], right[y][1]);
            else cnt[y] += BIT.query(left[y][1], right[y][1]);
      }

      FOR(i, 0, Q){
//            cout << result[i] << '\n';
            if(result[i] && cnt[i] > 0) result[i] = 1;
            else result[i] = 0;
      }
      return result;
}

#ifdef LOCAL
      int main(){
            ios_base::sync_with_stdio(0); cin.tie(0);

            freopen("task.inp", "r", stdin);

            int N, M, Q;
            cin >> N >> M >> Q;

            vi X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
            FOR(i, 0, M) cin >> X[i] >> Y[i];
            FOR(i, 0, Q) cin >> S[i] >> E[i] >> L[i] >> R[i];

            vi ans = check_validity(N, X, Y, S, E, L, R);
            FOR(i, 0, Q) cout << ans[i] << '\n';

            return 0;
      }
#endif // LOCAL

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51