Submission #1093543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093543		zNatsumi	Joker (BOI20_joker)	C++17	14 / 100	2061 ms	5724 KiB

Joker

#include <bits/stdc++.h>

using namespace std;

#define ii pair<int, int>
#define fi first
#define se second

const int N = 2e5 + 5;

int n, m, q;
int pa[N], sz[N], lz[N];
ii edge[N];

int fset(int i, int &c){
  c ^= lz[i];
  return i == pa[i] ? i : fset(pa[i], c);
}

bool uset(int u, int v){
  int cu = 0, cv = 0;
  u = fset(u, cu);
  v = fset(v, cv);
  if(u == v){
    if(cu == cv) return true;
    return false;
  }
  if(sz[u] < sz[v]) swap(u, v);
  pa[v] = u;
  sz[u] += sz[v];
  if(cu == cv) lz[v] ^= 1;
  return false;
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
  #define task "test"
  if(fopen(task ".inp", "r")){
    freopen(task ".inp", "r", stdin);
    freopen(task ".out", "w", stdout);
  }

  cin >> n >> m >> q;
  for(int i = 1; i <= m; i++){
    int u, v; cin >> u >> v;
    edge[i] = {u, v};
  }
  for(int t = 1; t <= q; t++){
    int l, r; cin >> l >> r;

    for(int i = 1; i <= n; i++){
      pa[i] = i;
      sz[i] = 1;
      lz[i] = 0;
    }
    bool ok = false;
    for(int i = 1; i <= m; i++){
      if(l <= i && i <= r) continue;

      if(uset(edge[i].fi, edge[i].se)){
        ok = true;
        break;
      }
    }
    cout << (ok ? "YES\n" : "NO\n");
  }

  return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'int32_t main()':
Joker.cpp:39:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     freopen(task ".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:40:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     freopen(task ".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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