#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
vector<vector<int>> g,atj;
int n;
struct Event{
int s,e,l,r;
int id;
pair<int,int> per;
Event(int A,int B,int C,int D,int E){
s = A;
e = B;
l = C;
r = D;
id = E;
}
};
vector<int> dsu;
vector<vector<int>> fr,to;
int T;
void addEdge(int u,int v){
g[u].push_back(v);
g[v].push_back(u);
}
int To;
void init(int n,int x){
dsu = vector<int> (2*n+x);
T = 0;
g.clear();
g.resize(2*n);
To = n;
iota(dsu.begin()+x,dsu.end(),x);
}
int find(int u){
return u == dsu[u] ? u : dsu[u] = find(dsu[u]);
}
void merge(int u,int v){
u = find(u);
v = find(v);
if(u == v)return;
addEdge(u,To);
addEdge(v,To);
// cerr << u << ' ' << v << ' ' << To << '\n';
dsu[v] = To;
dsu[u] = To;
To++;
}
void dfs(int u,int p,bool t){
fr[t][u] = ++T;
// cerr << "- " << t << ' ' << u << '\n';
for(int v : g[u]){
if(v == p)continue;
dfs(v,u,t);
}
to[t][u] = T;
}
int p,q;
const int nax = 4e5 + 100;
vector<int> seg[nax];
vector<int> val;
void build(int n = 1,int s = 1,int e = ::n*2){
if(s == e){
seg[n].push_back(val[s]);
return;
}
build(n+n,s,(s+e)/2);
build(n+n+1,(s+e)/2+1,e);
int a=0,b=0;
seg[n].clear();
while(a < seg[n+n].size() || b < seg[n+n+1].size()){
if(a == seg[n+n].size())seg[n].push_back(seg[n+n+1][b++]);
else if(b == seg[n+n+1].size())seg[n].push_back(seg[n+n][a++]);
else if(seg[n+n][a] < seg[n+n+1][b])seg[n].push_back(seg[n+n][a++]);
else seg[n].push_back(seg[n+n+1][b++]);
}
}
int get(int l,int r,int L,int R,int n=1,int s = 1,int e = ::n*2){
if(s > r || e < l || l > r)return 0;
if(s >= l && e <= r){
int fr = lower_bound(all(seg[n]) , L) - seg[n].begin();
int to = upper_bound(all(seg[n]) , R) - seg[n].begin();
to--;
return to - fr + 1;
}
return get(l,r,L,R,n+n,s,(s+e)/2) + get(l,r,L,R,n+n+1,(s+e)/2+1,e);
}
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;
vector<Event> e;
atj.resize(n);
for(int i=0;i<x.size();i++){
atj[x[i]].push_back(y[i]);
atj[y[i]].push_back(x[i]);
}
fr = to = vector<vector<int>>(2,vector<int>(2*n));
for(int i=0;i<S.size();i++){
e.push_back(Event(S[i] , E[i] , L[i] , R[i] , i));
}
{//Build X axis
init(n,0);
sort(all(e) , [](Event a,Event b){
return a.l > b.l;
});
int u = n-1;
for(int i=0;i<e.size();i++){
for(;u>=e[i].l;u--){
for(int v : atj[u]){
if(v > u)
merge(u,v);
}
}
e[i].per.first = find(e[i].s);
}
for(;u>=0;u--){
for(int v : atj[u]){
if(v > u)
merge(u,v);
}
}
dfs(To-1,-1,0);
}
{//Build Y axis
init(n,0);
sort(all(e) , [](Event a,Event b){
return a.r < b.r;
});
int u = 0;
for(int i=0;i<e.size();i++){
for(;u<=e[i].r;u++){
for(int v : atj[u]){
if(v < u)
merge(u,v);
}
}
e[i].per.second = find(e[i].e);
}
for(;u<=n-1;u++){
for(int v : atj[u]){
if(v < u)
merge(u,v);
}
}
dfs(To-1,-1,1);
}
val.resize(n*2+1);
for(int i=0;i<2*n;i++){
// cerr << fr[0][i] << ' ' << val.size() << '\n';
val[fr[0][i]] = fr[1][i];
}
// return {};
build();
vector<int> A(S.size() , 0);
// return {};
for(int i=0;i<e.size();i++){
int id = e[i].per.first;
int id2 = e[i].per.second;
p = fr[1][id2];
q = to[1][id2];
// cerr << i << ' ' << id << ' ' << fr[0][id] << ' ' << to[0][id] << '\n';
A[e[i].id] = get(fr[0][id] , to[0][id],p,q) > 0;
}
// cerr << "WTF\n";
return A;
}
Compilation message
werewolf.cpp: In function 'void build(int, int, int)':
werewolf.cpp:87:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | while(a < seg[n+n].size() || b < seg[n+n+1].size()){
| ~~^~~~~~~~~~~~~~~~~
werewolf.cpp:87:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | while(a < seg[n+n].size() || b < seg[n+n+1].size()){
| ~~^~~~~~~~~~~~~~~~~~~
werewolf.cpp:88:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | if(a == seg[n+n].size())seg[n].push_back(seg[n+n+1][b++]);
| ~~^~~~~~~~~~~~~~~~~~
werewolf.cpp:89:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | else if(b == seg[n+n+1].size())seg[n].push_back(seg[n+n][a++]);
| ~~^~~~~~~~~~~~~~~~~~~~
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:114:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for(int i=0;i<x.size();i++){
| ~^~~~~~~~~
werewolf.cpp:119:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(int i=0;i<S.size();i++){
| ~^~~~~~~~~
werewolf.cpp:128:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for(int i=0;i<e.size();i++){
| ~^~~~~~~~~
werewolf.cpp:153:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | for(int i=0;i<e.size();i++){
| ~^~~~~~~~~
werewolf.cpp:179:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
179 | for(int i=0;i<e.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
790 ms |
144076 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
