Submission #877323

#	Time	Username	Problem	Language	Result	Execution time	Memory
877323		huutuan	Joker (BOI20_joker)	C++14	0 / 100	2072 ms	17572 KiB

Joker

#include<bits/stdc++.h>
#define taskname "nohome"

using namespace std;

struct DSU{
   vector<int> lab, val;
   bool ans=1;
   void init(int n){
      lab.assign(n+1, -1);
      val.assign(n+1, 0);
   }
   pair<int, int> find_set(int u){
      if (lab[u]<0) return {u, 0};
      auto p=find_set(lab[u]);
      lab[u]=p.first;
      val[u]^=p.second;
      return {lab[u], val[u]};
   }
   void union_sets(int u, int v){
      auto pu=find_set(u), pv=find_set(v);
      if (pu.first!=pv.first){
         if (lab[pu.first]>lab[pv.first]) swap(pu, pv), swap(u, v);
         lab[pu.first]+=lab[pv.first];
         val[pu.first]=0;
         lab[pv.first]=pu.first;
         val[pv.first]=pu.second^pv.second^1;
      }else
         ans&=pu.second^pv.second;
   }
};

const int N=2e5+1;
int n, m, q, ans[N];
pair<int, int> edge[N];
vector<pair<int, int>> qq[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   // freopen(taskname".inp", "r", stdin);
   // freopen(taskname".out", "w", stdout);
   cin >> n >> m >> q;
   bool sus=1;
   for (int i=1; i<=m; ++i){
      int x, y; cin >> x >> y;
      edge[i]={x, y};
      sus&=x==1;
   }
   if (sus){
      for (int i=1; i<=q; ++i){
         int l, r; cin >> l >> r;
         qq[l].emplace_back(r, i);
      }
      DSU dsu;
      dsu.init(n);
      for (int i=1; i<=m; ++i){
         if (qq[i].size()){
            DSU dsu2=dsu;
            sort(qq[i].rbegin(), qq[i].rend());
            int cur=m;
            for (auto &j:qq[i]){
               while (cur>j.first){
                  dsu2.union_sets(edge[cur].first, edge[cur].second);
                  --cur;
               }
               ans[j.second]=!dsu2.ans;
            }
         }
         dsu.union_sets(edge[i].first, edge[i].second);
      }
   }else{
      for (int i=1; i<=q; ++i){
         int l, r; cin >> l >> r;
         qq[r].emplace_back(l, i);
      }
      DSU dsu;
      dsu.init(n);
      for (int i=m; i>=1; --i){
         if (qq[i].size()){
            DSU dsu2=dsu;
            sort(qq[i].rbegin(), qq[i].rend());
            int cur=1;
            for (auto &j:qq[i]){
               while (cur<j.first){
                  dsu2.union_sets(edge[cur].first, edge[cur].second);
                  ++cur;
               }
               ans[j.second]=!dsu2.ans;
            }
         }
         dsu.union_sets(edge[i].first, edge[i].second);
      }
   }
   for (int i=1; i<=q; ++i) cout << (ans[i]?"YES\n":"NO\n");
   return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29