Submission #275152

#	Time	Username	Problem	Language	Result	Execution time	Memory
275152		cjoa	Werewolf (IOI18_werewolf)	C++11	34 / 100	1425 ms	37980 KiB

werewolf

#include "werewolf.h"
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <cassert>
#include <iostream>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;

const int INF = 1000000000;
struct SegmentTree {
   int N;
   vector<int> MIN, MAX;
   SegmentTree(const vector<int>& A) {
      N = A.size();
      MIN = vector<int>(4*N);
      MAX = vector<int>(4*N);
      build(A, 1, 0, N-1);
   }
   void build(const vector<int>& A, int node, int L, int R) {
      if (L == R) {
         MIN[node] = A[L];
         MAX[node] = A[L];
         return;
      }
      int mid = (L + R)/2;
      build(A, node*2, L, mid);
      build(A, node*2+1, mid+1, R);
      MIN[node] = min(MIN[node*2], MIN[node*2+1]);
      MAX[node] = max(MAX[node*2], MAX[node*2+1]);
   }
   int query_min(int qL, int qR) {
      return query_min(qL, qR, 1, 0, N-1);
   }
   int query_min(int qL, int qR, int node, int L, int R) {
      if (qR < L || qL > R) return +INF;
      if (qL <= L && R <= qR) return MIN[node];
      int mid = (L + R)/2;
      return min(query_min(qL, qR, node*2, L, mid),
                 query_min(qL, qR, node*2+1, mid+1, R));
   }
   int query_max(int qL, int qR) {
      return query_max(qL, qR, 1, 0, N-1);
   }
   int query_max(int qL, int qR, int node, int L, int R) {
      if (qR < L || qL > R) return -INF;
      if (qL <= L && R <= qR) return MAX[node];
      int mid = (L + R)/2;
      return max(query_max(qL, qR, node*2, L, mid),
                 query_max(qL, qR, node*2+1, mid+1, R));
   }
};

VVI get_graph(int N, const VI& X, const VI& Y) {
   VVI G(N);
   int M = X.size();
   for (int j = 0; j < M; ++j) {
      int u = X[j], v = Y[j];
      G[u].push_back(v);
      G[v].push_back(u);
   }
   return G;
}

VI bfs(int N, VVI& adj, int src, int dst) {
   queue<int> q;
   q.push(src);
   VI D(N, INF);
   D[src] = 0;
   VI P(N, -1);
   while (!q.empty()) {
      int u = q.front(); q.pop();
      if (u == dst) {
         VI path;
         for (int x = dst; x >= 0; x = P[x])
            path.push_back(x);
         reverse(path.begin(), path.end());
         return path;
      }
      for (int v : adj[u]) {
         if (D[v] > D[u] + 1) {
            D[v] = D[u] + 1;
            P[v] = u;
            q.push(v);
         }
      }
   }
   return {};
}

bool is_subtask3(int N, int M, VVI& adj, VI& line) {
   if (M != N-1)
      return false;

   VI nodes_deg1;
   for (int u = 0; u < N; ++u) {
      if (adj[u].size() > 2)
         return false;
      if (adj[u].size() == 1)
         nodes_deg1.push_back(u);
   }
   assert(nodes_deg1.size() == 2);
   
   line = bfs(N, adj, nodes_deg1[0], nodes_deg1[1]);
   assert(line.size() == N);

   return true;
}

bool query(SegmentTree& st, const VI& line, const VI& pos,
           int src, int dst, int L, int R) {
   int src_pos = pos[src], dst_pos = pos[dst];
   if (src_pos < dst_pos) {
      // de izquierda a derecha

      if (st.query_min(src_pos, dst_pos) >= L)
         return true;

      // binary search para encontrar el primer nodo (a la derecha de src_pos)
      // mas pequenio que L
      int lo = src_pos, hi = dst_pos;
      int m = -1;
      while (lo <= hi) {
         int mid = (lo + hi) / 2;
         int cur = st.query_min(lo, mid);
         if (cur < L) {
            m = mid;
            hi = mid-1;
         }
         else {
            lo = mid+1;
         }
      }

      assert(m != -1 && m > src_pos);
      assert(line[m-1] >= L);

      // m es la posicion del primer nodo mas pequenio que L
      if (line[m-1] > R)
         return false;

      if (st.query_max(m, dst_pos) > R)
         return false;

   }
   else {
      // de derecha a izquierda

      if (st.query_min(dst_pos, src_pos) >= L)
         return true;

      // binary search para encontrar el primer nodo (a la izquierda de src_pos)
      // mas pequenio que L
      int lo = dst_pos, hi = src_pos;
      int m = -1;
      while (lo <= hi) {
         int mid = (lo + hi) / 2;
         if (st.query_min(mid, hi) < L) {
            m = mid;
            lo = mid+1;
         }
         else {
            hi = mid-1;
         }
      }
      assert(m != -1 && m < src_pos);
      assert(line[m+1] >= L);

      // m es la posicion del primer nodo mas pequenio que L
      if (line[m+1] > R)
         return false;

      if (st.query_max(dst_pos, m) > R)
         return false;
   }

   
   return true;
}

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();
   std::vector<int> res(Q);

   VVI adj = get_graph(N, X, Y);

   VI line;
   if (is_subtask3(N, X.size(), adj, line)) {
      VI pos(N);
      for (int i = 0; i < N; ++i) {
         int u = line[i];
         pos[u] = i;
      }
      SegmentTree st(line);
      for (int q = 0; q < Q; ++q) {
         res[q] = query(st, line, pos, S[q], E[q], L[q], R[q]);
      }
      return res;
   }

   for (int i = 0; i < Q; ++i) {
      res[i] = rand() % 2;
   }
   return res;
}

Compilation message (stderr)

In file included from /usr/include/c++/9/cassert:44,
                 from werewolf.cpp:5:
werewolf.cpp: In function 'bool is_subtask3(int, int, VVI&, VI&)':
werewolf.cpp:108:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  108 |    assert(line.size() == N);
      |           ~~~~~~~~~~~~^~~~

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