oj.uz

답안 #969162

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
969162 2024-04-24T15:50:04 Z duckindog 늑대인간 (IOI18_werewolf) C++17
34 / 100
 1749 ms 45824 KB 
#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;

const int N = 200'000 + 10;
vector<int> ad[N];

int a[N], rvs[N], it;
void dfs(int u, int p = -1) { 
  a[it] = u; rvs[u] = it++;
  for (const auto& v : ad[u]) if (v != p) dfs(v, u);
}

int f[N << 2][2];
void build(int s, int l, int r) { 
  if (l == r) { 
    f[s][0] = f[s][1] = a[l];
    return;
  }
  int mid = l + r >> 1;
  build(s << 1, l, mid); build(s << 1 | 1, mid + 1, r);
  f[s][0] = min(f[s << 1][0], f[s << 1 | 1][0]);
  f[s][1] = max(f[s << 1][1], f[s << 1 | 1][1]);
}
int getmi(int s, int l, int r, int u, int v) { 
  if (v < l || u > r) return 200'000;
  if (u <= l && r <= v) return f[s][0];
  int mid = l + r >> 1;
  return min(getmi(s << 1, l, mid, u, v), getmi(s << 1 | 1, mid + 1, r, u, v));
}
int getma(int s, int l, int r, int u, int v) { 
  if (v < l || u > r) return -1;
  if (u <= l && r <= v) return f[s][1];
  int mid = l + r >> 1;
  return max(getma(s << 1, l, mid, u, v), getma(s << 1 | 1, mid + 1, r, u, v));
}

vector<int> check_validity(int n, vector<int> x, vector<int> y,
                                vector<int> s, vector<int> e,
                                vector<int> l, vector<int> r) {
  int m = x.size(), q = s.size();
  bool line = true;
  for (int i = 0; i < m; ++i) { 
    int u = x[i], v = y[i];
    ad[u].push_back(v);
    ad[v].push_back(u);
    line &= (ad[u].size() <= 2 && ad[v].size() <= 2);
  }

  if (line) { 
    int root;
    for (int i = 0; i < n; ++i) if (ad[i].size() == 1) root = i;
    dfs(root);
    build(1, 0, n - 1);
    
    vector<int> answer;
    for (int i = 0; i < q; ++i) {
      if (rvs[s[i]] < rvs[e[i]]) { 
        int st = rvs[s[i]], ed = rvs[e[i]];
        int vegan = -1;
        { 
          int lt = st, rt = ed;
          while (lt <= rt) { 
            int mid = lt + rt >> 1;
            if (getma(1, 0, n - 1, mid, ed) > r[i]) lt = (vegan = mid) + 1;
            else rt = mid - 1;
          }
        }
        
        int meat = -1;
        { 
          int lt = st, rt = ed;
          while (lt <= rt) { 
            int mid = lt + rt >> 1;
            if (getmi(1, 0, n - 1, st, mid) < l[i]) rt = (meat = mid) - 1;
            else lt = mid + 1;
          }
        }
    
        if (meat == -1 || vegan == -1) { 
          answer.push_back(1);
          continue;
        }        
        
        if (meat <= vegan + 1) answer.push_back(0);
        else answer.push_back(1);

      } else { 
        int st = rvs[e[i]], ed = rvs[s[i]];
        int vegan = -1;
        { 
          int lt = st, rt = ed;
          while (lt <= rt) { 
            int mid = lt + rt >> 1;
            if (getma(1, 0, n - 1, st, mid) > r[i]) rt = (vegan = mid) - 1;
            else lt = mid + 1;
          }
        }
        
        int meat = -1;
        { 
          int lt = st, rt = ed;
          while (lt <= rt) { 
            int mid = lt + rt >> 1;
            if (getmi(1, 0, n - 1, mid, ed) < l[i]) lt = (meat = mid) + 1;
            else rt = mid - 1;;
          }
        }
        if (meat == -1 || vegan == -1) { 
          answer.push_back(1);
          continue;
        }

        if (meat >= vegan - 1) answer.push_back(0);
        else answer.push_back(1);
      }

    }
    return answer;
  }

}

Compilation message

werewolf.cpp: In function 'void build(int, int, int)':
werewolf.cpp:21:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |   int mid = l + r >> 1;
      |             ~~^~~
werewolf.cpp: In function 'int getmi(int, int, int, int, int)':
werewolf.cpp:29:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   int mid = l + r >> 1;
      |             ~~^~~
werewolf.cpp: In function 'int getma(int, int, int, int, int)':
werewolf.cpp:35:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   int mid = l + r >> 1;
      |             ~~^~~
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:65:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |             int mid = lt + rt >> 1;
      |                       ~~~^~~~
werewolf.cpp:75:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |             int mid = lt + rt >> 1;
      |                       ~~~^~~~
werewolf.cpp:95:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |             int mid = lt + rt >> 1;
      |                       ~~~^~~~
werewolf.cpp:105:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |             int mid = lt + rt >> 1;
      |                       ~~~^~~~
werewolf.cpp:123:1: warning: control reaches end of non-void function [-Wreturn-type]
  123 | }
      | ^
werewolf.cpp:54:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |     dfs(root);
      |     ~~~^~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 19 ms 31328 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 19 ms 31328 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1486 ms 45824 KB Output is correct
2 Correct 1679 ms 45556 KB Output is correct
3 Correct 1698 ms 45524 KB Output is correct
4 Correct 1678 ms 45588 KB Output is correct
5 Correct 1652 ms 45376 KB Output is correct
6 Correct 1542 ms 45612 KB Output is correct
7 Correct 1720 ms 45404 KB Output is correct
8 Correct 1743 ms 45556 KB Output is correct
9 Correct 714 ms 45612 KB Output is correct
10 Correct 931 ms 45460 KB Output is correct
11 Correct 1022 ms 45512 KB Output is correct
12 Correct 1337 ms 45576 KB Output is correct
13 Correct 1749 ms 45620 KB Output is correct
14 Correct 1720 ms 45508 KB Output is correct
15 Correct 1703 ms 45652 KB Output is correct
16 Correct 1654 ms 45548 KB Output is correct
17 Correct 1718 ms 45644 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 19 ms 31328 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -