oj.uz

Submission #768235

# Submission time Handle Problem Language Result Execution time Memory
768235 2023-06-27T19:07:11 Z oyber Joker (BOI20_joker) C++14
25 / 100
 85 ms 9804 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <stack>
using namespace std;

vector<int> u;
vector<int> s;
vector<int> p;

int find(int n) {
    if (u[n] == n) return n;
    return find(u[n]);
}

int find_compress(int n) {
    if (u[n] == n) return n;
    int r = find_compress(u[n]); 
    if (p[u[n]] != p[r]) p[n] = !p[n];
    u[n] = r;
    return u[n];
}

int parity(int n) {
    if (u[n] == n) return 0;
    return parity(u[n])^p[n];
}

struct UniteInfo {
    int a;
    int b;
    int sa;
};

UniteInfo unite(int a, int b) {
    int ap = find(a);
    int bp = find(b);
    if (s[bp] > s[ap]) {
        swap(a, b);
        swap(ap, bp);
    }
    u[bp] = ap;
    s[ap] += s[bp];
    if (parity(a) == parity(b)) {
        p[bp] = 1;
    } else {
        p[bp] = 0;
    }
    return UniteInfo {
        ap,
        bp,
        s[ap] - s[bp],
    };
}

void undo(UniteInfo info) {
    u[info.b] = info.b;
    s[info.a] = info.sa;
    p[info.b] = 0;
}

struct Query {
    int l;
    int r;
    int i;
};

bool comp_query(Query q1, Query q2) {
    return q1.r > q2.r;
}

bool comp_query2(Query q1, Query q2) {
    return q1.l < q2.l;
}

int main() {
    int n, m, qn;
    scanf("%d %d %d", &n, &m, &qn);

    u.resize(n);
    s.resize(n, 1);
    p.resize(n);


    vector<pair<int, int>> e(m);
    for (int i = 0; i < m; i++) {
        int a, b; 
        scanf("%d %d", &a, &b);
        a--;b--;
        e[i] = make_pair(a, b);
        //printf("%d %d %d\n", a, b, i);
    }

    vector<Query> q(qn);
    for (int i = 0; i < qn; i++) {
        int l, r;
        scanf("%d %d", &l, &r);
        l--;r--;
        q[i] = Query{l,r,i};
    }
    sort(q.begin(), q.end(), comp_query2);

    int group_size = 1024;
    int group_num = q[q.size()-1].l / group_size + 1;
    //printf("%d %d\n", int(q[q.size()-1].l), group_num);
    vector<vector<Query>> groups(group_num);
    vector<int> min_l(group_num, 1000000);
    int j = 0;
    for (int i = 0; i < group_num; i++) {
        while (j < qn) {
            if (q[j].l >= (i+1)*group_size) break;
            groups[i].push_back(q[j]);
            min_l[i] = min(min_l[i], q[j].l);
            //printf("g: %d q: %d\n", i, q[j].i);
            j++;
        }
        sort(groups[i].begin(), groups[i].end(), comp_query);
    }

    vector<UniteInfo> infos;
    vector<bool> result(qn);
    for (int j = 0; j < group_num; j++) {
        if (groups[j].size() == 0) break;

        //reset state
        for (int i = 0; i < n; i++) {
            u[i] = i;
            s[i] = 1;
            p[i] = 0;
        }

        bool l_cycle = false;
        int current_l = 0;
        for (; current_l < min_l[j]; current_l++) {
            int a = e[current_l].first;
            int b = e[current_l].second;
            //printf("%d %d %d\n", current_l, a, b);
            if (find(a) == find(b)) {
                if (parity(a) == parity(b)) {
                    l_cycle = true;
                    break;
                }
            } else {
                unite(a, b);
            }
        }
        //printf("l: %d\n", current_l);


        int current_r = m-1;
        bool r_cycle = false;
        for (int i = 0; i < int(groups[j].size()); i++) {
            if (r_cycle || l_cycle) {
                result[groups[j][i].i] = true;
                continue;
            }
            int l = groups[j][i].l;
            int r = groups[j][i].r;
            //printf("%d: %d %d\n", i, l, r);

            while (current_r > r) {
                int a = e[current_r].first;
                int b = e[current_r].second;
                //printf("%d %d %d\n", current_r, a, b);
                if (find(a) == find(b)) {
                    if (parity(a) == parity(b)) {
                        r_cycle = true;
                        break;
                    }
                } else {
                    unite(a, b);
                }
                current_r--;
            }

            if (r_cycle) {
                result[groups[j][i].i] = true;
                continue;
            }

            bool cycle = false;
            for (int c_l = current_l; c_l < l; c_l++) {
                int a = e[c_l].first;
                int b = e[c_l].second;
                //printf("%d %d %d\n", current_l, a, b);
                if (find(a) == find(b)) {
                    if (parity(a) == parity(b)) {
                        cycle = true;
                        break;
                    }
                } else {
                    infos.push_back(unite(a, b));
                }
            }
            if (cycle) {
                result[groups[j][i].i] = true;
            }
            while (infos.size() > 0) {
                undo(infos.front());
                infos.pop_back();
            }
        }
    }

    for (int i = 0; i < qn; i++) {
        if (result[i]) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
}

Compilation message

Joker.cpp: In function 'int main()':
Joker.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     scanf("%d %d %d", &n, &m, &qn);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~
Joker.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         scanf("%d %d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 79 ms 8572 KB Output is correct
4 Correct 83 ms 9692 KB Output is correct
5 Correct 76 ms 9452 KB Output is correct
6 Correct 81 ms 8556 KB Output is correct
7 Correct 79 ms 8556 KB Output is correct
8 Correct 78 ms 8156 KB Output is correct
9 Correct 75 ms 8568 KB Output is correct
10 Correct 78 ms 9804 KB Output is correct
11 Correct 76 ms 8568 KB Output is correct
12 Correct 77 ms 9496 KB Output is correct
13 Correct 77 ms 7616 KB Output is correct
14 Correct 78 ms 8084 KB Output is correct
15 Correct 85 ms 9104 KB Output is correct
16 Correct 81 ms 9744 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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