Submission #1324193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1324193		888313666	Joker (BOI20_joker)	C++20	14 / 100	2094 ms	10604 KiB

Joker

#include <bits/stdc++.h>    
using namespace std;
typedef long long ll;
#define _ <<' '<<
#define print(x) cout<<#x<<": "<<(x)<<'\n'

int n,m,q,l,r;
bool val;
vector<vector<array<int, 2>>> adj;
vector<int> bip;

void dfs(const int u) {
    for (const auto [v, i]:adj[u]) if (i<l || r<i) {
        if (bip[v]==bip[u]) {
            //print(u);
            //print(v);
            //print(i);
            val=false;
        }
        else if (bip[v]==-1) {
            bip[v]=!bip[u];
            dfs(v);
        }
    } 
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    cin>>n>>m>>q;
    adj.resize(n);
    for (int i=0; i<m; i++) {
        int a,b;
        cin>>a>>b;
        adj[--a].push_back({--b, i});
        adj[b].push_back({a, i});
    }
    for (int i=0; i<q; i++) {
        cin>>l>>r;
        --l;
        --r;
        bip.assign(n, -1);
        val=1;
        for (int i=0; i<n; i++) if (bip[i]==-1) {
            bip[i]=0;
            dfs(i);
        }
        if (val) cout<<"NO\n";
        else cout<<"YES\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