| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 867022 |
2023-10-27T15:14:33 Z |
Andrey |
Colors (RMI18_colors) |
C++14 |
|
134 ms |
43604 KB |
#include<bits/stdc++.h>
using namespace std;
vector<int> col(200001);
vector<int> wow(200001);
vector<int> haha[200001];
vector<int> yoo[200001];
vector<int> yay[200001];
vector<int> seg[1000000];
vector<int> dsu(200001);
vector<bool> bruh(200001,false);
vector<pair<int,int>> wut[20];
bool yeah = true;
int calc(int a, int d) {
int c = a,e,b;
while(c != dsu[c]) {
c = dsu[c];
}
e = a;
while(e != dsu[e]) {
b = dsu[e];
wut[d].push_back({e,dsu[e]});
dsu[e] = c;
e = b;
}
return c;
}
void edge(int a, int b, int d) {
a = calc(a,d),b = calc(b,d);
wut[d].push_back({a,dsu[a]});
dsu[a] = b;
}
void dude(int l, int r, int x, int d) {
for(int i = 0; i < seg[x].size(); i++) {
int a = seg[x][i];
bruh[a] = true;
for(int j = 0; j < haha[a].size(); j++) {
if(bruh[haha[a][j]]) {
edge(a,haha[a][j],d);
}
}
}
int m = (l+r)/2;
if(l != r) {
dude(l,m,x*2+1,d+1);
dude(m+1,r,x*2+2,d+1);
}
else {
set<int> idk;
for(int i = 0; i < yoo[l].size(); i++) {
idk.insert(calc(yoo[l][i],d));
}
for(int i = 0; i < yay[l].size(); i++) {
if(idk.find(calc(yay[l][i],d)) == idk.end()) {
yeah = false;
}
}
}
while(wut[d].size() > 0) {
int a = wut[d][wut[d].size()-1].first;
int b = wut[d][wut[d].size()-1].second;
dsu[a] = b;
wut[d].pop_back();
}
for(int i = 0; i < seg[x].size(); i++) {
bruh[seg[x][i]] = false;
}
}
void upd(int l, int r, int x, int ql, int qr, int k) {
if(ql == l && qr == r) {
seg[x].push_back(k);
return;
}
int m = (l+r)/2;
if(qr <= m) {
upd(l,m,x*2+1,ql,qr,k);
}
else if(ql > m) {
upd(m+1,r,x*2+2,ql,qr,k);
}
else {
upd(l,m,x*2+1,ql,m,k);
upd(m+1,r,x*2+2,m+1,qr,k);
}
}
void solve() {
int n,m,a,b;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
haha[i].clear();
yoo[i].clear();
yay[i].clear();
bruh[i] = false;
dsu[i] = i;
}
for(int i = 0; i <= 4*n; i++) {
seg[i].clear();
}
vector<pair<int,int>> wut(0);
for(int i = 1; i <= n; i++) {
cin >> col[i];
yoo[col[i]].push_back(i);
}
for(int i = 1; i <= n; i++) {
cin >> wow[i];
yay[wow[i]].push_back(i);
}
for(int i = 0; i < m; i++) {
cin >> a >> b;
haha[a].push_back(b);
haha[b].push_back(a);
}
for(int i = 1; i <= n; i++) {
if(wow[i] > col[i]) {
cout << "NO\n";
return;
}
}
for(int i = 1; i <= n; i++) {
upd(1,n,0,wow[i],col[i],i);
}
dude(1,n,0,0);
cout << yeah << "\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while(t--) {
solve();
}
return 0;
}
Compilation message
colors.cpp: In function 'void dude(int, int, int, int)':
colors.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int i = 0; i < seg[x].size(); i++) {
| ~~^~~~~~~~~~~~~~~
colors.cpp:40:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int j = 0; j < haha[a].size(); j++) {
| ~~^~~~~~~~~~~~~~~~
colors.cpp:53:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int i = 0; i < yoo[l].size(); i++) {
| ~~^~~~~~~~~~~~~~~
colors.cpp:56:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int i = 0; i < yay[l].size(); i++) {
| ~~^~~~~~~~~~~~~~~
colors.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i = 0; i < seg[x].size(); i++) {
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
41720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
42068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
41824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
41824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
41720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
134 ms |
43604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
41276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
41720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
