| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 261741 |
2020-08-12T03:50:37 Z |
lyc |
Colors (RMI18_colors) |
C++14 |
|
18 ms |
14968 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];
vector<int> atB[mxN];
struct UFDS {
vector<int> p;
vector<set<int>> s;
vector<multiset<int>> col;
UFDS(){
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].insert(A[i]);
}
}
inline int finds(int i) { return p[i]; }
bool unions(int i, int j) {
int x = finds(i), y = finds(j);
if (x == -1 || y == -1 || x == y) return 0;
if (SZ(s[x]) < SZ(s[y])) swap(x,y);
for (auto& a : s[y]) {
p[a] = x;
s[x].insert(a);
}
for (auto& a : col[y]) {
col[x].insert(a);
}
return 1;
}
void rm(int u) {
int x = finds(u);
p[x] = -1;
s[x].erase(u); // unique
col[x].erase(col[x].find(A[u]));
}
bool findCol(int u, int c) {
int x = finds(u);
assert(x != -1);
return !!col[x].count(c);
}
};
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);
}
FOR(b,1,N) atB[b].clear();
FOR(u,1,N) atB[B[u]].push_back(u);
UFDS ufds;
using edge=tuple<int,int,int>; // priority, from, to
priority_queue<ii,vector<ii>,greater<ii>> del;
priority_queue<edge,vector<edge>,greater<edge>> add;
bool ok = 1;
FOR(i,1,N) if (A[i] < B[i]) { ok = 0; break; }
FOR(b,1,N){
if (!ok) break;
for (int& u : atB[b]) {
del.emplace(A[u], u);
for (int& v : al[u]) {
add.emplace(B[v], u, v);
}
}
//~ TRACE("ADDED" _ b);
while (!del.empty() && del.top().first < b) {
auto v = del.top(); del.pop();
ufds.rm(v.second);
}
//~ TRACE("REMOVED" _ b);
while (!add.empty()) {
auto e = add.top();
int pr, fr, to; tie(pr,fr,to) = e;
if (pr > b) break;
add.pop();
ufds.unions(fr,to);
}
//~ TRACE("RELAXED" _ b);
for (int& u : atB[b]) {
ok &= (ufds.findCol(u, B[u]));
}
}
cout << ok << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
14720 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
14968 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
14720 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
14720 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
14720 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
14848 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
14848 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
14720 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
