Submission #318643

#	Time	Username	Problem	Language	Result	Execution time	Memory
318643		ivan_tudor	Werewolf (IOI18_werewolf)	C++14	100 / 100	1106 ms	111744 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
vector<int> gr[N];
vector<int> amin[N], amax[N];
int dmin[20][N], dmax[20][N];
int pmin[N], pmax[N];
int findt(int x, int p[]){
  if(x == p[x])
    return x;
  p[x] = findt(p[x], p);
  return p[x];
}
void join (int x, int y, int p[], int d[20][N]){ // x tatal de care unesc pe fiul y
  if(findt(x,p) != findt(y,p)){
    y = findt(y,p);
    p[y] = x;
    d[0][y] = x;
  }
}

struct intv{
  int l,r;
};
intv itvmin[N];
int postord[N];
void dfsmin(int nod,int dad, int &cnt){
  cnt++;
  itvmin[nod].l = cnt;
  postord[cnt] = nod;
  for(auto x: amin[nod]){
    if(x!=dad){
      dfsmin(x,nod,cnt);
    }
  }
  itvmin[nod].r = cnt;
}

intv itvmax[N];
void dfsmax(int nod,int dad, int &cnt){
  cnt++;
  itvmax[nod].l = cnt;
  for(auto x: amax[nod]){
    if(x!=dad){
      dfsmax(x,nod,cnt);
    }
  }
  itvmax[nod].r = cnt;
}

struct querys{
  int l;
  int c1,c2;
  int type;
  int id;
};
bool cmpquerys(querys a, querys b){
  return a.l < b.l;
}

int aib[N];
void update(int poz,int val){
  for(int i = poz; i < N ; i+= i&(-i))
    aib[i] += val;
}
int query(int poz){
  int ans = 0;
  for(int i=poz; i>0; i-= i&(-i))
    ans+=aib[i];
  return ans;
}

std::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< X.size(); i++){
    gr[X[i] + 1].push_back(Y[i] + 1);
    gr[Y[i] + 1].push_back(X[i] + 1);
  }
  for(int i=1;i<=n;i++){
    pmin[i] = pmax[i] = i;
  }
  for(int i=1; i<=n;i++){
    for(auto j:gr[i]){
      if(j < i){
        join(i, j, pmax, dmax);
      }
    }
  }
  for(int i=1; i<=n; i++){
    amax[dmax[0][i]].push_back(i);
    amax[i].push_back(dmax[0][i]);
  }
  int cnt = 0;
  dfsmax(n, 0, cnt);
  for(int i = n; i>=1; i--){
    for(auto j:gr[i]){
      if(j > i){
        join(i, j, pmin, dmin);
      }
    }
  }
  cnt = 0;
  for(int i=1; i<=n; i++){
    amin[dmin[0][i]].push_back(i);
    amin[i].push_back(dmin[0][i]);
  }
  dfsmin(1, 0, cnt);
  for(int log = 1; log < 20; log ++){
    for(int i= 1; i<=n;i++){
      dmin[log][i] = dmin[log-1][dmin[log-1][i]];
      dmax[log][i] = dmax[log-1][dmax[log-1][i]];
    }
  }
  int Q = S.size();
  vector<querys> q;
  for(int i = 0 ; i < Q ; i++){
    int s = S[i] + 1;
    int e = E[i] + 1;
    int l = L[i] + 1;
    int r = R[i] + 1;

    for(int pas = 19; pas >= 0; pas--){
      if(dmin[pas][s]!=0 && dmin[pas][s] >= l)
        s = dmin[pas][s];
    }
    intv mn = itvmin[s];
    for(int pas = 19; pas>=0; pas--){
      if(dmax[pas][e]!=0 && dmax[pas][e] <= r)
        e = dmax[pas][e];
    }
    intv mx = itvmax[e];
    q.push_back({mn.l-1, mx.l, mx.r, -1, i});
    q.push_back({mn.r, mx.l, mx.r, 1, i});
  }
  std::vector<int> A(Q);
  sort(q.begin(),q.end(),cmpquerys);
  int pc = 1;
  for(auto qc:q){
    while(pc <= qc.l){
      update(itvmax[postord[pc]].l, 1);
      pc++;
    }
    A[qc.id] += qc.type * (query(qc.c2) - query(qc.c1 - 1));
  }
  for(auto &a: A)
    if(a > 0)
      a = 1;
    else
      a = 0;
  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:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for(int i = 0; i< X.size(); i++){
      |                  ~^~~~~~~~~~

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