Submission #1091397

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1091397	2024-09-20T18:58:15 Z	andrei_iorgulescu	Joker (BOI20_joker)	C++14	25 / 100	483 ms	20052 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4952 KB	Output is correct
2	Correct	3 ms	4956 KB	Output is correct
3	Runtime error	8 ms	10076 KB	Execution killed with signal 6
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4952 KB	Output is correct
2	Correct	3 ms	4956 KB	Output is correct
3	Runtime error	8 ms	10076 KB	Execution killed with signal 6
4	Halted	0 ms	0 KB	-

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4952 KB	Output is correct
2	Correct	3 ms	4956 KB	Output is correct
3	Correct	395 ms	17416 KB	Output is correct
4	Correct	467 ms	20052 KB	Output is correct
5	Correct	370 ms	15184 KB	Output is correct
6	Correct	415 ms	17492 KB	Output is correct
7	Correct	412 ms	17232 KB	Output is correct
8	Correct	392 ms	15952 KB	Output is correct
9	Correct	443 ms	17168 KB	Output is correct
10	Correct	448 ms	17484 KB	Output is correct
11	Correct	422 ms	16768 KB	Output is correct
12	Correct	436 ms	17196 KB	Output is correct
13	Correct	377 ms	14224 KB	Output is correct
14	Correct	405 ms	16580 KB	Output is correct
15	Correct	441 ms	18004 KB	Output is correct
16	Correct	483 ms	17744 KB	Output is correct