# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
261755 |
2020-08-12T04:24:03 Z |
lyc |
Colors (RMI18_colors) |
C++14 |
|
3000 ms |
68372 KB |
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ii=pair<int,int>;
const int mxN = 150005;
//~ const int mxN = 1505;
int N, M, A[mxN], B[mxN];
vector<int> al[mxN];
struct Update { int x, y, u, v; };
struct Query { int b, u; };
struct UFDS {
vector<int> p;
vector<set<int>> s;
vector<map<int,int>> col;
vector<ii> history;
void init() {
p.resize(N+1);
s.resize(N+1);
col.resize(N+1);
FOR(i,1,N){
p[i] = i;
s[i].clear();
s[i].insert(i);
col[i].clear();
col[i][A[i]] = 1;
}
}
bool unions(int i, int j) {
//~ TRACE("UNIONS" _ i _ j);
int x = p[i], y = p[j];
if (x == y) return 0;
if (SZ(s[x]) < SZ(s[y])) swap(x,y);
history.emplace_back(x,y);
for (int a : s[y]) {
s[x].insert(a);
++col[x][A[a]];
p[a] = x;
}
return 1;
}
int getTime() { return SZ(history); }
void undo(int t) {
while (SZ(history) > t) {
ii cur = history.back(); history.pop_back();
int x = cur.first, y = cur.second;
for (int a : s[y]) {
s[x].erase(a);
--col[x][A[a]];
p[a] = y;
}
}
}
int query(int i, int c) {
return col[p[i]][c];
}
} ufds;
bool reach[mxN];
void dnc(int L, int R, vector<Update> upd, vector<Query> qry) {
if (L > R) return;
int t = ufds.getTime();
vector<Update> ul, ur;
vector<Query> ql, qr;
int m = (L+R)/2;
for (auto& u : upd) {
if (L == u.x && R == u.y) ufds.unions(u.u,u.v);
else if (u.y <= m) ul.push_back(u);
else if (u.x > m) ur.push_back(u);
else ul.push_back({u.x, m, u.u, u.v}), ur.push_back({m+1, u.y, u.u, u.v});
}
for (auto& q : qry) {
if (q.b <= m) ql.push_back(q);
else qr.push_back(q);
}
if (L != R) {
dnc(L,m,ul,ql);
dnc(m+1,R,ur,qr);
}
//~ TRACE(L _ R _ t _ ufds.getTime());
//~ for (auto& u : upd) { if (L == u.x && R == u.y) cout << u.u _ u.v << " :: "; }
//~ cout << endl;
for (auto& q : qry) {
//~ TRACE("QUERY" _ q.u _ q.b _ ufds.query(q.u, q.b));
reach[q.u] |= ufds.query(q.u, q.b) > 0;
}
ufds.undo(t);
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int TC; cin >> TC;
while (TC--) {
cin >> N >> M;
FOR(i,1,N){ cin >> A[i]; }
FOR(i,1,N){ cin >> B[i]; }
FOR(i,1,N) al[i].clear();
FOR(i,1,M){
int U, V; cin >> U >> V;
al[U].push_back(V);
al[V].push_back(U);
}
bool ok = 1;
vector<Update> upd;
vector<Query> qry;
FOR(u,1,N){
if (A[u] < B[u]) { ok = 0; break; }
for (int& v : al[u]) if (u < v) {
int x = max(B[u],B[v]), y = min(A[u],A[v]);
//~ TRACE("UPD" _ x _ y _ u _ v);
if (x <= y) upd.push_back({ x, y, u, v });
}
qry.push_back({ B[u], u });
}
if (ok) {
memset(reach,0,sizeof reach);
ufds.init();
dnc(1,N,upd,qry);
//~ FOR(i,1,N){ cout << reach[i] << ' '; } cout << endl;
FOR(i,1,N) ok &= reach[i];
}
cout << ok << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
297 ms |
4600 KB |
Output is correct |
2 |
Correct |
126 ms |
4728 KB |
Output is correct |
3 |
Correct |
21 ms |
5504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
131 ms |
4564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
344 ms |
4612 KB |
Output is correct |
2 |
Correct |
138 ms |
4600 KB |
Output is correct |
3 |
Correct |
17 ms |
4864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
344 ms |
4612 KB |
Output is correct |
2 |
Correct |
138 ms |
4600 KB |
Output is correct |
3 |
Correct |
17 ms |
4864 KB |
Output is correct |
4 |
Correct |
731 ms |
5240 KB |
Output is correct |
5 |
Execution timed out |
3060 ms |
59064 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
297 ms |
4600 KB |
Output is correct |
2 |
Correct |
126 ms |
4728 KB |
Output is correct |
3 |
Correct |
21 ms |
5504 KB |
Output is correct |
4 |
Correct |
344 ms |
4612 KB |
Output is correct |
5 |
Correct |
138 ms |
4600 KB |
Output is correct |
6 |
Correct |
17 ms |
4864 KB |
Output is correct |
7 |
Correct |
321 ms |
4600 KB |
Output is correct |
8 |
Correct |
139 ms |
4600 KB |
Output is correct |
9 |
Correct |
37 ms |
5376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
683 ms |
5752 KB |
Output is correct |
2 |
Execution timed out |
3044 ms |
68372 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
75 ms |
4412 KB |
Output is correct |
2 |
Correct |
28 ms |
5508 KB |
Output is correct |
3 |
Correct |
21 ms |
4864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
297 ms |
4600 KB |
Output is correct |
2 |
Correct |
126 ms |
4728 KB |
Output is correct |
3 |
Correct |
21 ms |
5504 KB |
Output is correct |
4 |
Correct |
131 ms |
4564 KB |
Output is correct |
5 |
Correct |
344 ms |
4612 KB |
Output is correct |
6 |
Correct |
138 ms |
4600 KB |
Output is correct |
7 |
Correct |
17 ms |
4864 KB |
Output is correct |
8 |
Correct |
731 ms |
5240 KB |
Output is correct |
9 |
Execution timed out |
3060 ms |
59064 KB |
Time limit exceeded |
10 |
Halted |
0 ms |
0 KB |
- |