Submission #1316844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316844		mikolaj00	Joker (BOI20_joker)	C++20	14 / 100	2094 ms	13216 KiB

Joker

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;

    vector<pair<int, int>> edges(m+1);
    for (int i = 1; i <= m; i++)
        cin >> edges[i].first >> edges[i].second;

    for (int i = 0; i < q; i++)
    {
        int l, r;
        cin >> l >> r;

        vector<vector<int>> g(n+1);
        for (int j = 1; j <= m; j++)
        {
            if (l <= j && j <= r)
                continue;

            auto[u, v] = edges[j];
            g[u].push_back(v);
            g[v].push_back(u);
        }

        bool ok = false;
        vector<bool> vis(n+1);
        vector<bool> col(n+1);
        function<void(int, bool)> dfs = [&](int u, bool color) -> void
        {
            col[u] = color;
            vis[u] = true;
            for (auto v : g[u])
            {
                if (vis[v] && col[v] == color)
                    ok = true;

                if (!vis[v])
                    dfs(v, !color);
            }
        };
        for (int i = 1; i <= n; i++)
            if (!vis[i])
                dfs(i, true);

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

• Subtask 1: 8 / 8
• Subtask 2: 0 / 25
• Subtask 3: 0 / 10
• Subtask 4: 0 / 22
• Subtask 5: 0 / 29
• Subtask 6: 6 / 6