Submission #130227

#	Time	Username	Problem	Language	Result	Execution time	Memory
130227		Talant	Werewolf (IOI18_werewolf)	C++17	49 / 100	2904 ms	52124 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 fl = 0;
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 man (int v,int mx) {
      if (v < mx) return;
      used[v] = 1;
      for (auto to : g[v])
            if (!used[to] && to >= mx) man(to,mx);
}
void wolf(int v,int mx) {
      if (v > mx) return;
      if (used[v] || fl) {
            fl = 1;
            return;
      }
      used[v] = 2;
      for (auto to : g[v])
            if (used[to] != 2 && to <= mx) wolf(to,mx);
}
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 (n <= 3000 && m <= 6000 && q <= 3000) {
            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];
                  for (int i = 1; i <= n; i ++)
                        used[i] = 0;
                  man(aa,sl);
                  wolf(bb,sr);

                  ans.pb(fl);
                  fl = 0;
             }
             return ans;
      }
      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;


}

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