oj.uz

Submission #1094132

# Submission time Handle Problem Language Result Execution time Memory
1094132 2024-09-28T15:05:23 Z Wjsc Joker (BOI20_joker) C++14
41 / 100
 998 ms 23244 KB 
#include<bits/stdc++.h>

using namespace std;

#define pi pair<int, int>
#define fi first
#define se second
#define all(v) v.begin(), v.end()

const int N = 2e5 + 5;

using tp = tuple<int, int, int>;

int n, m, q;
pi edge[N];
tp Q[N];
vector<int> ad[N];

namespace sub1 {
  bool ok = 0;
  int col[N];

  void dfs(int u, int c) {
    col[u] = c;
    for(auto v : ad[u]) {
      if(col[v] == col[u]) ok = 1;
      if(col[v] == -1) dfs(v, c ^ 1);
    }
  }

  void solve() {
    while(q--) {
      int l, r; cin >> l >> r;

      for(int i = 1; i <= n; ++i) ad[i].clear();

      for(int i = 1; i < l; ++i) {
        int u, v; tie(u, v) = edge[i];
        ad[u].push_back(v);
        ad[v].push_back(u);
      }
      for(int i = r + 1; i <= m; ++i) {
        int u, v; tie(u, v) = edge[i];
        ad[u].push_back(v);
        ad[v].push_back(u);
      }

      for(int i = 1; i <= n; ++i) col[i] = -1;

      ok = 0;
      for(int i = 1; i <= n; ++i)
        if(col[i] == -1) dfs(i, 0);

      cout << (ok ? "YES\n" : "NO\n");
    }
  }
}

///
namespace sub3 {
  int par[N], sz[N], lz[N], ans[N];
  vector<int> L;
  vector<pi> queries[N];

  void make_set() {
    for(int i = 1; i <= n; ++i) par[i] = i, sz[i] = 1, lz[i] = 0;
  }

  int find_set(int v, int &c) {
    c ^= lz[v];
    if(v == par[v]) return v;
    return find_set(par[v], c);
  }

  void union_set(int a, int b) {
    int ca = 0, cb = 0;
    a = find_set(a, ca); b = find_set(b, cb);
    if(a != b) {
      if(sz[a] < sz[b]) swap(a, b);
      sz[a] += sz[b];
      par[b] = a;
      if(ca == cb) lz[b] = 1;
    }
  }

  bool check(int a, int b) {
    int ca = 0, cb = 0;
    a = find_set(a, ca); b = find_set(b, cb);
    if(a == b && ca == cb) return true;
    return false;
  }

  void solve() {
    sort(Q + 1, Q + q + 1);

    for(int i = 1, cur = 0; i <= q; ++i) {
      int l, r, id; tie(l, r, id) = Q[i];
      if(l != cur) cur = l, L.push_back(cur);
      queries[cur].emplace_back(r, id);
    }

    for(auto x : L) sort(all(queries[x]), greater<pi>());

    for(auto l : L) {
      make_set();
      bool ok = 0;

      for(int i = 1; i < l; ++i) {
        int u, v; tie(u, v) = edge[i];
        if(check(u, v)) ok = 1;
        union_set(u, v);
      }

      int j = m;
      for(int i = m; i > queries[l][0].fi; --i) {
        int u, v; tie(u, v) = edge[i];
        if(check(u, v)) ok = 1;
        union_set(u, v);
        j = i;
      }
      ans[queries[l][0].se] = ok;

      for(int i = 1; i < queries[l].size(); ++i) {
        int r, id; tie(r, id) = queries[l][i];
        if(ok) {
          ans[id] = ok;
          continue;
        }

        while(j > r) {
          if(check(edge[j].fi, edge[j].se)) ok = 1;
          union_set(edge[j].fi, edge[j].se);
          --j;
        }
        ans[id] = ok;
      }
    }

    for(int i = 1; i <= q; ++i) cout << (ans[i] ? "YES\n" : "NO\n");
  }
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);

  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};
  }

  bool chk = 1;
  for(int i = 1; i <= q; ++i) {
    int l, r; cin >> l >> r;
    Q[i] = {l, r, i};
    if(l > 200) chk = 0;
  }

  if(chk) sub3 :: solve();
  else if(n <= 2000 && m <= 2000 && q <= 2000) sub1 :: solve();
}

