#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int VAL = 500;
const int MAXN = 2e5+5;
#define pb push_back
#define fr first
#define sc second
int pai[MAXN], sz[MAXN];
vector<int> alt;
int find(int x) {
if(pai[x] == x) return x;
alt.pb(x);
return pai[x] = find(pai[x]);
}
void join(int x, int y) {
x = find(x);
y = find(y);
if(x == y) return;
alt.pb(x);
alt.pb(y);
if(sz[x] < sz[y]) {
pai[x] = y;
sz[y] += sz[x];
}
else {
pai[y] = x;
sz[x] += sz[y];
}
}
vector<int> check_validity(int n, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
vector<pii> edges;
vector<vector<int>> graph(n);
for(int i = 0; i < X.size(); i++) {
if(X[i] > Y[i]) swap(X[i], Y[i]);
edges.pb({X[i],Y[i]});
graph[Y[i]].pb(X[i]);
}
sort(edges.begin(), edges.end());
reverse(edges.begin(), edges.end());
vector<vector<int>> query(n);
for(int i = 0; i < S.size(); i++)
if(S[i] >= L[i] and E[i] <= R[i])
query[R[i]].pb(i);
vector<int> ans(S.size()), pre_calc(n), calc(n);
for(int i = 0; i < edges.size(); i++) {
if(i == 0) pre_calc[0] = X[0];
else pre_calc[i] = min(pre_calc[i-1], X[i]);
}
for(int i = 0; i < n; i++)
pai[i] = i, sz[i] = 1;
//for(auto [a,b] : edges) cout << a << " " << b << "\n";
for(int i = 0, c = 0; i < edges.size(); i++) {
if(VAL * c == i) {
vector<int> save_pai(n), save_sz(n), aux_pai(n), aux_sz(n);
for(int j = 0; j < n; j++)
save_pai[j] = aux_pai[j] = pai[j], save_sz[j] = aux_sz[j] = sz[j];
for(int j = 0; j < n; j++) {
for(int viz : graph[j])
join(j,viz);
// cout << "testando r = " << j << "\n";
// for(int A = 0; A < n; A++)
// cout << pai[A] << " \n"[A==n-1];
for(int it : alt)
aux_pai[it] = pai[it], aux_sz[it] = sz[it];
alt.clear();
for(int l : query[j]) {
if(L[l] < pre_calc[min(i+VAL-1,n-1)] or calc[l]) continue;
for(int k = i; k < min(n, i + VAL); k++)
if(edges[k].fr >= L[l]) join(edges[k].fr, edges[k].sc);
else break;
// for(int A = 0; A < n; A++)
// cout << pai[A] << " \n"[A==n-1];
// cout << "calculo " << j << "\n";
if(find(S[l]) == find(E[l])) ans[l] = 1;
for(int it : alt)
pai[it] = aux_pai[it], sz[it] = aux_sz[it];
alt.clear();
calc[l] = 1;
}
}
for(int j = 0; j < n; j++)
pai[j] = save_pai[j], sz[j] = save_sz[j];
c++;
}
join(edges[i].fr, edges[i].sc);
alt.pop_back();
}
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:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i = 0; i < X.size(); i++) {
| ~~^~~~~~~~~~
werewolf.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int i = 0; i < S.size(); i++)
| ~~^~~~~~~~~~
werewolf.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int i = 0; i < edges.size(); i++) {
| ~~^~~~~~~~~~~~~~
werewolf.cpp:68:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i = 0, c = 0; i < edges.size(); i++) {
| ~~^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1643 ms |
79576 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
