#include <bits/stdc++.h>
using namespace std;
int a[(int)2e5];
int b[(int)2e5];
vector<int> adj[(int)2e5];
struct DSU{
vector<int> sz, par, cm;
stack<pair<int,int>> rb;
DSU(int n){
sz.resize(n,1); par.resize(n); iota(par.begin(), par.end(),0);
cm.resize(n); for (int i=0; i<n; i++) cm[i] = a[i];
}
int get(int p) {
return par[p] == p? p: get(par[p]);
}
void unite(int u, int v){
u = get(u); v = get(v);
if (u==v){
rb.push({-1,-1}); return;
}
if (sz[u] > sz[v]) swap(u,v);
rb.push({u, cm[v]});
cm[v] = min(cm[v], cm[u]);
sz[v] += sz[u];
par[u] = v;
}
void rollback(){
int u = rb.top().first; int m = rb.top().second; rb.pop();
if (u==-1) return;
int p = par[u];
sz[p] -= sz[u];
par[u] = u;
cm[p] = m;
}
};
struct SGT{
vector<vector<pair<int,int>>> t;
int R; DSU* dsu;
SGT(int n){
dsu = new DSU(n); R = n-1; t.resize(4*n+7);
}
void add(int tl, int tr, int p, int l, int r, pair<int,int> e){
if (l>r) return;
if (tl==l && tr==r){
t[p].push_back(e); return;
}
int tm = (tl+tr)/2;
add(tl, tm, 2*p, l, min(r, tm), e);
add(tm+1, tr, 2*p+1, max(tm+1, l), r, e);
}
void add(int l, int r, pair<int,int> e){
add(0, R, 1, l, r, e);
}
void dfs(int l, int r, int p){
for (auto [u,v]: t[p]) dsu->unite(u, v);
if (l != r){
int m = (l+r)/2;
dfs(m+1, r, 2*p+1);
dfs(l, m, 2*p);
}
for (auto [u,v]: t[p]) a[u] = min(a[u], dsu->cm[dsu->get(u)]),
a[v] = min(a[v], dsu->cm[dsu->get(v)]);
for (auto [u,v]: t[p]) dsu->rollback();
}
void dfs(){
dfs(0, R, 1);
}
};
int solve(){
int n,m; cin>>n>>m;
vector<pair<int,int>> edges;
for (int i=0; i<n; i++) adj[i].clear();
for (int i=0; i<n; i++) cin>>a[i];
for (int i=0; i<n; i++) cin>>b[i];
for (int i=0; i<m; i++){
int u,v; cin>>u>>v; u--; v--;
adj[u].push_back(v); adj[v].push_back(u); edges.push_back({u,v});
}
for (int i=0; i<n; i++) if (b[i] > a[i]) return 0;
SGT sgt(n);
for (auto [u,v]: edges){
int l1 = b[u], r1 = a[u], l2 = b[v], r2 = a[v];
if (l1>l2) swap(l1,l2), swap(r1,r2);
if (r1<l2) continue;
sgt.add(max(l1, l2)-1, min(r1,r2)-1, {u,v});
}
sgt.dfs();
for (int i=0; i<n; i++) if (a[i] != b[i]) return 0;
return 1;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t; cin>>t;
while (t--){
cout << solve() << '\n';
}
}
Compilation message
colors.cpp: In member function 'void SGT::dfs(int, int, int)':
colors.cpp:66:13: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
66 | for (auto [u,v]: t[p]) dsu->rollback();
| ^~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
57 ms |
11172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
59 ms |
5880 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
64 ms |
11328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
64 ms |
11328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
57 ms |
11172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
122 ms |
14532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
30 ms |
5716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
57 ms |
11172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
