Submission #1209109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209109		vincentbucourt1	Werewolf (IOI18_werewolf)	C++20	0 / 100	769 ms	204172 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second

struct Query {
  int iQ, from, to, humanLB, wolfUB;
};
struct SumQ {
  int human, wolfL, wolfR, iq, sign;
};
bool cmpSumQ (const SumQ& a, const SumQ& b) {
  return tie(a.human, a.wolfL, a.wolfR) < tie(b.human, b.wolfL, b.wolfR);
}

int numV, numE, numQ;
vector<Query> queries;
vector<pair<int,int>> edges;
vector<int> ans;

struct DSU {
  int N;
  vector<int> par;
  DSU (int n) {
    N = n;
    par.resize(N);
    iota(par.begin(), par.end(), 0);
  }
  int find (int x) {
    if (par[x] == x) return x;
    else return par[x] = find(par[x]);
  }
  bool combine (int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    par[y] = x;
    return true;
  }
  bool sameCC (int x, int y) {
    x = find(x), y = find(y);
    return (x == y);
  }
};

struct Segtree {
  int numleaves;
  vector<int> sum;
  Segtree (int n) {
    numleaves = 1;
    while (numleaves < n) numleaves *= 2;
    sum.assign(2*numleaves, 0);
  }
  int query (int l, int r) {
    l += numleaves, r += numleaves+1;
    int res = 0;
    while (l < r) {
      if (l&1) {
        res += sum[l++];
      }
      if (r&1) {
        res += sum[--r];
      }
      l /= 2;
      r /= 2;
    }
    return res;
  }
  void update (int idx, int val) {
    idx += numleaves;
    sum[idx] += val;
    idx /= 2;
    while (idx > 0) {
      sum[idx] = sum[2*idx] + sum[2*idx+1];
      idx /= 2;
    }
  }
};

template<int (*cmp)(int, int), bool side>
struct Tree {
  vector<vector<int>> tree;
  vector<int> cmpST;
  vector<int> tIn, tOut;
  vector<vector<int>> jump;
  int t;

  bool cmpSide (int a, int b) {
    if (side) return a < b;
    else return a > b;
  }

  void dfs (int node, int par) {
    tIn[node] = t++;
    for (int child : tree[node]) {
      if (child != par) {
        jump[child][0] = node;
        dfs(child, node);
      }
    }
    tOut[node] = t-1;
  }

  int jumpQ (int node, int valQ) {
    for (int len = 31; len >= 0; len--) {
      if (cmpSide(cmpST[jump[node][len]], valQ) || valQ == cmpST[jump[node][len]]) {
        node = jump[node][len];
      }
    }
    return node;
  }
  
  Tree () {
    tree.resize(2*numV), tIn.resize(2*numV), tOut.resize(2*numV), cmpST.resize(2*numV);
    jump.resize(2*numV, vector<int>(32));
    vector<pair<int,int>> edgeList(numE);
    copy(edges.begin(), edges.end(), edgeList.begin());
    sort(edgeList.begin(), edgeList.end(), [&](const pair<int,int>& a, const pair<int,int>& b) {
      return cmpSide((*cmp)(a.f, a.s), (*cmp)(b.f, b.s));
    });
    iota(cmpST.begin(), cmpST.end(), 0);
    DSU dsu(2*numV);

    int nodeOn = numV;
    for (int iEdge = 0; iEdge < numE; iEdge++) {
      pair<int,int> edgeOn = edgeList[iEdge];
      if (!dsu.sameCC(edgeOn.f, edgeOn.s)) {
        tree[nodeOn].push_back(dsu.find(edgeOn.f));
        tree[nodeOn].push_back(dsu.find(edgeOn.s));
        cmpST[nodeOn] = (*cmp)(cmpST[dsu.find(edgeOn.f)], cmpST[dsu.find(edgeOn.s)]);
        dsu.combine(edgeOn.f, edgeOn.s);
        dsu.combine(nodeOn, edgeOn.f);
        nodeOn++;
      }
    }

    t = 0;
    for (int i = 0; i < 2*numV; i++) {
      for (int len = 0; len < 32; len++) {
        jump[i][len] = nodeOn-1;
      }
    }
    dfs(nodeOn-1, -1);
    // for (int i = 0; i < 2*numV; i++) cerr << tIn[i] << " " << tOut[i] << "\n";
    for (int len = 1; len < 32; len++) {
      for (int i = 0; i < numV; i++) {
        jump[i][len] = jump[jump[i][len-1]][len-1];
      }
    }
  }
};
int mini (int a, int b) {return min(a, b);}
int maxi (int a, int b) {return max(a, b);}

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) {
  numQ = (int)S.size();
  numV = N;
  numE = (int)X.size();
  queries.resize(numQ);
  for (int iq = 0; iq < numQ; iq++) {
    queries[iq] = Query{iq, S[iq], E[iq], L[iq], R[iq]};
  }
  edges.resize(numE);
  for (int i = 0; i < numE; i++) {
    edges[i] = make_pair(X[i], Y[i]);
  }

  Tree<mini, false> humanTree;
  // cerr << "\n";
  Tree<maxi, true> wolfTree;
  // cerr << "\n";

  vector<pair<int,int>> points;
  for (int i = 0; i < numV; i++) {
    points.push_back(make_pair(humanTree.tIn[i], wolfTree.tIn[i]));
  }
  sort(points.begin(), points.end());

  vector<SumQ> updates;
  for (int iq = 0; iq < numQ; iq++) {
    Query queryOn = queries[iq];
    int humanL = humanTree.tIn[humanTree.jumpQ(queryOn.from, queryOn.humanLB)];
    int humanR = humanTree.tOut[humanTree.jumpQ(queryOn.from, queryOn.humanLB)];
    int wolfL = wolfTree.tIn[wolfTree.jumpQ(queryOn.to, queryOn.wolfUB)];
    int wolfR = wolfTree.tOut[wolfTree.jumpQ(queryOn.to, queryOn.wolfUB)];
    updates.push_back(SumQ{humanL-1, wolfL, wolfR, iq, -1});
    updates.push_back(SumQ{humanR, wolfL, wolfR, iq, 1});
  }
  sort(updates.begin(), updates.end(), cmpSumQ);

  ans.resize(numQ);
  int iPoint = 0, iUpdate = 0;
  Segtree segQ(2*numV+1);
  for (int iHuman = -1; iHuman < 2*numV; iHuman++) {
    while (iPoint < (int)points.size() && points[iPoint].f == iHuman) {
      pair<int,int> pointOn = points[iPoint];
      segQ.update(pointOn.s, 1);
      iPoint++;
    }
    while (iUpdate < (int)updates.size() && updates[iUpdate].human == iHuman) {
      SumQ queryOn = updates[iUpdate]; 
      ans[queryOn.iq]  += queryOn.sign * segQ.query(queryOn.wolfL, queryOn.wolfR);
      iUpdate++;
    }
  }

  for (int& val : ans) {
    if (val > 0) {
      val = 1;
    }
    else {
      val = 0;
    }
  }

  return ans;
}

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