oj.uz

Submission #898229

# Submission time Handle Problem Language Result Execution time Memory
898229 2024-01-04T11:49:23 Z GrandTiger1729 Joker (BOI20_joker) C++17
14 / 100
 2000 ms 18368 KB 
#include <bits/stdc++.h>
using namespace std;

struct DSU
{
    vector<int> rt, sz;
    vector<int> stk;
    DSU(int n)
    {
        rt.resize(n);
        iota(rt.begin(), rt.end(), 0);
        sz.resize(n, 1);
    }
    int find(int u)
    {
        if (u == rt[u])
        {
            return u;
        }
        return find(rt[u]);
    }
    bool same(int u, int v)
    {
        return find(u) == find(v);
    }
    void unite(int u, int v)
    {
        u = find(u), v = find(v);
        if (u == v)
        {
            stk.push_back(-1);
            return;
        }
        if (sz[u] > sz[v])
        {
            swap(u, v);
        }
        rt[u] = v;
        sz[v] += sz[u];
        stk.push_back(u);
    }
    void undo()
    {
        int u = stk.back();
        stk.pop_back();
        if (u == -1)
        {
            return;
        }
        int v = rt[u];
        sz[v] -= sz[u];
        rt[u] = u;
    }
};

const int B = 450;
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, m, q;
    cin >> n >> m >> q;
    vector<pair<int, int>> ed(m);
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        u--, v--;
        ed[i] = make_pair(u, v);
    }
    vector<int> rr(m, -1);
    DSU dsu(2 * n);
    bool f = 0;
    for (int r = m - 1; r >= 0; r--)
    {
        if (f)
        {
            continue;
        }
        int l = 0;
        while (l <= r)
        {
            auto [u, v] = ed[l];
            dsu.unite(u, v + n);
            dsu.unite(u + n, v);
            if (dsu.same(u, v))
            {
                for (int j = 0; j <= l; j++)
                {
                    dsu.undo();
                    dsu.undo();
                }
                break;
            }
            l++;
        }
        rr[r] = l;
        auto [u, v] = ed[r];
        dsu.unite(u, v + n);
        dsu.unite(u + n, v);
        if (dsu.same(u, v))
        {
            f = 1;
        }
    }
    // for (int b = 0; b * B < m; b++)
    // {
    //     int l1 = b * B, l2 = min(m, (b + 1) * B);
    //     int r = -1;
    //     DSU dsu(2 * n);
    //     for (int i = 0; i < l1; i++)
    //     {
    //         auto [u, v] = ed[i];
    //         dsu.unite(u, v + n);
    //         dsu.unite(u + n, v);
    //         if (dsu.same(u, v))
    //         {
    //             r = i;
    //             break;
    //         }
    //     }
    //     if (r != -1)
    //     {
    //         break;
    //     }
    //     for (int i = l1; i < l2; i++)
    //     {
    //         auto [u, v] = ed[i];
    //         dsu.unite(u, v + n);
    //         dsu.unite(u + n, v);
    //         if (dsu.same(u, v))
    //         {
    //             r = i;
    //             break;
    //         }
    //     }
    //     if (r == -1)
    //     {
    //         r = m - 1;
    //         while (r >= l2)
    //         {
    //             auto [u, v] = ed[r];
    //             dsu.unite(u, v + n);
    //             dsu.unite(u + n, v);
    //             if (dsu.same(u, v))
    //             {
    //                 dsu.undo();
    //                 dsu.undo();
    //                 break;
    //             }
    //             r--;
    //         }
    //         for (int i = m - 1; i > r; i--)
    //         {
    //             dsu.undo();
    //             dsu.undo();
    //         }
    //         for (int i = l1; i < l2; i++)
    //         {
    //             dsu.undo();
    //             dsu.undo();
    //         }
    //     }
    //     else
    //     {
    //         for (int i = l1; i <= r; i++)
    //         {
    //             dsu.undo();
    //             dsu.undo();
    //         }
    //         r = m - 1;
    //     }
    //     for (int i = m - 1; i > r; i--)
    //     {
    //         auto [u, v] = ed[i];
    //         dsu.unite(u, v + n);
    //         dsu.unite(u + n, v);
    //     }
    //     for (int i = r; i >= l1 && !dsu.same(ed[i].first, ed[i].second); i--)
    //     {
    //         int l = l1;
    //         while (l < l2 && l <= i)
    //         {
    //             auto [u, v] = ed[l];
    //             dsu.unite(u, v + n);
    //             dsu.unite(u + n, v);
    //             if (dsu.same(u, v))
    //             {
    //                 for (int j = l1; j <= l; j++)
    //                 {
    //                     dsu.undo();
    //                     dsu.undo();
    //                 }
    //                 break;
    //             }
    //             l++;
    //         }
    //         rr[i] = l;
    //         auto [u, v] = ed[i];
    //         dsu.unite(u, v + n);
    //         dsu.unite(u + n, v);
    //     }
    // }
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        l--, r--;
        cout << (rr[r] >= l ? "NO" : "YES") << '\n';
    }
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 452 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 464 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 452 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 464 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 8 ms 6092 KB Output is correct
30 Correct 7 ms 348 KB Output is correct
31 Correct 6 ms 348 KB Output is correct
32 Correct 3 ms 544 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 5 ms 348 KB Output is correct
35 Correct 12 ms 348 KB Output is correct
36 Correct 7 ms 344 KB Output is correct
37 Correct 16 ms 344 KB Output is correct
38 Correct 21 ms 18368 KB Output is correct
39 Correct 2 ms 348 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 1 ms 348 KB Output is correct
43 Correct 2 ms 348 KB Output is correct
44 Correct 3 ms 472 KB Output is correct
45 Correct 4 ms 348 KB Output is correct
46 Correct 8 ms 348 KB Output is correct
47 Correct 4 ms 348 KB Output is correct
48 Correct 5 ms 468 KB Output is correct
49 Correct 5 ms 348 KB Output is correct
50 Correct 7 ms 348 KB Output is correct
51 Correct 2 ms 544 KB Output is correct
52 Correct 3 ms 552 KB Output is correct
53 Correct 5 ms 344 KB Output is correct
54 Correct 8 ms 348 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Execution timed out 2031 ms 7308 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 452 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 464 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Execution timed out 2031 ms 7308 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 452 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 464 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 8 ms 6092 KB Output is correct
30 Correct 7 ms 348 KB Output is correct
31 Correct 6 ms 348 KB Output is correct
32 Correct 3 ms 544 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 5 ms 348 KB Output is correct
35 Correct 12 ms 348 KB Output is correct
36 Correct 7 ms 344 KB Output is correct
37 Correct 16 ms 344 KB Output is correct
38 Correct 21 ms 18368 KB Output is correct
39 Correct 2 ms 348 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 1 ms 348 KB Output is correct
43 Correct 2 ms 348 KB Output is correct
44 Correct 3 ms 472 KB Output is correct
45 Correct 4 ms 348 KB Output is correct
46 Correct 8 ms 348 KB Output is correct
47 Correct 4 ms 348 KB Output is correct
48 Correct 5 ms 468 KB Output is correct
49 Correct 5 ms 348 KB Output is correct
50 Correct 7 ms 348 KB Output is correct
51 Correct 2 ms 544 KB Output is correct
52 Correct 3 ms 552 KB Output is correct
53 Correct 5 ms 344 KB Output is correct
54 Correct 8 ms 348 KB Output is correct
55 Execution timed out 2043 ms 6868 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 452 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 464 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 8 ms 6092 KB Output is correct
30 Correct 7 ms 348 KB Output is correct
31 Correct 6 ms 348 KB Output is correct
32 Correct 3 ms 544 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 5 ms 348 KB Output is correct
35 Correct 12 ms 348 KB Output is correct
36 Correct 7 ms 344 KB Output is correct
37 Correct 16 ms 344 KB Output is correct
38 Correct 21 ms 18368 KB Output is correct
39 Correct 2 ms 348 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 1 ms 348 KB Output is correct
43 Correct 2 ms 348 KB Output is correct
44 Correct 3 ms 472 KB Output is correct
45 Correct 4 ms 348 KB Output is correct
46 Correct 8 ms 348 KB Output is correct
47 Correct 4 ms 348 KB Output is correct
48 Correct 5 ms 468 KB Output is correct
49 Correct 5 ms 348 KB Output is correct
50 Correct 7 ms 348 KB Output is correct
51 Correct 2 ms 544 KB Output is correct
52 Correct 3 ms 552 KB Output is correct
53 Correct 5 ms 344 KB Output is correct
54 Correct 8 ms 348 KB Output is correct
55 Execution timed out 2031 ms 7308 KB Time limit exceeded
56 Halted 0 ms 0 KB -