제출 #283054

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
283054		milleniumEeee	늑대인간 (IOI18_werewolf)	C++14	0 / 100	4051 ms	118404 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define prev prev123
#define pii pair<int, int>
#define fr first
#define sc second
using namespace std;
typedef vector<int> vi;

const int MAXN = (int)2e5 + 5;
const int MAXM = (int)4e5 + 5;
const int MAXQ = (int)2e5 + 5;

vector <int> g[MAXN];
int N, M, Q;

struct Query {
  int s, e, l, r; 
  Query (int s_, int e_, int l_, int r_) {
    s = s_, e = e_, l = l_, r = r_;
  }
  Query () {

  }
}query[MAXQ];

struct Small_Solve {
  vector <int> ans;
  bool need() {
    return (N <= 3000 && M <= 6000 && Q <= 3000);
  }
  void solve() {
    ans.resize(Q, 0);
    vector <int> used[3];
    used[1].resize(N, 0);
    used[2].resize(N, 0);
    int cnt = 0;
    for (int i = 0; i < Q; i++) {
      cnt++;
      queue <int> q[3];
      if (query[i].s >= query[i].l) {
        q[1].push(query[i].s);
      }
      if (query[i].e <= query[i].r) {
        q[2].push(query[i].e);
      }
      while (!q[1].empty()) {
        int v = q[1].front();
        q[1].pop();
        if (used[1][v] == cnt) {
          continue;
        }
        used[1][v] = cnt;
        for (int to : g[v]) {
          if (to >= query[i].l) {
            q[1].push(to);
          }
        }
      }
      while (!q[2].empty()) {
        int v = q[2].front();
        q[2].pop();
        if (used[2][v] == cnt) {
          continue;
        }
        used[2][v] = cnt;
        for (int to : g[v]) {
          if (to <= query[i].r) {
            q[2].push(to);
          }
        }
      }
      int found = 0;
      for (int v = 0; v < N; v++) {
        found |= (used[1][v] == cnt && used[2][v] == cnt);
      }
      ans[i] = found;
    }
  }
}subtask12;

struct Line_Solve {
  int start = -1, finish = -1;
  pii table[20][(int)2e5 + 5];
  int pows[20];

  Line_Solve() {
    pows[0] = 1;
    for (int i = 0; i < 20; i++) {
      pows[i] = pows[i - 1] * 2;
    }
  }

  vector <int> ans;
  bool need() {
    if (M != N - 1) {
      return false;
    }
    for (int i = 0; i < N; i++) {
      if (szof(g[i]) == 1) {
        if (start == -1) {
          start = i;
        } else {
          finish = i;
        }
      }
    }
    return true;
  }
  pii merge(pii &a, pii &b) {
    return {min(a.fr, b.fr), max(a.sc, b.sc)};
  }
  bool in(int l1, int r1, int l2, int r2) { // l1...r1 in l2...r2
    return (l2 <= l1 && r1 <= r2);
  }
  pii get(int l, int r) {
    if (l == r) {
      return table[0][l];
    } else {
      int pw = log2(r - l + 1);
      return merge(table[pw][l], table[pw][r - pows[pw] + 1]);
    }
  };

  pii get_segment(int our_pos, int L, int R) {
    pii segment = {-1, -1};
    int l = -1, r = our_pos;
    while (r - l > 1) {
      int mid = l + r >> 1;
      pii pr = get(mid, our_pos);
      if (in(pr.fr, pr.sc, L, R)) {
        r = mid;
      } else {
        l = mid;
      }
    }
    segment.fr = r;
    l = our_pos, r = N;
    while (r - l > 1) {
      int mid = l + r >> 1;
      pii pr = get(our_pos, mid);
      if (in(pr.fr, pr.sc, L, R)) {
        l = mid;
      } else {
        r = mid;
      }
    }
    segment.sc = l;
    return segment;
  }

  void solve() {
    vector <int> pos(N);
    vector <int> convert(N);
    ans.resize(Q);
    int id = 0, prev = -1;
    int now = start;
    
    if (start == -1 || finish == -1 || start == finish) {
      while (1) {
        
      }
    }

    //cout << "Q: " << Q << endl;
    //puts("ok");

    while (1) {
      pos[now] = id++;
      convert[pos[now]] = now;
      if (now == finish) {
        break;
      }
      for (int to : g[now]) {
        if (to != prev) {
          prev = now, now = to;
        }
      }
    }

    for (int pw = 0; pw < 20; pw++) {
      for (int i = 0; i < N; i++) {
        if (pw == 0) {
          table[pw][i] = {convert[i], convert[i]};
        } else if (i + pows[i] - 1 < N) {
          table[pw][i] = merge(table[pw - 1][i], table[pw - 1][i + pows[pw - 1]]);
        }
      }
    }
    for (int i = 0; i < Q; i++) {
      if ((query[i].s >= query[i].l && query[i].e <= query[i].r) == false) {
        ans[i] = 0;
        continue;
      }
      pii segment[3];
      segment[1] = get_segment(query[i].s, query[i].l, N - 1);
      segment[2] = get_segment(query[i].e, 0, query[i].r);
      ans[i] = !(segment[1].fr > segment[2].sc || segment[2].fr > segment[1].sc);
    }
  }
}subtask3;


vi check_validity(int NN, vi X, vi Y, vi S, vi E, vi L, vi R) {
  N = NN;
  M = szof(X);
  Q = szof(S);
  for (int i = 0; i < M; i++) {
    g[X[i]].push_back(Y[i]);
    g[Y[i]].push_back(X[i]);
  }
  for (int i = 0; i < Q; i++) {
    query[i] = Query(S[i], E[i], L[i], R[i]);
  }
  /*if (subtask12.need()) {
    subtask12.solve();
    return subtask12.ans;
  }*/
  if (subtask3.need()) {
    subtask3.solve();
    return subtask3.ans;
  }
  while (1) {

  }
}

컴파일 시 표준 에러 (stderr) 메시지

werewolf.cpp: In member function 'std::pair<int, int> Line_Solve::get_segment(int, int, int)':
werewolf.cpp:131:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  131 |       int mid = l + r >> 1;
      |                 ~~^~~
werewolf.cpp:142:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  142 |       int mid = l + r >> 1;
      |                 ~~^~~

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