Submission #1308704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308704		Born_To_Laugh	Joker (BOI20_joker)	C++17	14 / 100	2095 ms	7868 KiB

Joker

// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7;

const int maxn = 2e5 + 10;
int n, m, q;
vector<pair<int, int>> edges(maxn);

namespace sub5
{
    vector<vector<int>> adj;
    vector<int> col;
    bool bfs(int a){
        deque<int> bfs;
        col[a] = 1;
        bfs.push_back(a);

        while(!bfs.empty()){
            int x = bfs.front();
            bfs.pop_front();
            for(auto &elm: adj[x]){
                if(col[elm] != 0 && col[elm] != 3 - col[x]){
                    return 1;
                }
                if(col[elm] == 0){
                    col[elm] = 3 - col[x];
                    bfs.push_back(elm);
                }
            }
        }
        return 0;
    }
    bool ope(int l, int r){
        adj.assign(n + 1, vector<int>());
        col.assign(n + 1, 0);

        for(int i=1; i<l; ++i){
            int a = edges[i].fi;
            int b = edges[i].se;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        for(int i=r + 1; i<=m; ++i){
            int a = edges[i].fi;
            int b = edges[i].se;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }

        for(int i=1; i<=n; ++i){
            if(col[i] != 0)continue;
            if(bfs(i)){
                return 1;
            }
        }
        return 0;
    }
    void solve(){
        while(q--){
            int l, r;cin >> l >> r;
            if(ope(l, r))cout << "YES\n";
            else cout << "NO\n";
        }
    }
};

void solve(){
    cin >> n >> m >> q;
    for(int i=1; i<=m; ++i){
        cin >> edges[i].fi >> edges[i].se;
    }
    if(q <= 2000){
        sub5::solve();
        return;
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

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