This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct ps {
int size;
int cnt;
bool need_copy;
ps * l;
ps * r;
ps() {}
ps(int sz) {
need_copy = false;
size = sz;
cnt = 0;
if(size > 1) {
l = new ps(size/2);
r = new ps((size+1)/2);
}
}
ps(ps & oth) {
*this = oth;
need_copy = true;
}
void push() {
if(size == 1) return;
if(need_copy) {
need_copy = false;
l = new ps(*l);
r = new ps(*r);
}
}
void ins(int i) {
push();
if(size == 1) {
cnt = 1;
} else {
if(i < l->size) l->ins(i);
else r->ins(i - l->size);
cnt = l->cnt + r->cnt;
}
}
int check(int i) {
if(size == 1) return cnt;
if(i < l->size) return l->check(i);
else return r->check(i - l->size);
}
void vectorize(vector<int> & v, int pos = 0) {
if(!cnt) return;
if(size == 1) {
v.push_back(pos);
} else {
l->vectorize(v, pos);
r->vectorize(v, pos + l->size);
}
}
~ps() {
if(size == 1) return;
if(need_copy) return;
delete l;
delete r;
}
};
const int mx = 200005;
ps trees[mx];
void share(int a, int b) {
if(trees[a].cnt > trees[b].cnt) swap(a, b);
vector<int> a_elems;
trees[a].vectorize(a_elems);
for(int i : a_elems) trees[b].ins(i);
trees[a] = ps(trees[b]);
trees[b].need_copy = true;
}
void query(int a, int d) {
if(trees[a].check(d)) cout << "yes" << endl;
else cout << "no" << endl;
}
void count(int d) {
cout << 1 << endl;
}
main() {
int n, k; cin >> n >> k;
ps emp(n + 1);
for(int i = 1; i <= n; i++) {
trees[i] = ps(emp);
trees[i].ins(i);
trees[i].need_copy = true;
}
for(int i = 0; i < n + k - 1; i++) {
char opp; cin >> opp;
if(opp == 'S') {
int a, b;
cin >> a >> b;
share(a, b);
} else if(opp == 'Q') {
int a, d;
cin >> a >> d;
query(a, d);
} else {
for(int j = 1; j <= n; j++) {
vector<int> tmp;
trees[j].vectorize(tmp);
for(int k : tmp) cout << k << " ";
cout << endl;
}
}
}
}
Compilation message (stderr)
servers.cpp:80:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
80 | main() {
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |