Submission #1161766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161766		12345678	Joker (BOI20_joker)	C++20	14 / 100	2095 ms	15940 KiB

Joker

#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;

int n, m, q, u, v, c[nx], l, r, f;
vector<pair<int, int>> d[nx];

void dfs(int u, int p)
{
    for (auto [v, idx]:d[u])
    {
        if (v==p||(l<=idx&&idx<=r)) continue;
        if (c[v]==-1) c[v]=!c[u], dfs(v, u);
        else if (c[u]==c[v]) f=1;
    }
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>q;
    for (int i=1; i<=m; i++) cin>>u>>v, d[u].push_back({v, i}), d[v].push_back({u, i});
    while (q--)
    {
        cin>>l>>r;
        f=0;
        for (int i=1; i<=n; i++) c[i]=-1;
        for (int i=1; i<=n; i++) if (c[i]==-1) c[i]=1, dfs(i, -1);
        if (f) cout<<"YES\n";
        else cout<<"NO\n";
    }
}

/*
6 8 2
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
4 8
4 7
*/

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