Submission #671623

#TimeUsernameProblemLanguageResultExecution timeMemory
671623US3RN4M3Inside information (BOI21_servers)C++17
32.50 / 100
1439 ms524288 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...