#include <bits/stdc++.h>
using namespace std;
class UnionFind {
public:
vector<int> par;
void init(int size_) {
par.resize(size_, -1);
}
int root(int pos) {
if (par[pos] == -1) return pos;
par[pos] = root(par[pos]);
return par[pos];
}
void unite(int u, int v) {
u = root(u); v = root(v);
if (u != v) par[u] = v;
}
bool same(int u, int v) {
if (root(u) == root(v)) return true;
return false;
}
};
int N, M, Q, X[1 << 18], Y[1 << 18], S[1 << 18], E[1 << 18], L[1 << 18], R[1 << 18], dp[1 << 18][2];
vector<int> G[1 << 18];
vector<int> check_validity (int NN, vector<int> XX, vector<int> YY, vector<int> SS, vector<int> EE, vector<int> LL, vector<int> RR) {
// ------------------------------- 1. Input Data -------------------------------------
N = NN; M = XX.size(); Q = SS.size();
for (int i = 0; i < M; i++) X[i] = XX[i];
for (int i = 0; i < M; i++) Y[i] = YY[i];
for (int i = 0; i < Q; i++) S[i] = SS[i];
for (int i = 0; i < Q; i++) E[i] = EE[i];
for (int i = 0; i < Q; i++) L[i] = LL[i];
for (int i = 0; i < Q; i++) R[i] = RR[i];
for (int i = 0; i < M; i++) { if (X[i] < Y[i]) swap(X[i], Y[i]); }
// ------------------------------- 2. Make Tree --------------------------------------
vector<pair<int, int>> vec;
for (int i = 0; i < M; i++) vec.push_back(make_pair(X[i], Y[i]));
sort(vec.begin(), vec.end());
UnionFind UF; UF.init(N);
for (int i = 0; i < vec.size(); i++) {
if (UF.same(vec[i].first, vec[i].second) == false) {
G[vec[i].first].push_back(vec[i].second);
G[vec[i].second].push_back(vec[i].first);
UF.unite(vec[i].first, vec[i].second);
}
}
// ----------------------- 3. Calculate (15-points solution) ------------------------
vector<int>ans;
for (int i = 0; i < Q; i++) {
for (int j = 0; j < N; j++) { dp[j][0] = 0; dp[j][1] = 0; }
queue<pair<int, int>> que; dp[S[i]][0] = 1; que.push(make_pair(S[i], 0));
while (!que.empty()) {
int pos1 = que.front().first, pos2 = que.front().second; que.pop();
if (L[i] <= pos1 && pos1 <= R[i] && dp[pos1][1] == 0 && pos2 == 0) {
dp[pos1][1] = 1; que.push(make_pair(pos1, 1));
}
for (int j = 0; j < G[pos1].size(); j++) {
int to = G[pos1][j];
if (pos2 == 0 && to < L[i]) continue;
if (pos2 == 1 && R[i] < to) continue;
if (dp[to][pos2] == 0) { dp[to][pos2] = 1; que.push(make_pair(to, pos2)); }
}
}
ans.push_back(dp[E[i]][1]);
}
return ans;
}
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:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vec.size(); i++) {
~~^~~~~~~~~~~~
werewolf.cpp:67:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < G[pos1].size(); j++) {
~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
6528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
6528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4025 ms |
31276 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
6528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
