Submission #826913

#	Time	Username	Problem	Language	Result	Execution time	Memory
826913		peteza	Werewolf (IOI18_werewolf)	C++14	100 / 100	494 ms	103520 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
 
vector<int> adj[200005];
vector<int> ladj[400005], radj[400005];
int pl[400005], pr[400005];
int pls, prs, cur;
int llabel[400005], rlabel[400005];
pair<int, int> rngl[400005], rngr[400005];
int fenw[400005];
bool vis[400005];
 
int qr(int x) {
  int s = 0;
  for(;x;x-=x&-x) s += fenw[x];
  return s;
}
 
void upd(int x) {
  for(;x<=400000;x+=x&-x) fenw[x]++;
}
 
int fpar(int *parr, int x) {
  return parr[x] == x ? x : (parr[x] = fpar(parr, parr[x]));
}
 
void dfs(vector<int>* adj, pair<int, int>* rngarr, int *lab, int x) {
  rngarr[x].first = cur;// cout << x << ' ';
  if(adj[x].empty()){lab[x] = cur; rngarr[x].second=cur++; return;}
  for(int e:adj[x]) dfs(adj, rngarr, lab, e);
  rngarr[x].second = cur-1;
}
 
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
  for(int i=0;i<=400000;i++) pl[i] = pr[i] = i;
  int Q = S.size(); pls = prs = N;
  vector<int> A(Q, 0);
  vector<pair<int, int>> ls(Q), rs(Q);
  vector<int> lnode(Q), rnode(Q);
  for(int i=0;i<Q;i++) ls[i] = {L[i], i};
  for(int i=0;i<Q;i++) rs[i] = {R[i], i};
  for(int i=0;i<N;i++) ls.emplace_back(i, INT_MAX), rs.emplace_back(i, INT_MIN);
  sort(ls.rbegin(), ls.rend()); sort(rs.begin(), rs.end());
  vector<pair<int, int>> points;
  for(int i=0;i<X.size();i++) {
    adj[X[i]].push_back(Y[i]);
    adj[Y[i]].push_back(X[i]);
  }
  for(auto e:ls) {
    if(e.second == INT_MAX) { //merge
      ladj[pls].push_back(e.first); pl[e.first] = pls;
      for(int E:adj[e.first]) {
        if(E <= e.first) continue;
        if(fpar(pl, E) == pls) continue;
        ladj[pls].push_back(fpar(pl, E));
        pl[fpar(pl, E)] = pls; 
      }
      pls++;
    } else {
      lnode[e.second] = fpar(pl, S[e.second]);
    }
  }
  for(auto e:rs) {
    if(e.second == INT_MIN) { //merge
      radj[prs].push_back(e.first); pr[e.first] = prs;
      for(int E:adj[e.first]) {
        if(E >= e.first) continue;
        if(fpar(pr, E) == prs) continue;
        radj[prs].push_back(fpar(pr, E));
        pr[fpar(pr, E)] = prs;
      }
      prs++;
    } else {
      rnode[e.second] = fpar(pr, E[e.second]);
    }
  } pls--; prs--; //pls, prs == root of left and right respectively
  //for(int i=0;i<=pls;i++) {cout << i << ": "; for(int e:ladj[i]) cout << e << ' '; cout << '\n';}
  cur = 1; dfs(ladj, rngl, llabel, pls); 
  cur = 1; dfs(radj, rngr, rlabel, prs);
  for(int i=0;i<N;i++) points.emplace_back(llabel[i], rlabel[i]);
  for(int i=0;i<Q;i++) points.emplace_back(rngl[lnode[i]].first-1, N+i+1), points.emplace_back(rngl[lnode[i]].second, N+i+1);
  //cout << "Helhloe";
  sort(points.begin(), points.end());
  for(auto e:points) {
    if(e.second > N) {
      int ci = e.second-N-1; //query number
      A[ci] += (vis[ci] ? 1 : -1) * (qr(rngr[rnode[ci]].second) - qr(rngr[rnode[ci]].first-1));
      vis[ci] = 1; A[ci] = min(A[ci], 1);
    } else {
      upd(e.second);
    }
  }
  return A;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:46:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for(int i=0;i<X.size();i++) {
      |               ~^~~~~~~~~

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