oj.uz

Submission #765447

# Submission time Handle Problem Language Result Execution time Memory
765447 2023-06-24T13:34:22 Z oyber Joker (BOI20_joker) C++14
25 / 100
 96 ms 10180 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 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;
}

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

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

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

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

    for (int i = 0; i < n; i++) {
        u[i] = i;
    }

    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_query);

    vector<bool> result(qn);
    int current_r = m-1;
    bool r_cycle = false;
    for (int i = 0; i < qn; i++) {
        if (r_cycle) {
            result[q[i].i] = true;
            continue;
        }
        int l = q[i].l;
        int r = q[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[q[i].i] = true;
            continue;
        }

        bool cycle = false;
        int current_l = 0;
        stack<UniteInfo> infos;
        while (current_l < 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)) {
                    cycle = true;
                    break;
                }
            } else {
                infos.push(unite(a, b));
            }
            current_l++;
        }
        if (cycle) {
            result[q[i].i] = true;
        }
        while (infos.size() > 0) {
            undo(infos.top());
            infos.pop();
        }
    }

    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:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     scanf("%d %d %d", &n, &m, &qn);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~
Joker.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         scanf("%d %d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 78 ms 5968 KB Output is correct
4 Correct 81 ms 7056 KB Output is correct
5 Correct 80 ms 7084 KB Output is correct
6 Correct 77 ms 9004 KB Output is correct
7 Correct 78 ms 6988 KB Output is correct
8 Correct 74 ms 6996 KB Output is correct
9 Correct 75 ms 7116 KB Output is correct
10 Correct 76 ms 9860 KB Output is correct
11 Correct 78 ms 8980 KB Output is correct
12 Correct 96 ms 9976 KB Output is correct
13 Correct 81 ms 6088 KB Output is correct
14 Correct 79 ms 8556 KB Output is correct
15 Correct 81 ms 9560 KB Output is correct
16 Correct 80 ms 10180 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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