oj.uz

답안 #968927

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
968927 2024-04-24T09:47:14 Z duckindog 늑대인간 (IOI18_werewolf) C++17
0 / 100
 4000 ms 51028 KB 
#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;

const int N = 200'000 + 10,
          S = 500;
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 Q[N];

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 (n <= 3000 && m <= 6000 && q <= 3000) { 
  //   vector<int> answer;
  //   for (int i = 0; i < q; ++i) { 
  //     vector<vector<bool>> f(n, vector<bool>(2));
  //     vector<int> mk(n);
      
  //     for (int j = 0; j < n; ++j) mk[j] = (j < l[i] ? 0 : j <= r[i] ? 1 : 2);

  //     queue<int> que;
  //     f[s[i]][0] = f[s[i]][mk[s[i]] == 1] = true;
  //     que.push(s[i]);
  //     while (que.size()) { 
  //       auto u = que.front(); que.pop();
  //       for (const auto& v : ad[u]) { 
  //         if (f[v][0] || f[v][1]) continue;
  //         if (mk[v] >= 1) f[v][0] = f[u][0];
  //         if (mk[v] <= 1) f[v][1] = (f[u][1] || mk[v] == 1);
  //         if (f[v][0] || f[v][1]) que.push(v);
  //       }
  //     }
      
  //     answer.push_back(f[e[i]][1]);
  //   }
  //   return answer;
  // }

  if (line) { 
    int root;
    for (int i = 0; i < n; ++i) if (ad[i].size() == 1) root = i;
    dfs(root);
    
    iota(Q, Q + q, 0);
    sort(Q, Q + q, [&](const auto& a, const auto& b) { 
      return make_pair(l[a] / S, r[a]) < make_pair(l[b] / S, r[b]);
    });

    vector<int> answer(q);
    
    set<int> w, b, h(a, a + n);
    
    int lt = 0, rt = -1;
    for (int i = 0; i < q; ++i) { 
      const auto& idx = Q[i];
      
      while (rt < r[idx]) { 
        rt += 1;
        if (h.count(rvs[rt])) h.erase(rvs[rt]);
        b.insert(rvs[rt]);
      }

      while (rt > r[idx]) { 
        if (b.count(rvs[rt])) b.erase(rvs[rt]);
        h.insert(rvs[rt]);
        rt -= 1;
      }

      while (lt > l[idx]) { 
        lt -= 1;
        if (w.count(rvs[lt])) w.erase(rvs[lt]);
        b.insert(rvs[lt]);
      }

      while (lt < l[idx]) { 
        if (b.count(rvs[lt])) b.erase(rvs[lt]);
        w.insert(rvs[lt]);
        lt += 1;
      }

      
      if (b.size() == n || !h.size()) {
        answer[idx] = 1;
        continue;
      }
      
      if (rvs[s[idx]] < rvs[e[idx]]) { 
        auto vegan = h.upper_bound(rvs[e[idx]]);
        if (vegan == h.begin()) { 
          answer[idx] = 1;
          continue;
        }
        
        vegan = prev(vegan);
        if (a[*vegan + 1] < l[idx]) continue;
        
        auto meat = w.upper_bound(*vegan);
        if (meat == w.begin() || a[*prev(meat)] > rvs[s[idx]]) answer[idx] = 1;
      } else { 
        auto vegan = h.upper_bound(rvs[e[idx]]);
        if (vegan == h.end()) { 
          answer[idx] = 1;
          continue;
        }
        
        if (a[*vegan - 1] < l[idx]) continue;

        auto meat = w.upper_bound(*vegan);
        if (meat == w.end() || a[*meat] > rvs[e[idx]]) answer[idx] = 1;
      }
      
    }
    return answer;
  }

}

Compilation message

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:99:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   99 |       if (b.size() == n || !h.size()) {
      |           ~~~~~~~~~^~~~
werewolf.cpp:133:1: warning: control reaches end of non-void function [-Wreturn-type]
  133 | }
      | ^
werewolf.cpp:59:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |     dfs(root);
      |     ~~~^~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4025 ms 51028 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

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