Submission #1091397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091397		andrei_iorgulescu	Joker (BOI20_joker)	C++14	25 / 100	483 ms	20052 KiB

Joker

#include <bits/stdc++.h>

using namespace std;

int n, m, q;
int u[200005], v[200005];
vector<int> g[200005];
bool viz[200005];
int tip[200005];
bool cst;

void dfs(int nod)
{
    viz[nod] = true;
    for (auto vecin : g[nod])
    {
        if (!viz[vecin])
        {
            tip[vecin] = 1 - tip[nod];
            dfs(vecin);
        }
        else
        {
            if (tip[vecin] == tip[nod])
                cst = true;
        }
    }
}

bool win(int k)
{
    for (int i = 1; i <= n; i++)
        g[i].clear();
    for (int i = k + 1; i <= m; i++)
    {
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    for (int i = 1; i <= n; i++)
        viz[i] = false, tip[i] = 0;
    cst = false;
    for (int i = 1; i <= n; i++)
        if (!viz[i])
            dfs(i);
    return cst;
}

int main()
{
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++)
        cin >> u[i] >> v[i];
    int st = 0, pas = 1 << 17;
    while (pas != 0)
    {
        if (st + pas <= m and win(st + pas))
            st += pas;
        pas /= 2;
    }
    for (int i = 1; i <= q; i++)
    {
        int x,y;
        cin >> x >> y;
        assert(x == 1 and x <= y and y <= m);
        if (y <= st)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}

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