제출 #130226

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
130226		Talant	늑대인간 (IOI18_werewolf)	C++17	34 / 100	2893 ms	95612 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 = (2e6 + 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 (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];
                  for (int i = 1; i <= n; i ++)
                        used[i] = 0;
                  man(aa,sl);
                  wolf(bb,sr);

                  ans.pb(fl);
                  fl = 0;
             }
             return ans;
      }
}

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