Submission #729636

#TimeUsernameProblemLanguageResultExecution timeMemory
729636t6twotwoWerewolf (IOI18_werewolf)C++17
15 / 100
200 ms71636 KiB
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; 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(); int Q = S.size(); vector<vector<int>> adj(N); for (int i = 0; i < M; i++) { adj[X[i]].push_back(Y[i]); adj[Y[i]].push_back(X[i]); } if (N <= 3000 && M <= 6000 && Q <= 3000) { vector<int> p(N); function<int(int)> find = [&](int x) { return x == p[x] ? x : p[x] = find(p[x]); }; vector<vector<int>> s(N); auto unite = [&](int x, int y) { x = find(x); y = find(y); if (x == y) { return; } if (s[x].size() > s[y].size()) { swap(x, y); } for (int z : s[x]) { p[z] = y; s[y].push_back(z); } }; for (int i = 0; i < N; i++) { p[i] = i; s[i] = {i}; } vector hi(N, vector<int>(N, -1)); for (int x = N - 1; x >= 0; x--) { hi[x][x] = x; for (int y : adj[x]) { if (y < x || find(x) == find(y)) { continue; } for (int u : s[find(x)]) { for (int v : s[find(y)]) { hi[u][v] = x; hi[v][u] = x; } } unite(x, y); } } for (int i = 0; i < N; i++) { p[i] = i; s[i] = {i}; } vector lo(N, vector<int>(N, -1)); for (int x = 0; x < N; x++) { lo[x][x] = x; for (int y : adj[x]) { if (y > x || find(x) == find(y)) { continue; } for (int u : s[find(x)]) { for (int v : s[find(y)]) { lo[u][v] = x; lo[v][u] = x; } } unite(x, y); } } vector<int> ans(Q); for (int i = 0; i < Q; i++) { for (int j = L[i]; j <= R[i]; j++) { if (hi[S[i]][j] >= L[i] && lo[j][E[i]] <= R[i]) { ans[i] = 1; } } } return ans; } else { vector<int> A; for (int i = 0; i < N; i++) { if (adj[i].size() == 1) { A.push_back(i); A.push_back(adj[i][0]); break; } } while (A.size() < N) { int x = A[A.size() - 2]; int y = A[A.size() - 1]; A.push_back(adj[y][0] ^ adj[y][1] ^ x); } vector<int> B(N); for (int i = 0; i < N; i++) { B[A[i]] = i; } vector<int> ans(Q); for (int i = 0; i < Q; i++) { if (S[i] < L[i] || E[i] > R[i]) { continue; } int x = B[S[i]], u = -1; int y = B[E[i]], v = -1; if (x < y) { u = x; assert(A[u] >= L[i]); while (u + 1 <= y && A[u + 1] >= L[i]) { u++; } v = y; assert(A[v] <= R[i]); while (v - 1 >= x && A[v - 1] <= R[i]) { v--; } } else { u = x; assert(A[u] <= R[i]); while (u + 1 <= y && A[u + 1] <= R[i]) { u++; } v = y; assert(A[v] >= L[i]); while (v - 1 >= x && A[v - 1] >= L[i]) { v--; } } if (v <= u) { ans[i] = 1; } } return ans; } }

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:90:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   90 |         while (A.size() < N) {
      |                ~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...