| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1108614 |
2024-11-04T15:35:51 Z |
cpptowin |
Colors (RMI18_colors) |
C++17 |
|
141 ms |
206732 KB |
// PhuThuyRuntime <3
// A secret makes a woman woman
#include <bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define ef emplace_front
#define pb push_back
#define pf push_front
#define all(v) v.begin(), v.end()
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define fo(i, l, r) for(int i = l; i <= r; i++)
#define foi(i, l, r) for(int i = l; i >= r; i--)
#define elif else if
#define el cout << "\n";
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define pil pair<int, ll>
#define fi first
#define se second
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define ll long long
#define ull unsigned long long
#define pob pop_back
#define bs binary_search
#define vi vector<int>
#define vii vector<pair<int, int>>
#define getbit(i, j) (i >> j) & 1
#define offbit(i, j) (1 << j) ^ i
#define onbit(i, j) (1 << j) | i
const int N = 1e6 + 2;
const ll mod = 1e9 + 7;
const int inf = INT_MAX;
const int base = 31;
const long double EPS = 1e-9;
const long double pi = acos(-1.0);
int t, n, m, a[2 * N], b[2 * N];
vi adjA[2 * N], adjB[2 * N];
vii edges, e[4 * N];
void inp(){
cin >> n >> m;
edges.clear();
fo(i, 1, n) adjA[i].clear(), adjB[i].clear();
fo(i, 1, 4 * n) e[i].clear();
fo(i, 1, n){
cin >> a[i];
adjA[a[i]].eb(i);
}
fo(i, 1, n){
cin >> b[i];
adjB[b[i]].eb(i);
}
fo(i, 1, m){
int u, v; cin >> u >> v;
edges.eb(u, v);
}
}
struct zata{
int x, y, xSize, ySize;
};
stack<zata> st;
struct dsu{
int par[2 * N], sz[2 * N];
void makeset(int u){
par[u] = u;
sz[u] = 1;
}
int findset(int u){
return u == par[u] ? u : par[u] = findset(par[u]);
}
void joinset(int u, int v){
u = findset(u);
v = findset(v);
if(u == v) return;
if(sz[u] < sz[v]) swap(u, v);
st.push({u, v, sz[u], sz[v]});
par[v] = u;
sz[u] += sz[v];
}
void rollback(int SZ) {
while ((int)st.size() > SZ) {
zata top = st.top();
st.pop();
par[top.x] = top.x;
par[top.y] = top.y;
sz[top.x] = top.xSize;
sz[top.y] = top.ySize;
}
}
} dsu;
void update(int id, int l, int r, int u, int v, pii edge){
if(l > v || r < u) return;
if(u <= l && r <= v){
e[id].eb(edge);
return;
}
int m = l + r >> 1;
update(id << 1, l, m, u, v, edge);
update(id << 1 | 1, m + 1, r, u, v, edge);
}
int ans;
void solve(int id, int l, int r) {
int sz = (int)st.size();
for (auto [u, v] : e[id]) dsu.joinset(u, v);
if (l == r){
unordered_set<int> cnt;
for (auto x : adjA[l]) cnt.insert(dsu.findset(x));
for (auto x : adjB[l]) {
if (!cnt.count(dsu.findset(x))) ans = 0;
}
}
else {
int m = (l + r) / 2;
solve(id << 1, l, m);
solve(id << 1 | 1, m + 1, r);
}
dsu.rollback(sz);
}
void sol(){
fo(i, 1, n){
if(a[i] < b[i]){
cout << 0, el
return;
}
}
for(auto [u, v] : edges){
int mn = max(b[u], b[v]);
int mx = min(a[u], a[v]);
if(mn <= mx) update(1, 1, n, mn, mx, {u, v});
}
ans = 1;
solve(1, 1, n);
cout << ans, el
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
fo(i, 1, 1000000) dsu.makeset(i);
cin >> t;
while(t--){
inp();
sol();
}
return 0;
}
Compilation message
colors.cpp: In function 'void update(int, int, int, int, int, std::pair<int, int>)':
colors.cpp:106:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
106 | int m = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
205200 KB |
Output is correct |
| 2 |
Correct |
48 ms |
204272 KB |
Output is correct |
| 3 |
Correct |
38 ms |
204052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
205640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
205128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
205128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
205200 KB |
Output is correct |
| 2 |
Correct |
48 ms |
204272 KB |
Output is correct |
| 3 |
Correct |
38 ms |
204052 KB |
Output is correct |
| 4 |
Incorrect |
83 ms |
205128 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
141 ms |
206732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
204616 KB |
Output is correct |
| 2 |
Correct |
42 ms |
204368 KB |
Output is correct |
| 3 |
Correct |
37 ms |
204020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
205200 KB |
Output is correct |
| 2 |
Correct |
48 ms |
204272 KB |
Output is correct |
| 3 |
Correct |
38 ms |
204052 KB |
Output is correct |
| 4 |
Correct |
76 ms |
205640 KB |
Output is correct |
| 5 |
Incorrect |
83 ms |
205128 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
