#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define f first
#define s second
const int maxn = 1e5 + 5e4 + 10;
int n, m, a[maxn], b[maxn];
vector<int> sexo[maxn], q[maxn];
bool ans;
struct edge{
int l, r, u, v;
edge():l(0), r(0), u(0), v(0){}
edge(int l, int r, int u, int v):l(l), r(r), u(u), v(v){}
};
class DSU{
private:
int pai[maxn], sz[maxn];
bool ok[maxn];
stack<pii> s;
public:
void init(int n){ for(int i=1; i<=n; i++) pai[i] = i, sz[i] = 1; }
int find(int x){ return pai[x] == x ? x : find(pai[x]); }
void join(int a, int b){
a = find(a), b = find(b);
if(a == b){
s.push({0, 0});
return;
}
if(sz[a] > sz[b]) swap(a, b);
pai[a] = b;
sz[b] += sz[a];
s.push({a, b});
}
void rollback(){
int a = s.top().f, b = s.top().s;
s.pop();
pai[a] = a;
sz[b] -= sz[a];
}
void att(int x, bool v){ ok[find(x)] = v; }
bool query(int x){ return ok[find(x)]; }
}dsu;
class SEG{
private:
vector<pii> tree[1<<19];
public:
void build(int n){ for(int i=1; i<=(1<<(2+(31-__builtin_clz(n)))); i++) tree[i].clear(); }
void update(int node, int tl, int tr, edge e){
if(tl > e.r or tr < e.l) return;
if(tl >= e.l and tr <= e.r){
tree[node].push_back({e.u, e.v});
return;
}
int mid = (tl + tr) >> 1;
update(2*node, tl, mid, e); update(2*node+1, mid+1, tr, e);
}
void solve(int node, int tl, int tr){
for(pii p : tree[node]) dsu.join(p.f, p.s);
if(tl == tr){
for(int x : sexo[tl]) dsu.att(x, 1);
for(int x : q[tl]) ans &= dsu.query(x);
for(int x : sexo[tl]) dsu.att(x, 0);
}
else{
int mid = (tl + tr) >> 1;
solve(2*node, tl, mid); solve(2*node+1, mid+1, tr);
}
for(pii p : tree[node]) dsu.rollback();
}
}seg;
void reset(){
dsu.init(n);
seg.build(n);
for(int i=1; i<=n; i++) sexo[i].clear(), q[i].clear();
ans = 1;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin >> t;
while(t--){
cin >> n >> m;
for(int i=1; i<=n; i++) cin >> a[i];
for(int i=1; i<=n; i++) cin >> b[i];
reset();
for(int i=1; i<=n; i++){
if(a[i] < b[i]) ans = 0;
q[b[i]].push_back(i);
sexo[a[i]].push_back(i);
}
for(int i=1; i<=m; i++){
int u, v;
cin >> u >> v;
int r = min(a[u], a[v]), l = max(b[u], b[v]);
if(l > r) continue;
edge e(l, r, u, v);
seg.update(1, 1, n, e);
}
seg.solve(1, 1, n);
cout << ans << "\n";
}
return 0;
}
Compilation message
colors.cpp: In member function 'void SEG::solve(int, int, int)':
colors.cpp:72:11: warning: variable 'p' set but not used [-Wunused-but-set-variable]
72 | for(pii p : tree[node]) dsu.rollback();
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
62 ms |
19660 KB |
Output is correct |
2 |
Correct |
29 ms |
19736 KB |
Output is correct |
3 |
Correct |
13 ms |
20044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
69 ms |
19836 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
69 ms |
19700 KB |
Output is correct |
2 |
Correct |
32 ms |
19744 KB |
Output is correct |
3 |
Correct |
15 ms |
19876 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
69 ms |
19700 KB |
Output is correct |
2 |
Correct |
32 ms |
19744 KB |
Output is correct |
3 |
Correct |
15 ms |
19876 KB |
Output is correct |
4 |
Correct |
133 ms |
19728 KB |
Output is correct |
5 |
Correct |
363 ms |
35116 KB |
Output is correct |
6 |
Correct |
595 ms |
54692 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
62 ms |
19660 KB |
Output is correct |
2 |
Correct |
29 ms |
19736 KB |
Output is correct |
3 |
Correct |
13 ms |
20044 KB |
Output is correct |
4 |
Correct |
69 ms |
19700 KB |
Output is correct |
5 |
Correct |
32 ms |
19744 KB |
Output is correct |
6 |
Correct |
15 ms |
19876 KB |
Output is correct |
7 |
Correct |
68 ms |
19660 KB |
Output is correct |
8 |
Correct |
35 ms |
19752 KB |
Output is correct |
9 |
Correct |
14 ms |
19944 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
123 ms |
19660 KB |
Output is correct |
2 |
Correct |
354 ms |
36112 KB |
Output is correct |
3 |
Correct |
365 ms |
45540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
19800 KB |
Output is correct |
2 |
Correct |
22 ms |
20056 KB |
Output is correct |
3 |
Correct |
15 ms |
19880 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
62 ms |
19660 KB |
Output is correct |
2 |
Correct |
29 ms |
19736 KB |
Output is correct |
3 |
Correct |
13 ms |
20044 KB |
Output is correct |
4 |
Correct |
69 ms |
19836 KB |
Output is correct |
5 |
Correct |
69 ms |
19700 KB |
Output is correct |
6 |
Correct |
32 ms |
19744 KB |
Output is correct |
7 |
Correct |
15 ms |
19876 KB |
Output is correct |
8 |
Correct |
133 ms |
19728 KB |
Output is correct |
9 |
Correct |
363 ms |
35116 KB |
Output is correct |
10 |
Correct |
595 ms |
54692 KB |
Output is correct |
11 |
Correct |
68 ms |
19660 KB |
Output is correct |
12 |
Correct |
35 ms |
19752 KB |
Output is correct |
13 |
Correct |
14 ms |
19944 KB |
Output is correct |
14 |
Correct |
123 ms |
19660 KB |
Output is correct |
15 |
Correct |
354 ms |
36112 KB |
Output is correct |
16 |
Correct |
365 ms |
45540 KB |
Output is correct |
17 |
Correct |
38 ms |
19800 KB |
Output is correct |
18 |
Correct |
22 ms |
20056 KB |
Output is correct |
19 |
Correct |
15 ms |
19880 KB |
Output is correct |
20 |
Correct |
96 ms |
19948 KB |
Output is correct |
21 |
Correct |
367 ms |
38792 KB |
Output is correct |
22 |
Correct |
571 ms |
69204 KB |
Output is correct |