Submission #1054856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054856		cnastea	Joker (BOI20_joker)	C++14	14 / 100	410 ms	736 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
vector<int> a[2000];
map<pair<int, int>, int> t;
int l, r, c, b[2000], d[2000];

void dfs(int u, int p){
    if(c) return;
    for(int v : a[u]){
        if(v == p || (t[{min(u, v), max(u, v)}] >= l && t[{min(u, v), max(u, v)}] <= r) || c) continue;
        if(b[v] && (d[v] == d[u])) {c = 1; continue;}
        else if(b[v]) continue;
        b[v] = 1;
        d[v] = (d[u]+1)%2;
        dfs(v, u);
    }
}

int main(){
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 0; i < m; i++){
        int x, y;
        cin >> x >> y;
        x--; y--;
        t[{min(x, y), max(x, y)}] = i;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    while(q--){
        cin >> l >> r;
        l--; r--;
        for(int i = 0; i < n; i++) b[i] = 0;
        c = 0;
        for(int i = 0; i < n; i++){
            if(c || b[i]) continue;
            b[i] = 1;
            dfs(i, -1);
        }
        if(c) cout << "YES\n";
        else cout << "NO\n";
    }
}

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