Submission #129737

#	Time	Username	Problem	Language	Result	Execution time	Memory
129737		Talant	Werewolf (IOI18_werewolf)	C++17	34 / 100	2912 ms	33640 KiB

werewolf

#include <bits/stdc++.h>

#define a first
#define b second
#define pb push_back
#define mk make_pair
#define node pair<int,int>

using namespace std;

const int NN = (2e5 + 5);
const int inf = (1e9 + 7);

int n,q,m;
int dev[NN];
int l = -1,r;
int a[NN],pos[NN],cn;
node t[NN * 4],cr;
int used[NN];
vector <int> ans,g[NN];

node combine(node a,node b) {
      a.a = max(a.a,b.a);
      a.b = min(a.b,b.b);
      return a;
}
void build (int v = 1,int tl = 1,int tr = n) {
      if (tl == tr) {
            t[v].a = t[v].b = a[tl];
      }
      else {
            int tm = (tl + tr) >> 1;
            build (v + v,tl,tm);
            build (v + v + 1,tm + 1,tr);
            t[v] = combine(t[v + v],t[v + v + 1]);
      }
}
node get (int l,int r,int v = 1,int tl = 1,int tr = n) {
      if (tl > r || tr < l) return {0,inf};
      if (l <= tl && tr <= r) return t[v];
      int tm = (tl + tr) >> 1;
      return combine(get(l,r,v + v,tl,tm),get(l,r,v + v + 1,tm + 1,tr));
}
void Dfs (int v,int mx,int f) {
      used[v] += f;
      for (auto to : g[v]) {
            if (used[to] >= f) continue;
            if (f == 1) {
                  if (to >= mx) Dfs(to,mx,f);
            }
            else {
                  if (to <= mx) Dfs(to,mx,f);
            }
      }
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E, vector<int> L, vector<int> R) {

      n = N,q = S.size(),m = X.size();

      for (int i = 0; i < m; i ++)
            X[i] ++,Y[i] ++;
      for (int i = 0; i < q; i ++)
            S[i] ++,E[i] ++,L[i] ++,R[i] ++;
      if (m == n - 1) {
            for (int i = 0; i < m; i ++) {
                  g[X[i]].pb(Y[i]);
                  g[Y[i]].pb(X[i]);
                  dev[X[i]] ++;
                  dev[Y[i]] ++;
            }
            for (int i = 1; i <= n; i ++) {
                  if (dev[i] == 1 && l == -1) l = i;
                  else if (dev[i] == 1) r = i;
            }
            int cur = l;
            while (cur != r) {
                  a[++cn] = cur;
                  pos[cur] = cn;
                  if (a[cn - 1] != g[cur][0]) cur = g[cur][0];
                  else cur = g[cur][1];
            }
            a[++cn] = r;
            pos[r] = cn;

            build();
            for (int i = 0; i < q; i ++) {
                  int aa = S[i],bb = E[i],sl = L[i],sr = R[i];
                  if (pos[aa] <= pos[bb]) {
                        int lo = pos[aa],hi = pos[bb];
                        while (hi - lo > 1) {
                              int md = (hi + lo) >> 1;
                              cr = get(pos[aa],md);
                              if (cr.b >= sl) lo = md;
                              else hi = md;
                        }
                        cr = get(pos[aa],hi);
                        if (cr.b >= sl) lo = hi;

                        l = pos[aa],r = pos[bb];
                        while (r - l > 1) {
                              int md = (r + l) >> 1;
                              cr = get(md,pos[bb]);
                              if (cr.a <= sr) r = md;
                              else l = md;
                        }
                        cr = get(l,pos[bb]);
                        if (cr.a <= sr) r = l;
                        if (r <= lo) ans.pb(1);
                        else ans.pb(0);
                  }
                  else {
                        int lo = pos[bb],hi = pos[aa];
                        while (hi - lo > 1) {
                              int md = (hi + lo) >> 1;
                              cr = get(pos[bb],md);
                              if (cr.a <= sr) lo = md;
                              else hi = md;
                        }
                        cr = get(pos[bb],hi);
                        if (cr.a <= sr) lo = hi;

                        l = pos[bb],r = pos[aa];
                        while (r - l > 1) {
                              int md = (r + l) >> 1;
                              cr = get(md,pos[aa]);
                              if (cr.b >= sl) r = md;
                              else l = md;
                        }
                        cr = get(l,pos[aa]);

                        if (cr.b >= sl) r = l;

                        if (r <= lo) ans.pb(1);
                        else ans.pb(0);
                  }
            }
            return ans;
      }

      else {
            for (int i = 0; i < m; i ++) {
                  g[X[i]].pb(Y[i]);
                  g[Y[i]].pb(X[i]);
            }
             for (int i = 0; i < q; i ++) {
                  int aa = S[i],bb = E[i],sl = L[i],sr = R[i];
                  Dfs(aa,sl,1);
                  Dfs(bb,sr,2);
                  int o = 0;
                  for (int i = 1; i <= n; i ++) {
                        if (used[i] == 3) o = 1;
                  }
                  ans.pb(o);
             }
             return ans;
      }
}

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