제출 #914305

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
914305		3as8	Joker (BOI20_joker)	C++14	39 / 100	820 ms	23700 KiB

Joker

#include <bits/stdc++.h>

#define ll long long
#define endl "\n"
#define fastIO cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false);

#define mid ((l + r) / 2)
#define lChild ((index * 2) + 1)
#define rChild ((index * 2) + 2)

using namespace std;

struct node {
    ll u, i;
};

bool bi(vector<vector<node> >& graph, vector<ll>& color, ll startIndex, ll p, ll col, ll l, ll r) {

    color[startIndex] = col;

    ll ret = true;
    for(auto [el, i] : graph[startIndex]) {
        if(el == p || (l <= i && i <= r)) continue;
        if(color[el] == -1) ret &= bi(graph, color, el, startIndex, !col, l, r);


        if(color[el] != -1 && color[el] == col) return false;
        if(color[el] != col) continue;

    }

    return ret;
}

bool check(vector<vector<node> >& graph, ll i, ll l = 0) {

    ll n = graph.size();

    vector<ll> col(n, -1);

    ll ans = true;
    for(int j = 0; j < n; j++) {
        if(col[j] != -1) continue;
        ans &= bi(graph, col, j, -1, 0, l, i);
    }

    return !ans;
}


void solve(ll _) {

    ll n, m, q; cin>>n>>m>>q;

    vector<vector<node> > graph(n);
    for(int i = 0; i < m; i++) {
        ll x, y; cin>>x>>y;
        x--; y--;

        graph[x].push_back({y, i});
        graph[y].push_back({x, i});
    }

    ll cnt = min({1ll, m - 1, 201ll});
    vector<ll> x(cnt);
    vector<bool> is(cnt);

    for(int k = 0; k < cnt; k++) {
        ll l = 0, r = m - 1;
        while (l < r) {

            bool ck = check(graph, mid, k);

            if (!ck) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        is[k] = check(graph, l, k);
        x[k] = l;
    }
    // cout<<" => "<<l<<" "<<r<<endl;

    for(int i = 0; i < q; i++) {
        ll l, r; cin>>l>>r;
        l--; r--;
        //l = 0, r = min(q - 1, (ll)i);

        if(n <= 2050 && q <= 2050) {

            cout<<(check(graph, r, l) ? "YES" : "NO")<<endl;
            continue;
        }
        if( x[l] < r) cout<<"NO"<<endl;
        else if(r < x[l]) cout<<"YES"<<endl;
        else {
            cout<<(is[l] ? "YES" : "NO")<<endl;
        }

    }

}

int main() {
    //fastIO

    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);

    ll t = 0; solve(t);
}

컴파일 시 표준 에러 (stderr) 메시지

Joker.cpp: In function 'bool bi(std::vector<std::vector<node> >&, std::vector<long long int>&, long long int, long long int, long long int, long long int, long long int)':
Joker.cpp:22:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |     for(auto [el, i] : graph[startIndex]) {
      |              ^

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