Submission #484512

#TimeUsernameProblemLanguageResultExecution timeMemory
484512wwddKeys (IOI21_keys)C++17
100 / 100
1321 ms128408 KiB
#include <vector> #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> ii; class U { private: vi p,rk; int n; public: U(int sz) { n = sz; for(int i=0;i<n;i++) { p.push_back(i); } rk.assign(n,0); } int find(int a) { if(p[a] == a) { return a; } return p[a] = find(p[a]); } inline bool same(int a, int b) { return find(a) == find(b); } int un(int a, int b) { if(same(a,b)) {return -1;} int x = find(a); int y = find(b); if(rk[x] < rk[y]) {swap(x,y);} if(rk[x] == rk[y]) {rk[x]++;} p[y] = x; return x; } }; struct NO { map<int,list<int>> eg; set<int> cols; list<int> act,reps; int sz; NO(int u) { sz = 1; reps.push_back(u); } void morg(NO& ot) { reps.splice(reps.end(),ot.reps); sz += ot.sz; ot.sz = -1; if(cols.size() < ot.cols.size()) { swap(cols,ot.cols); swap(eg,ot.eg); } for(const auto& col: ot.cols) { if(eg.count(col)) { act.insert(act.end(),eg[col].begin(),eg[col].end()); eg.erase(col); } } cols.insert(ot.cols.begin(),ot.cols.end()); ot.cols.clear(); for(auto& ek: ot.eg) { if(cols.count(ek.first)) { act.insert(act.end(),ek.second.begin(),ek.second.end()); } else { list<int>& cur = eg[ek.first]; if(ek.second.size() > cur.size()) { swap(cur,ek.second); } cur.splice(cur.end(),ek.second); } ek.second.clear(); } ot.eg.clear(); act.splice(act.end(),ot.act); } }; std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) { vector<NO> wu; for(int i=0;i<r.size();i++) { wu.emplace_back(i); wu[i].cols.insert(r[i]); } for(int i=0;i<u.size();i++) { int vu = u[i]; int vv = v[i]; int vc = c[i]; if(vc == r[vu]) { wu[vu].act.push_back(vv); } else { wu[vu].eg[vc].push_back(vv); } if(vc == r[vv]) { wu[vv].act.push_back(vu); } else { wu[vv].eg[vc].push_back(vu); } } vi st; U bu(r.size()); vector<bool> wac(r.size()); vi vs(r.size()); vi enb; for(int sti=0;sti<r.size();sti++) { if(vs[sti]) {continue;} vs[sti] = 1; st.push_back(sti);wac[sti] = 1; bool cont = true; int los; while(cont) { int vu = st.back(); int nx = -1; while(!wu[vu].act.empty()) { int nu = wu[vu].act.back(); nu = bu.find(nu); wu[vu].act.pop_back(); if(nu == vu) {continue;} if(wac[nu]) { st.pop_back();wac[vu] = 0; while(!bu.same(nu,vu)) { int vv = st.back();st.pop_back();wac[vv] = 0; int com = bu.un(vv,vu); wu[com].morg(wu[vv+vu-com]); vu = com; } st.push_back(vu);wac[vu] = 1; } else if(vs[nu]) { cont = false;break; } else { nx = nu;break; } } if(nx == -1) { los = vu; break; } else { vs[nx] = 1; st.push_back(nx); wac[nx] = true; } } while(!st.empty()) { wac[st.back()] = false; st.pop_back(); } if(cont) { enb.push_back(los); } } int ma = r.size()+1; for(const auto& mat: enb) { ma = min(ma,wu[mat].sz); } std::vector<int> ans(r.size(), 0); for(const auto& mat: enb) { if(wu[mat].sz == ma) { for(const auto& it: wu[mat].reps) { ans[it] = 1; } } } return ans; }

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:85:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  for(int i=0;i<r.size();i++) {
      |              ~^~~~~~~~~
keys.cpp:89:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for(int i=0;i<u.size();i++) {
      |              ~^~~~~~~~~
keys.cpp:109:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |  for(int sti=0;sti<r.size();sti++) {
      |                ~~~^~~~~~~~~
#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...