#include "werewolf.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 3e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
set<ii> poss;
// comp1[]: from high to low, this guy is at component from this time to that time
vector<ii> comp1[N], comp2[N];
int n;
vector<int> Adj[N];
int sz[N], rt[N];
vector<int> nodes[N];
int root(int x){
return (x == rt[x] ? x : rt[x] = root(rt[x]));
}
bool ck = 0;
void merge(int x, int y, int ti){
//cout << "OK " << x << " " << y << " " << ti << "\n";
x = root(x), y = root(y);
if(x == y) return;
if(sz[x] < sz[y]) swap(x, y);
for(auto it : nodes[y]){
if(!ck){
while(comp1[it].size() && comp1[it].back().fi == ti) comp1[it].pop_back();
comp1[it].pb({ti, x});
}
else{
while(comp2[it].size() && comp2[it].back().fi == ti) comp2[it].pop_back();
comp2[it].pb({ti, x});
}
nodes[x].pb(it);
}
nodes[y].clear();
sz[x] += sz[y];
rt[y] = x;
}
int cnt;
struct chash{
int operator()(const ii&a)const{
return (a.fi * 43920342 + a.se);
}
};
unordered_map<ii, int, chash> uomp;
vector<ii> vc[N * 10];
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
n = N;
for(int i = 0; i < X.size(); i++){
Adj[X[i] + 1].pb(Y[i] + 1);
Adj[Y[i] + 1].pb(X[i] + 1);
}
ck = 0;
for(int i = n; i >= 1; i--){
//comp1[i].pb({n + 1, -1});
comp1[i].pb({i, i});
sz[i] = 1, rt[i] = i;
nodes[i].pb(i);
for(auto it : Adj[i]){
if(it < i) continue;
merge(i, it, i);
}
}
ck = 1;
for(int i = 1; i <= n; i++){
comp1[i].pb({0, 0});
sz[i] = 0, rt[i] = 0, nodes[i].clear();
}
for(int i = 1; i <= n; i++){
comp2[i].pb({i, i});
sz[i] = 1, rt[i] = i, nodes[i].pb(i);
for(auto it : Adj[i]){
if(it > i) continue;
merge(i, it, i);
}
}
for(int i = 1; i <= n; i++) comp2[i].pb({n + 1, 0});
for(int node = 1; node <= n; node++){
for(int i = 0; (i + 1) < comp1[node].size(); i++){
for(int j = 0; (j + 1) < comp2[node].size(); j++){
// cout << node << " " << comp1[node][i].fi << " " << comp1[node][i].se << " " << comp2[node][j].fi << " " << comp2[node][j].se << "\n";
if(uomp.find({comp1[node][i].se, comp2[node][j].se}) == uomp.end()){
cnt++;
uomp[{comp1[node][i].se, comp2[node][j].se}] = cnt;
}
vc[uomp[{comp1[node][i].se, comp2[node][j].se}]].pb({comp1[node][i].fi, comp2[node][j].fi});
//ii seg = {comp1[node][i + 1].fi + 1, comp1[node][i].fi};
//seg.fi = max(seg.fi, comp2[node][j].fi);
//seg.se = min(seg.se, comp2[node][j + 1].fi - 1);
//if(seg.fi > seg.se) continue;
//upd(1, 1, n, seg.fi, seg.se, {comp1[node][i].se, comp2[node][j].se});
}
}
}
for(int i = 1; i <= cnt; i++){
sort(vc[i].begin(), vc[i].end());
vector<ii> temp;
for(auto it : vc[i]){
while(temp.size() && temp.back().se >= it.se) temp.pop_back();
temp.pb(it);
}
vc[i] = temp;
}
vector<int> answ(S.size());
for(int i = 0; i < S.size(); i++){
S[i]++, E[i]++, L[i]++, R[i]++;
ii mn = {oo, oo};
for(auto it : comp1[S[i]]) if(it.fi >= L[i]) mn = min(mn, it);
ii mx = {-oo, -oo};
for(auto it : comp2[E[i]]) if(it.fi <= R[i]) mx = max(mx, it);
// cout << mn.se << " " << mx.se << " " << L[i] << " " << R[i] << "\n";
if(uomp.find({mn.se, mx.se}) == uomp.end()) answ[i] = 0;
else{
int temp = uomp[{mn.se, mx.se}];
vector<ii>::iterator it = lower_bound(vc[temp].begin(), vc[temp].end(), make_pair(mn.se, -oo));
if(it == vc[temp].end() || (*it).se > R[i]) answ[i] = 0;
else answ[i] = 1;
}
}
return answ;
}
Compilation message
werewolf.cpp:19:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
19 | const int oo = 1e18 + 7, mod = 1e9 + 7;
| ~~~~~^~~
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:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int i = 0; i < X.size(); i++){
| ~~^~~~~~~~~~
werewolf.cpp:104:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int i = 0; (i + 1) < comp1[node].size(); i++){
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~
werewolf.cpp:105:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(int j = 0; (j + 1) < comp2[node].size(); j++){
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~
werewolf.cpp:130:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | for(int i = 0; i < S.size(); i++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
98844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
98844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4054 ms |
360572 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
98844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
