Submission #450446

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
450446	2021-08-02T22:36:01 Z	mjhmjh1104	Joker (BOI20_joker)	C++17	25 / 100	112 ms	8932 KB

Joker

#include <cstdio>
#include <vector>
#include <utility>
using namespace std;

int uf[200006], sz[200006], ds[200006];

int _find(int x) {
    if (uf[x] == -1) return x;
    return _find(uf[x]);
}

int _dist(int x) {
    if (uf[x] == -1) return 0;
    return ds[x] + _dist(uf[x]);
}

bool _merge(int x, int y) {
    int a = _dist(x), b = _dist(y);
    x = _find(x), y = _find(y);
    if (x != y) {
        if (sz[x] > sz[y]) {
            uf[y] = x, sz[x] += sz[y];
            if ((a + b) % 2 == 0) ds[y]++;
        } else {
            uf[x] = y, sz[y] += sz[x];
            if ((a + b) % 2 == 0) ds[x]++;
        }
        return true;
    }
    return false;
}

int n, m, q;
vector<pair<int, int>> edges;

int main() {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        u--, v--;
        edges.push_back({ u, v });
    }
    for (int i = 0; i < n; i++) uf[i] = -1, sz[i] = 1, ds[i] = 0;
    int x = -1;
    for (int i = m - 1; i >= 0; i--) if (!_merge(edges[i].first, edges[i].second) && (_dist(edges[i].first) + _dist(edges[i].second) + 1) % 2) {
        x = i;
        break;
    }
    for (int i = 0; i < q; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        l--, r--;
        if (r < x) puts("YES");
        else puts("NO");
    }
}

Compilation message

Joker.cpp: In function 'int main()':
Joker.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d%d%d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~
Joker.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%d%d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	92 ms	3764 KB	Output is correct
4	Correct	111 ms	4824 KB	Output is correct
5	Correct	96 ms	4736 KB	Output is correct
6	Correct	94 ms	7748 KB	Output is correct
7	Correct	98 ms	7744 KB	Output is correct
8	Correct	94 ms	6704 KB	Output is correct
9	Correct	93 ms	7176 KB	Output is correct
10	Correct	99 ms	8620 KB	Output is correct
11	Correct	99 ms	7628 KB	Output is correct
12	Correct	101 ms	8768 KB	Output is correct
13	Correct	112 ms	6584 KB	Output is correct
14	Correct	98 ms	7404 KB	Output is correct
15	Correct	101 ms	8156 KB	Output is correct
16	Correct	100 ms	8932 KB	Output is correct