Submission #1006947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006947		underwaterkillerwhale	Joker (BOI20_joker)	C++17	14 / 100	2041 ms	28040 KiB

Joker

//#ifdef ONLINE_JUDGE
//    #include "cyberland.h"
//#endif

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N  = 3e5 + 2;
const ll Mod = 998244353;
const int szBL = 50;
const int INF = 1e9 + 7;
const int BASE = 137;

struct Query {
    int L, R;
};

int n, m, Q;
pair<int,int> edges[N];
Query qr[N];

namespace sub3 {
    vector<pair<int,int>> ke[N];
    int num[N], high[N];

    int time_dfs = 0, res = 0;
    void dfs (int u, int p, int L, int R) {
        num[u] = 1;
        high[u] = high[p] + 1;
        iter (&id, ke[u])  {
            int v, idx;
            tie (v, idx) = id;
            if (v == p || (idx >= L && idx <= R)) continue;
            if (!num[v]) {
                dfs (v, u, L, R);
            }
            else res = max(res, (high[u] - high[v] + 1) % 2);
        }
    }
    void solution() {
        rep (i, 1, m) {
            int u, v;
            tie(u, v) = edges[i];
            ke[u].push_back({v, i});
            ke[v].push_back({u, i});
        }
        rep (q, 1, Q) {
            int L = qr[q].L, R = qr[q].R;
            rep (u, 1, n) num[u] = 0;
            res = 0;
            rep (u, 1, n) {
                if (num[u]) continue;
                time_dfs = 0;
                dfs (u, 0, L, R);
            }
            if (res) cout << "YES\n";
            else cout <<"NO\n";
        }
    }
}

void solution() {
    cin >> n >> m >> Q;
    rep (i, 1, m) {
        cin >> edges[i].fs >> edges[i].se;
    }
    rep (i, 1, Q) {
        cin >> qr[i].L >> qr[i].R;
    }
    sub3 :: solution();

}
#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    file ("PAINT");
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}

/*
5 7
11011
query 1 2
query 1 2
query 1 2
query 3 4
toggle 3
query 3 4
query 1 2



3 2
0 1 5
0 2 5
1
1 2

*/

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