Submission #1108711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108711		AverageAmogusEnjoyer	Joker (BOI20_joker)	C++17	14 / 100	2070 ms	22344 KiB

Joker

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }

constexpr int nax = 200200;
vector<pair<int,int>> adj[nax];
int color[nax];
pair<int,int> stk[nax];
int p = 0;

vector<bool> trova_cicli(int N, int M, int Q, vector<int> A, vector<int> B, vector<int> L, vector<int> R) {
    vector<bool> ans(Q);
    for (int i = 0; i < M; i++) {
        adj[A[i]].emplace_back(B[i],i);
        adj[B[i]].emplace_back(A[i],i);
    }
    for (int i = 0; i < Q; i++) {
        memset(color,-1,4 * N);
        int l = L[i], r = R[i];
        for (int current_node = 0; current_node < N && !ans[i]; current_node++) if (color[current_node] == -1) {
            p = 0;
            stk[p] = {current_node,0};
            color[current_node] = 0;
            while(p != -1) {
                auto &[node,idx_adj] = stk[p];
                // cout << node << " " << idx_adj << endl;
                while(idx_adj < adj[node].size() && (l <= adj[node][idx_adj].second && adj[node][idx_adj].second < r))
                    idx_adj++;
                if (idx_adj == adj[node].size()) {
                    p--;
                    continue;
                }
                int &other_node = adj[node][idx_adj].first;
                if (color[other_node] == color[node]) {
                    ans[i] = 1;
                    break;
                }
                if (color[other_node] != -1) {
                    idx_adj++;
                    continue;
                }
                color[other_node] = color[node] ^ 1;
                stk[++p] = {other_node,0}; 
            }
        }
    }
    return ans;
}

int main() {

    int N,M,Q;
    cin >> N >> M >> Q;
    vector<int> A(M),B(M),L(Q),R(Q);
    for (int i = 0; i < M; i++) {
        cin >> A[i] >> B[i];
        --A[i],--B[i];
    }
    for (int i = 0; i < Q; i++) {
        cin >> L[i] >> R[i];
        --L[i];
    }
    auto res = trova_cicli(N,M,Q,A,B,L,R);
    for (int i = 0; i < Q; i++) 
        cout << (res[i] ? "YES" : "NO") << "\n";

}

Compilation message (stderr)

Joker.cpp: In function 'std::vector<bool> trova_cicli(int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
Joker.cpp:31:31: warning: comparison of integer expressions of different signedness: 'std::tuple_element<1, std::pair<int, int> >::type' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |                 while(idx_adj < adj[node].size() && (l <= adj[node][idx_adj].second && adj[node][idx_adj].second < r))
      |                       ~~~~~~~~^~~~~~~~~~~~~~~~~~
Joker.cpp:33:29: warning: comparison of integer expressions of different signedness: 'std::tuple_element<1, std::pair<int, int> >::type' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |                 if (idx_adj == adj[node].size()) {
      |                     ~~~~~~~~^~~~~~~~~~~~~~~~~~~

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