Compilation message

Joker.cpp: In function 'void sub3::solve()':
Joker.cpp:123:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |       for(int i = 1; i < queries[l].size(); ++i) {
      |                      ~~^~~~~~~~~~~~~~~~~~~
Joker.cpp: In function 'int main()':
Joker.cpp:147:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |     freopen("task.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:148:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |     freopen("task.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9856 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 5 ms 9820 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 4 ms 9908 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 5 ms 9744 KB Output is correct
11 Correct 5 ms 9816 KB Output is correct
12 Correct 4 ms 9820 KB Output is correct
13 Correct 4 ms 9820 KB Output is correct
14 Correct 5 ms 9820 KB Output is correct
15 Correct 4 ms 9884 KB Output is correct
16 Correct 7 ms 9820 KB Output is correct
17 Correct 4 ms 9724 KB Output is correct
18 Correct 4 ms 9816 KB Output is correct
19 Correct 4 ms 9832 KB Output is correct
20 Correct 5 ms 9824 KB Output is correct
21 Correct 5 ms 9820 KB Output is correct
22 Correct 5 ms 9820 KB Output is correct
23 Correct 4 ms 9820 KB Output is correct
24 Correct 4 ms 9820 KB Output is correct
25 Correct 4 ms 9820 KB Output is correct
26 Correct 4 ms 9820 KB Output is correct
27 Correct 4 ms 9820 KB Output is correct
28 Correct 5 ms 9816 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9856 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 5 ms 9820 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 4 ms 9908 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 5 ms 9744 KB Output is correct
11 Correct 5 ms 9816 KB Output is correct
12 Correct 4 ms 9820 KB Output is correct
13 Correct 4 ms 9820 KB Output is correct
14 Correct 5 ms 9820 KB Output is correct
15 Correct 4 ms 9884 KB Output is correct
16 Correct 7 ms 9820 KB Output is correct
17 Correct 4 ms 9724 KB Output is correct
18 Correct 4 ms 9816 KB Output is correct
19 Correct 4 ms 9832 KB Output is correct
20 Correct 5 ms 9824 KB Output is correct
21 Correct 5 ms 9820 KB Output is correct
22 Correct 5 ms 9820 KB Output is correct
23 Correct 4 ms 9820 KB Output is correct
24 Correct 4 ms 9820 KB Output is correct
25 Correct 4 ms 9820 KB Output is correct
26 Correct 4 ms 9820 KB Output is correct
27 Correct 4 ms 9820 KB Output is correct
28 Correct 5 ms 9816 KB Output is correct
29 Runtime error 20 ms 23244 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 71 ms 17912 KB Output is correct
4 Correct 71 ms 19148 KB Output is correct
5 Correct 71 ms 18816 KB Output is correct
6 Correct 71 ms 17896 KB Output is correct
7 Correct 69 ms 17908 KB Output is correct
8 Correct 67 ms 17728 KB Output is correct
9 Correct 66 ms 18120 KB Output is correct
10 Correct 70 ms 19148 KB Output is correct
11 Correct 74 ms 17868 KB Output is correct
12 Correct 75 ms 18992 KB Output is correct
13 Correct 75 ms 16940 KB Output is correct
14 Correct 76 ms 17448 KB Output is correct
15 Correct 73 ms 18348 KB Output is correct
16 Correct 70 ms 19148 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9856 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 5 ms 9820 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 4 ms 9908 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 5 ms 9744 KB Output is correct
11 Correct 5 ms 9816 KB Output is correct
12 Correct 4 ms 9820 KB Output is correct
13 Correct 4 ms 9820 KB Output is correct
14 Correct 5 ms 9820 KB Output is correct
15 Correct 4 ms 9884 KB Output is correct
16 Correct 7 ms 9820 KB Output is correct
17 Correct 4 ms 9724 KB Output is correct
18 Correct 4 ms 9816 KB Output is correct
19 Correct 4 ms 9832 KB Output is correct
20 Correct 5 ms 9824 KB Output is correct
21 Correct 5 ms 9820 KB Output is correct
22 Correct 5 ms 9820 KB Output is correct
23 Correct 4 ms 9820 KB Output is correct
24 Correct 4 ms 9820 KB Output is correct
25 Correct 4 ms 9820 KB Output is correct
26 Correct 4 ms 9820 KB Output is correct
27 Correct 4 ms 9820 KB Output is correct
28 Correct 5 ms 9816 KB Output is correct
29 Correct 71 ms 17912 KB Output is correct
30 Correct 71 ms 19148 KB Output is correct
31 Correct 71 ms 18816 KB Output is correct
32 Correct 71 ms 17896 KB Output is correct
33 Correct 69 ms 17908 KB Output is correct
34 Correct 67 ms 17728 KB Output is correct
35 Correct 66 ms 18120 KB Output is correct
36 Correct 70 ms 19148 KB Output is correct
37 Correct 74 ms 17868 KB Output is correct
38 Correct 75 ms 18992 KB Output is correct
39 Correct 75 ms 16940 KB Output is correct
40 Correct 76 ms 17448 KB Output is correct
41 Correct 73 ms 18348 KB Output is correct
42 Correct 70 ms 19148 KB Output is correct
43 Correct 402 ms 18020 KB Output is correct
44 Correct 998 ms 19392 KB Output is correct
45 Correct 939 ms 19032 KB Output is correct
46 Correct 122 ms 18000 KB Output is correct
47 Correct 125 ms 18000 KB Output is correct
48 Correct 343 ms 18272 KB Output is correct
49 Correct 567 ms 19340 KB Output is correct
50 Correct 614 ms 17756 KB Output is correct
51 Correct 523 ms 18512 KB Output is correct
52 Correct 465 ms 19284 KB Output is correct
53 Correct 412 ms 17236 KB Output is correct
54 Correct 337 ms 17752 KB Output is correct
55 Correct 472 ms 18464 KB Output is correct
56 Correct 582 ms 19188 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9856 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 5 ms 9820 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 4 ms 9908 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 5 ms 9744 KB Output is correct
11 Correct 5 ms 9816 KB Output is correct
12 Correct 4 ms 9820 KB Output is correct
13 Correct 4 ms 9820 KB Output is correct
14 Correct 5 ms 9820 KB Output is correct
15 Correct 4 ms 9884 KB Output is correct
16 Correct 7 ms 9820 KB Output is correct
17 Correct 4 ms 9724 KB Output is correct
18 Correct 4 ms 9816 KB Output is correct
19 Correct 4 ms 9832 KB Output is correct
20 Correct 5 ms 9824 KB Output is correct
21 Correct 5 ms 9820 KB Output is correct
22 Correct 5 ms 9820 KB Output is correct
23 Correct 4 ms 9820 KB Output is correct
24 Correct 4 ms 9820 KB Output is correct
25 Correct 4 ms 9820 KB Output is correct
26 Correct 4 ms 9820 KB Output is correct
27 Correct 4 ms 9820 KB Output is correct
28 Correct 5 ms 9816 KB Output is correct
29 Runtime error 20 ms 23244 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9856 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 5 ms 9820 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 4 ms 9908 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 5 ms 9744 KB Output is correct
11 Correct 5 ms 9816 KB Output is correct
12 Correct 4 ms 9820 KB Output is correct
13 Correct 4 ms 9820 KB Output is correct
14 Correct 5 ms 9820 KB Output is correct
15 Correct 4 ms 9884 KB Output is correct
16 Correct 7 ms 9820 KB Output is correct
17 Correct 4 ms 9724 KB Output is correct
18 Correct 4 ms 9816 KB Output is correct
19 Correct 4 ms 9832 KB Output is correct
20 Correct 5 ms 9824 KB Output is correct
21 Correct 5 ms 9820 KB Output is correct
22 Correct 5 ms 9820 KB Output is correct
23 Correct 4 ms 9820 KB Output is correct
24 Correct 4 ms 9820 KB Output is correct
25 Correct 4 ms 9820 KB Output is correct
26 Correct 4 ms 9820 KB Output is correct
27 Correct 4 ms 9820 KB Output is correct
28 Correct 5 ms 9816 KB Output is correct
29 Runtime error 20 ms 23244 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -