oj.uz

답안 #1009694

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1009694 2024-06-27T21:12:46 Z HappyCapybara 늑대인간 (IOI18_werewolf) C++17
0 / 100
 1155 ms 36988 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;

int n;
vector<int> stx, stn;

void updatex(int pos, int val, int node=1, int tl=0, int tr=n-1){
  if (tl == tr){
    stx[node] = val;
    return;
  }
  int tm = (tl+tr)/2;
  if (pos <= tm) updatex(pos, val, node*2, tl, tm);
  else updatex(pos, val, node*2+1, tm+1, tr);
  stx[node] = max(stx[node*2], stx[node*2+1]);
}

int queryx(int l, int r, int node=1, int tl=0, int tr=n-1){
  if (l <= tl && tr <= r) return stx[node];
  int tm = (tl+tr)/2;
  int res = -1;
  if (l <= tm) res = max(res, queryx(l, r, node*2, tl, tm));
  if (tm+1 <= r) res = max(res, queryx(l, r, node*2+1, tm+1, tr));
  return res;
}

void updaten(int pos, int val, int node=1, int tl=0, int tr=n-1){
  if (tl == tr){
    stn[node] = val;
    return;
  }
  int tm = (tl+tr)/2;
  if (pos <= tm) updaten(pos, val, node*2, tl, tm);
  else updaten(pos, val, node*2+1, tm+1, tr);
  stn[node] = min(stn[node*2], stn[node*2+1]);
}

int queryn(int l, int r, int node=1, int tl=0, int tr=n-1){
  if (l <= tl && tr <= r) return stn[node];
  int tm = (tl+tr)/2;
  int res = 200000;
  if (l <= tm) res = min(res, queryn(l, r, node*2, tl, tm));
  if (tm+1 <= r) res = min(res, queryn(l, r, node*2+1, tm+1, tr));
  return res;
}

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;
  vector<vector<int>> g(N);
  for (int i=0; i<X.size(); i++){
    g[X[i]].push_back(Y[i]);
    g[Y[i]].push_back(X[i]);
  }
  vector<bool> seen(N, false);
  int cur;
  for (int i=0; i<N; i++){
    if (g[i].size() == 1){
      cur = i;
      break;
    }
  }
  stx = {};
  stx.resize(4*N, -1);
  stn = {};
  stn.resize(4*N, 200000);
  int pos = 0;
  vector<int> v(N);
  while (true){
    seen[cur] = true;
    updatex(pos, cur);
    updaten(pos, cur);
    v[cur] = pos;
    pos++;
    for (int next : g[cur]){
      if (!seen[next]) cur = next;
    }
    if (seen[cur]) break;
  }

  vector<int> A(S.size(), 0);
  for (int i=0; i<S.size(); i++){
    int s = v[S[i]], e = v[E[i]];
    if (s > e) swap(s, e);
    int l = s, r = e+1;
    while (l != r-1){
      int m = (l+r)/2;
      if (queryn(m, r-1) > L[i]) l = m;
      else r = m;
    }
    int rh = l;
    l = s; r = e+1;
    while (l != r-1){
      int m = (l+r)/2;
      if (queryx(l, m-1) < R[i]) r = m;
      else l = m;
    }
    int lw = l;
    if (lw < rh) A[i] = 1;
  }
  return A;
}

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:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for (int i=0; i<X.size(); i++){
      |                 ~^~~~~~~~~
werewolf.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for (int i=0; i<S.size(); i++){
      |                 ~^~~~~~~~~
werewolf.cpp:70:13: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |     seen[cur] = true;
      |             ^

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1155 ms 36988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -