| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 332482 |
2020-12-02T17:27:44 Z |
Vladth11 |
Colors (RMI18_colors) |
C++14 |
|
13 ms |
17932 KB |
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <ll, pii> piii;
const ll NMAX = 150001;
const ll INF = (1 << 30);
const ll MOD = 1000000007;
const ll BLOCK = 101;
const ll nr_of_bits = 14;
const ll delta = 0.0000001;
int n, m;
vector <int> v[NMAX];
int ok;
int a[NMAX], b[NMAX];
class DSU {
int minim[NMAX], cnt[NMAX];
struct dsu_save {
int w, x, y, size_x, size_y, parent_x, parent_y, mini_x, mini_y;
};
int parent[NMAX];
int root(int x) {
if(x == parent[x])
return x;
return root(parent[x]);
}
public:
stack <dsu_save> stiva;
void init() {
while(stiva.size())
stiva.pop();
for(int i = 1; i <= n; i++) {
cnt[i] = 1;
parent[i] = i;
minim[i] = a[i];
}
}
void merge(int node, int x, int y) {
x = root(x);
y = root(y);
if(x == y)
return;
dsu_save ss = {node, x, y,cnt[x], cnt[y], parent[x], parent[y], minim[x], minim[y]};
stiva.push(ss);
if(cnt[x] > cnt[y]) {
cnt[x] += cnt[y];
cnt[y] = 0;
parent[y] = x;
minim[x] = min(minim[x], minim[y]);
} else {
cnt[y] += cnt[x];
cnt[x] = 0;
parent[x] = y;
minim[y] = min(minim[x], minim[y]);
}
}
void rollback() {
if(stiva.size() == 0)
return;
dsu_save e = stiva.top();
int x = e.x;
int y = e.y;
cnt[x] = e.size_x;
cnt[y] = e.size_y;
parent[x] = e.parent_x;
parent[y] = e.parent_y;
minim[x] = e.mini_x;
minim[y] = e.mini_y;
stiva.pop();
}
int minimm(int x) {
x = root(x);
return minim[x];
}
};
class AINT {
vector <pii> aint[4 * NMAX];
DSU dsu;
public:
void init() {
dsu.init();
}
void update(int node, int st, int dr, int a, int b, pii x) {
if(a > b)
return;
if(a <= st && dr <= b) {
aint[node].push_back(x);
return;
}
int mid = (st + dr) / 2;
if(a <= mid) {
update(node * 2, st, mid, a, b, x);
}
if(b > mid) {
update(node * 2 + 1, mid + 1, dr, a, b, x);
}
}
void DFS(int node, int st, int dr) {
for(auto x : aint[node]) {
dsu.merge(node, x.first, x.second);
}
// debug(node);
if(st == dr) {
for(auto x : v[st]) {
// debug(st);
if(st != dsu.minimm(x)) {
//debug(dsu.minimm(x));
ok = 0;
}
}
}
int mid = (st + dr) / 2;
if(st != dr) {
DFS(node * 2, st, mid);
DFS(node * 2 + 1, mid + 1, dr);
}
while(dsu.stiva.size() > 0 && dsu.stiva.top().w == node) {
dsu.rollback();
}
aint[node].clear();
}
} DC;
int main() {
ifstream cin("colors2.in");
ofstream cout("colors2.out");
int t;
cin >> t;
while(t--) {
cin >> n >> m;
int i;
for(i = 1; i <= n; i++) {
v[i].clear();
cin >> a[i];
}
for(i = 1; i <= n; i++) {
cin >> b[i];
v[b[i]].push_back(i);
}
DC.init();
ok = 1;
for(i = 1; i <= n; i++) {
if(a[i] < b[i])
ok = 0;
}
for(i = 1; i <= m; i++) {
int x;
int y;
cin >> x >> y;
if(ok)
DC.update(1, 1, n, max(b[x], b[y]), min(a[x], a[y]), {x, y});
}
if(ok)
DC.DFS(1, 1, n);
// debug(ok);
cout << ok << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
17900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
17900 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
17900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
17900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
17900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
17900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
17932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
17900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
