Submission #130924

#	Time	Username	Problem	Language	Result	Execution time	Memory
130924		rondojim	Werewolf (IOI18_werewolf)	C++17	34 / 100	1572 ms	34932 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int INF = 1e8;
 
struct segTree {
  int N; vector<int> lows,highs;
  segTree(int N): N(N), lows(2*N,INF), highs(2*N,-1) {}
  pair<int,int> find(int a, int b) {
    a += N; b += N;
    if (a > b) swap(a,b);
    int low = INF, high = -1;
    while (a <= b) {
      if (a%2 == 1) {
        low = min(low,lows[a]);
        high = max(high,highs[a]);
        a++;
      }
      if (b%2 == 0) {
        low = min(low,lows[b]);
        high = max(high,highs[b]);
        b--;
      }
      a /= 2; b /= 2;
    }
    return make_pair(low,high);
  }
  void upd(int i, int x) {
    i += N;
    lows[i] = highs[i] = x;
    for (i /= 2; i > 0; i /= 2) {
      lows[i] = min(lows[2*i], lows[2*i+1]);
      highs[i] = max(highs[2*i], highs[2*i+1]);
    }
  }
};
 
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R) {
 
  int Q = S.size();
 
  vector<vector<int>> adj(N);
  
  for (int i = 0; i < N; i++) {
    adj[X[i]].push_back(Y[i]);
    adj[Y[i]].push_back(X[i]);
  }
 
  int end;
  for (int i = 0; i < N; i++) if (adj[i].size() == 1) end = i;
 
  int j = 0; 
  int cur = end; int pre = -1;
 
  vector<int> order {end}, index(N);
  segTree st(N);
  st.upd(0,end);
 
  for (int i = 1; i < N; i++) {
    int nxt = (adj[cur][0] == pre ? adj[cur][1] : adj[cur][0]);
    pre = cur;
    cur = nxt;
    index[nxt] = order.size();
    order.push_back(nxt);
    st.upd(i,nxt);
  }
 
  vector<int> A(Q,0);
 
  
 
  for (int q = 0; q < Q; q++) {
 
    S[q] = index[S[q]];
    E[q] = index[E[q]];
 
    int swap = 1;
    if (S[q] > E[q]) {
      swap = -1;
    }
 
    int high = abs(E[q]-S[q])+1;
 
    //find the most human can walk from start
 
    int goHuman = -1; 
 
    for (int b = high/2; b > 0; b /= 2) {
      while (goHuman + b < high && st.find(S[q],S[q]+(goHuman+b)*swap).first >= L[q]) goHuman += b; 
    }
 
 
    int goWolf = -1; 
 
    for (int b = high/2; b > 0; b /= 2) {
      while (goWolf + b < high && st.find(E[q]-(goWolf+b)*swap,E[q]).second <= R[q]) goWolf += b;
    }
 
 
 
    if (goWolf >= 0 && goHuman >= 0 && goWolf+goHuman >= abs(E[q]-S[q])) A[q] = 1;
    else A[q] = 0;
  }
 
  return A;
}

Compilation message (stderr)

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:54:7: warning: unused variable 'j' [-Wunused-variable]
   int j = 0; 
       ^
werewolf.cpp:51:7: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int end;
       ^~~

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