Submission #1161766

#TimeUsernameProblemLanguageResultExecution timeMemory
116176612345678Joker (BOI20_joker)C++20
14 / 100
2095 ms15940 KiB
#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
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...