oj.uz

Submission #877320

# Submission time Handle Problem Language Result Execution time Memory
877320 2023-11-23T06:25:26 Z huutuan Joker (BOI20_joker) C++14
0 / 100
 66 ms 15308 KB 
#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;
   }
   for (int i=1; i<=q; ++i){
      int l, r; cin >> l >> r;
      qq[l].emplace_back(r, i);
   }
   if (sus){
      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{
      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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Incorrect 1 ms 6748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Incorrect 1 ms 6748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Incorrect 66 ms 15308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Incorrect 1 ms 6748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Incorrect 1 ms 6748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Incorrect 1 ms 6748 KB Output isn't correct
4 Halted 0 ms 0 KB -