| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 701374 |
2023-02-21T05:01:34 Z |
Nursik |
Colors (RMI18_colors) |
C++14 |
|
3000 ms |
46312 KB |
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double
const ll maxn = 2e5 + 1, maxm = 3e5 + 1;
const ll mod = 1e9 + 7, cmod = 998244353, inf = 1e9, blck = 400, p2 = 31;
const ld eps = 1e-9;
int t;
int n, m, ver;
int a[maxn], b[maxn], pos[maxn], blocked[maxn], par[maxn];
int used[maxn];
set<int> setik[maxn];
vector<int> g[maxn], pth;
struct seg_tree{
int t[maxn * 4], t2[maxn * 4], mv[maxn * 4];
void push(int v, int l, int r){
if (mv[v] != inf){
t[v] = min(t[v], mv[v]);
if (l != r){
mv[v + v] = min(mv[v + v], mv[v]);
mv[v + v + 1] = min(mv[v + v + 1], mv[v]);
}
mv[v] = inf;
}
}
void upd(int pos, int val, int v = 1, int tl = 0, int tr = n - 1){
if (tl == tr){
t[v] = val;
return;
}
int tm = (tl + tr) / 2;
if (pos <= tm){
upd(pos, val, v + v, tl, tm);
}
else{
upd(pos, val, v + v + 1, tm + 1, tr);
}
t[v] = min(t[v + v], t[v + v + 1]);
}
void updlr(int l, int r, int val, int v = 1, int tl = 0, int tr = n - 1){
push(v, tl, tr);
if (l <= tl && tr <= r){
mv[v] = min(mv[v], val);
push(v, tl, tr);
return;
}
if (l > tr || r < tl)
return;
int tm = (tl + tr) / 2;
updlr(l, r, val, v + v, tl, tm);
updlr(l, r, val, v + v + 1, tm + 1, tr);
t[v] = min(t[v + v], t[v + v + 1]);
}
void upd2(int pos, int val, int v = 1, int tl = 0, int tr = n - 1){
if (tl == tr){
t2[v] = val;
return;
}
int tm = (tl + tr) / 2;
if (pos <= tm){
upd2(pos, val, v + v, tl, tm);
}
else{
upd2(pos, val, v + v + 1, tm + 1, tr);
}
t2[v] = max(t2[v + v], t2[v + v + 1]);
}
int getn(int l, int r, int v = 1, int tl = 0, int tr = n - 1){
push(v, tl, tr);
if (l <= tl && tr <= r){
return t[v];
}
if (l > tr || r < tl)
return inf;
int tm = (tl + tr) / 2;
return min(getn(l, r, v + v, tl, tm), getn(l, r, v + v + 1, tm + 1, tr));
}
int getx(int l, int r, int v = 1, int tl = 0, int tr = n - 1){
if (l <= tl && tr <= r){
return t2[v];
}
if (l > tr || r < tl)
return -inf;
int tm = (tl + tr) / 2;
return max(getx(l, r, v + v, tl, tm), getx(l, r, v + v + 1, tm + 1, tr));
}
} rt;
void dfs(int v, int p){
pth.pb(v);
for (auto to : g[v]){
if (to != p){
dfs(to, v);
}
}
}
void dfs(int v, int p, int x){
if (a[v] == x){
ver = v;
return;
}
for (auto to : g[v]){
if (to != p){
if (blocked[to] == 0 && a[to] >= x){
par[to] = v;
dfs(to, v, x);
}
else if (blocked[to] == 1 && a[to] == x){
par[to] = v;
dfs(to, v, x);
}
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> t;
while (t--){
cin >> n >> m;
for (int i = 1; i <= n * 4; ++i){
rt.t[i] = inf;
rt.t2[i] = 0;
rt.mv[i] = inf;
}
pth.clear();
for (int i = 1; i <= n; ++i){
cin >> a[i];
used[a[i]] = 1;
setik[a[i]].insert(i);
}
for (int i = 1; i <= n; ++i){
cin >> b[i];
}
for (int i = 1; i <= m; ++i){
int u, v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
int chain = (n - 1 == m);
for (int i = 1; i <= n; ++i){
chain &= ((int)g[i].size() <= 2);
}
if (chain){
int st = -1;
for (int i = 1; i <= n; ++i){
if ((int)g[i].size() <= 1){
st = i;
break;
}
}
dfs(st, 0);
for (int i = 0; i < n; ++i){
rt.upd(i, a[pth[i]]);
pos[pth[i]] = i;
}
vector<pair<int, int>> vec;
for (int i = 1; i <= n; ++i){
vec.pb(mp(b[i], i));
}
sort(vec.begin(), vec.end());
reverse(vec.begin(), vec.end());
int bad = 0;
/* for (auto it : pth){
cout << it << " ";
}
/ cout << '\n';
for (auto it : pth){
cout << a[it] << " ";
}
cout << '\n';
cout << "start\n";*/
for (int i = 0; i < n; ++i){
pair<int, int> cur = vec[i];
int x = pos[cur.s];
// cout << cur.f << " " << x << " " << cur.s << '\n';
if (cur.f == rt.getn(x, x)){
rt.upd2(x, cur.f);
continue;
}
// cout << "kek\n";
int l = 0, r = x, ans = -1;
while (l <= r){
int mid = (l + r) / 2;
if (rt.getn(mid, x) >= cur.f){
if (rt.getx(mid, x) > cur.f){
l = mid + 1;
continue;
}
r = mid - 1, ans = mid;
}
else{
l = mid + 1;
}
}
/* cout << ans << '\n';
cout << rt.getn(x - 1, x) << " " << rt.getx(x - 1, x) << '\n';
exit(0);*/
if (rt.getn(ans, x) == cur.f && rt.getx(ans, x) <= cur.f){
rt.updlr(ans, x, cur.f);
rt.upd2(x, cur.f);
// cout << ans << " " << x << " " << cur.f << '\n';
continue;
}
l = x, r = n - 1, ans = -1;
while (l <= r){
int mid = (l + r) / 2;
if (rt.getn(x, mid) >= cur.f){
if (rt.getx(x, mid) > cur.f){
r = mid - 1;
continue;
}
l = mid + 1, ans = mid;
}
else{
r = mid - 1;
}
}
if (rt.getn(x, ans) == cur.f && rt.getx(ans, x) <= cur.f){
rt.updlr(x, ans, cur.f);
rt.upd2(x, cur.f);
continue;
}
bad = 1;
break;
}
// cout << "end\n";
for (int i = 0; i < n; ++i){
int x = rt.getn(i, i);
// cout << x << " " << b[pth[i]] << '\n';
if (x != b[pth[i]]){
bad = 1;
break;
}
}
if (bad){
cout << 0 << '\n';
}
else{
cout << 1 << '\n';
}
for (int i = 1; i <= n; ++i){
used[i] = 0;
setik[i].clear();
g[i].clear();
}
continue;
}
int star = 0;
int complt = (n * (n - 1) / 2 == m);
if (complt){
vector<pair<int, int>> vec;
for (int i = 1; i <= n; ++i){
vec.pb(mp(b[i], i));
}
sort(vec.begin(), vec.end());
reverse(vec.begin(), vec.end());
int bad = 0;
for (int i = 0; i < n; ++i){
int x = vec[i].f, y = vec[i].s;
int ok = 0;
for (int j = 1; j <= n; ++j){
if (a[j] == x){
ok = 1;
a[y] = min(a[y], a[j]);
break;
}
}
bad |= !ok;
}
for (int i = 1; i <= n; ++i){
if (a[i] != b[i]){
bad = 1;
}
}
if (bad){
cout << 0 << '\n';
}
else{
cout << 1 << '\n';
}
for (int i = 1; i <= n; ++i){
setik[i].clear();
used[i] = 0;
g[i].clear();
}
continue;
}
for (int i = 1; i <= n; ++i){
if ((int)g[i].size() == n - 1){
star = i;
}
}
if (star){
int bad = 0;
vector<pair<int, int>> vec;
for (int i = 1; i <= n; ++i){
vec.pb(mp(b[i], i));
}
sort(vec.begin(), vec.end());
reverse(vec.begin(), vec.end());
for (int i = 0; i < n; ++i){
pair<int, int> cur = vec[i];
int x = cur.f;
int y = cur.s;
if (a[y] == b[y]){
setik[a[y]].insert(y);
continue;
}
if ((int)setik[x].size() == 0){
bad = 1;
break;
}
int z = *setik[x].begin();
setik[a[star]].erase(star);
a[star] = min(a[star], a[z]);
setik[a[star]].insert(star);
setik[a[y]].erase(y);
a[y] = min(a[y], a[star]);
setik[a[y]].insert(y);
}
for (int i = 1; i <= n; ++i){
if (a[i] != b[i]){
bad = 1;
}
}
if (bad){
cout << 0 << '\n';
}
else{
cout << 1 << '\n';
}
}
else if (m == n - 1){
vector<pair<int, int>> vec;
for (int i = 1; i <= n; ++i){
vec.pb(mp(b[i], i));
}
int bad = 0;
sort(vec.begin(), vec.end());
reverse(vec.begin(), vec.end());
for (int i = 0; i < n; ++i){
pair<int, int> cur = vec[i];
int x = cur.f, y = cur.s;
if (a[y] == b[y]){
blocked[y] = 1;
continue;
}
if (a[y] < b[y]){
bad = 1;
break;
}
ver = -1;
dfs(y, 0, b[y]);
if (ver == -1){
bad = 1;
break;
}
vector<int> putt;
while (ver != y){
putt.pb(ver);
ver = par[ver];
}
putt.pb(y);
for (auto it : putt){
a[it] = min(a[it], b[y]);
}
blocked[y] = 1;
}
if (bad){
cout << 0 << '\n';
}
else{
cout << 1 << '\n';
}
}
for (int i = 1; i <= n; ++i){
used[i] = 0;
g[i].clear();
setik[i].clear();
blocked[i] = 0;
}
}
}
Compilation message
colors.cpp: In function 'int main()':
colors.cpp:377:21: warning: unused variable 'x' [-Wunused-variable]
377 | int x = cur.f, y = cur.s;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
14480 KB |
Output is correct |
| 2 |
Correct |
27 ms |
14504 KB |
Output is correct |
| 3 |
Correct |
10 ms |
14548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
14420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
14456 KB |
Output is correct |
| 2 |
Correct |
45 ms |
14420 KB |
Output is correct |
| 3 |
Correct |
15 ms |
14548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
14456 KB |
Output is correct |
| 2 |
Correct |
45 ms |
14420 KB |
Output is correct |
| 3 |
Correct |
15 ms |
14548 KB |
Output is correct |
| 4 |
Correct |
233 ms |
14464 KB |
Output is correct |
| 5 |
Correct |
885 ms |
24824 KB |
Output is correct |
| 6 |
Correct |
611 ms |
46312 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
14480 KB |
Output is correct |
| 2 |
Correct |
27 ms |
14504 KB |
Output is correct |
| 3 |
Correct |
10 ms |
14548 KB |
Output is correct |
| 4 |
Correct |
114 ms |
14456 KB |
Output is correct |
| 5 |
Correct |
45 ms |
14420 KB |
Output is correct |
| 6 |
Correct |
15 ms |
14548 KB |
Output is correct |
| 7 |
Correct |
60 ms |
14420 KB |
Output is correct |
| 8 |
Correct |
27 ms |
14952 KB |
Output is correct |
| 9 |
Correct |
10 ms |
14644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
116 ms |
14520 KB |
Output is correct |
| 2 |
Execution timed out |
3059 ms |
25180 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
14492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
14480 KB |
Output is correct |
| 2 |
Correct |
27 ms |
14504 KB |
Output is correct |
| 3 |
Correct |
10 ms |
14548 KB |
Output is correct |
| 4 |
Correct |
60 ms |
14420 KB |
Output is correct |
| 5 |
Correct |
114 ms |
14456 KB |
Output is correct |
| 6 |
Correct |
45 ms |
14420 KB |
Output is correct |
| 7 |
Correct |
15 ms |
14548 KB |
Output is correct |
| 8 |
Correct |
233 ms |
14464 KB |
Output is correct |
| 9 |
Correct |
885 ms |
24824 KB |
Output is correct |
| 10 |
Correct |
611 ms |
46312 KB |
Output is correct |
| 11 |
Correct |
60 ms |
14420 KB |
Output is correct |
| 12 |
Correct |
27 ms |
14952 KB |
Output is correct |
| 13 |
Correct |
10 ms |
14644 KB |
Output is correct |
| 14 |
Correct |
116 ms |
14520 KB |
Output is correct |
| 15 |
Execution timed out |
3059 ms |
25180 KB |
Time limit exceeded |
| 16 |
Halted |
0 ms |
0 KB |
- |
