Submission #1014696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014696		MODDI	Joker (BOI20_joker)	C++14	39 / 100	2045 ms	22096 KiB

Joker

#include <bits/stdc++.h>

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC optimize("O3")

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()

const int mxn = 2e5 + 100;

int n, m, q;
int dpt[mxn];

vector<int> g[mxn];
bool visited[mxn], ans;

void dfs(int cur, int par = -1, int d = 0) {
    if (ans) return;
    dpt[cur] = d;
    visited[cur] = 1;
    for (auto x : g[cur]) {
        if (visited[x] && x != par) {
            if (abs(dpt[cur] - dpt[x]) % 2 == 0) {
                ans = 1;
                return;
            }
        }
    }
    for (auto x : g[cur]) {
        if (x != par && !visited[x]) dfs(x, cur, d + 1);
    }
}

vector<pair<int, int>> v, qr;

bool pos(int mid) {
    for (int i = 1; i <= n; i++) g[i].clear(), visited[i] = 0, dpt[i] = 0;
    for (int i = mid; i < m; i++) {
        g[v[i].first].push_back(v[i].second);
        g[v[i].second].push_back(v[i].first);
    }
    ans = 0;
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) dfs(i);
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> q;
    v.resize(m);
    qr.resize(q);
    for (int i = 0; i < m; i++) cin >> v[i].first >> v[i].second;
    bool S3 = 1;
    for (int i = 0; i < q; i++) {
        cin >> qr[i].first >> qr[i].second;
        if (qr[i].first != 1) S3 = 0;
    }
    if (S3) {
        int l = -1, r = m;
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            if (pos(mid)) l = mid;
            else r = mid;
        }
        for (int i = 0; i < q; i++) {
            bool ans = (qr[i].second - 1) < l;
            cout << (ans ? "YES" : "NO") << endl;
        }
        return 0;
    }
    else {
        for (int j = 0; j < q; j++) {
            int l = qr[j].first, r = qr[j].second;
            l--;
            r--;
            for (int i = 1; i <= n; i++) {
                g[i].clear();
                visited[i] = 0;
                dpt[i] = 0;
            }
            for (int i = 0; i < l; i++) {
                g[v[i].first].push_back(v[i].second);
                g[v[i].second].push_back(v[i].first);
            }
            for (int i = r + 1; i < m; i++) {
                g[v[i].first].push_back(v[i].second);
                g[v[i].second].push_back(v[i].first);
            }
            ans = 0;
            for (int i = 1; i <= n; i++) {
                if (!visited[i]) dfs(i);
            }
            cout << (ans ? "YES" : "NO") << endl;
        }
    }
}

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