Submission #729563

#TimeUsernameProblemLanguageResultExecution timeMemory
729563t6twotwoWerewolf (IOI18_werewolf)C++17
15 / 100
370 ms524288 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]); } 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...