oj.uz

Submission #1032580

# Submission time Handle Problem Language Result Execution time Memory
1032580 2024-07-24T03:14:29 Z HappyCapybara Werewolf (IOI18_werewolf) C++17
34 / 100
 1294 ms 37104 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;
  }
  /*for (int x : v) cout << x << " ";
  cout << "\n";*/

  vector<int> A(S.size(), 0);
  for (int i=0; i<S.size(); i++){
    int s = v[S[i]], e = v[E[i]];
    //cout << s << " " << e << "\n";
    if (s < e){
      int l = s, r = e+1;
      while (l != r-1){
        int m = (l+r)/2;
        if (queryn(l, m) >= 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(m-1, r-1) <= R[i]) r = m;
        else l = m;
      }
      int lw = l;
      //cout << lw << " " << rh << "\n";
      if (lw <= rh) A[i] = 1;
    }
    else {
      int l = e, r = s+1;
      while (l != r-1){
        int m = (l+r)/2;
        if (queryx(l, m) <= R[i]) l = m;
        else r = m;
      }
      int rw = l;
      l = e; r = s+1;
      while (l != r-1){
        int m = (l+r)/2;
        if (queryn(m-1, r-1) >= L[i]) r = m;
        else l = m;
      }
      int lh = l;
      //cout << lh << " " << rw << "\n";
      if (lh <= rw) 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:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   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

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1137 ms 35372 KB Output is correct
2 Correct 1233 ms 37100 KB Output is correct
3 Correct 1294 ms 36948 KB Output is correct
4 Correct 1205 ms 37096 KB Output is correct
5 Correct 1204 ms 36944 KB Output is correct
6 Correct 1117 ms 37088 KB Output is correct
7 Correct 1053 ms 37092 KB Output is correct
8 Correct 1136 ms 37096 KB Output is correct
9 Correct 481 ms 36944 KB Output is correct
10 Correct 623 ms 36952 KB Output is correct
11 Correct 641 ms 36944 KB Output is correct
12 Correct 795 ms 37104 KB Output is correct
13 Correct 1090 ms 36948 KB Output is correct
14 Correct 1174 ms 36944 KB Output is correct
15 Correct 1252 ms 37096 KB Output is correct
16 Correct 1215 ms 37100 KB Output is correct
17 Correct 1210 ms 36864 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -