Submission #1160951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160951		patgra	Joker (BOI20_joker)	C++20	25 / 100	178 ms	7616 KiB

Joker

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

constexpr int maxn = 2e5 + 7;
pair<int, int> edges[maxn];
int rep[maxn], repRelation[maxn], depth[maxn];
stack<pair<pair<int, int>, int>> stck; // if added: {{a, b}, depth[a]}; else: {{-1, -1}, [caused contradiction]}
stack<int> stck2;
bool currentlyWrong;
int n, M, q;
int prefSuf[maxn]; // with first i edges, how many must we take from the back (its index)

pair<int, int> fuFind(int x) { 
    if(rep[x] == x) return {x, 0};
    auto [rp, rl] = fuFind(rep[x]);
    rl ^= repRelation[x];
    return {rp, rl};
}
void addEdge(int i) {
    DEBUG {
        DC << " Adding edge " << i + 1 << eol;
        stck2.push(i);
    }
    auto [a, b] = edges[i];
    auto [ra, rla] = fuFind(a);
    auto [rb, rlb] = fuFind(b);
    if(ra == rb) {
        stck.push({{-1, -1}, !currentlyWrong && (rla == rlb)});
        currentlyWrong = currentlyWrong || (rla == rlb);
        return;
    }
    if(depth[ra] < depth[rb]) swap(a, b), swap(ra, rb), swap(rla, rlb);
    stck.push({{ra, rb}, depth[ra]});
    rep[rb] = ra;
    repRelation[rb] = rla == rlb;
    depth[ra] = max(depth[ra], depth[rb] + 1);
}
void undoEdge() {
    DEBUG {
        DC << " Undoing edge " << stck2.top() + 1 << eol;
        stck2.pop();
    }
    auto [ab, c] = stck.top();
    auto [a, b] = ab;
    stck.pop();
    if(a == -1) if(c) currentlyWrong = false;
    if(a != -1) {
        rep[b] = b;
        repRelation[b] = 0;
        depth[a] = c;
    }
}

void calcPrefSuf(int l, int r, int a, int b) { // edges added:  before l - 1   and after b
    if(l > r) return;
    int m = (l + r) / 2;
    DC << ' ' << l << ' ' << r << ' ' << a << ' ' << b << eol;
    DC << " calculating  ps[" << m << "]" << eol;
    DEBUG {
        DC << "Currently added edges: ";
        stack<int> s3;
        while(!stck2.empty()) {
            DC << stck2.top() + 1 << ' ';
            s3.push(stck2.top());
            stck2.pop();
        }
        DC << eol;
        while(!s3.empty()) stck2.push(s3.top()), s3.pop();
    }
    rep(i, l, m) addEdge(i);
    prefSuf[m] = b;
    while(!currentlyWrong && prefSuf[m] >= m) addEdge(prefSuf[m]--);
    int tmp = prefSuf[m];
    while(tmp < b) tmp++, undoEdge();
    addEdge(m);
    calcPrefSuf(m + 1, r, prefSuf[m] + 1, b);
    rep(i, l, m + 1) undoEdge();
    while(tmp > prefSuf[m]) addEdge(tmp--);
    calcPrefSuf(l, m - 1, a, tmp);
    while(tmp < b) undoEdge(), tmp++;
    prefSuf[m]++;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> M >> q;
    rep(i, 0, M) cin >> edges[i].first >> edges[i].second;
    rep(i, 1, n + 1) rep[i] = i;
    calcPrefSuf(0, n + 1, 0, M - 1);
    DEBUG {
        DC << "PrefSuf: ";
        rep(i, 0, n + 1) DC << prefSuf[i] + 1 << ' ';
        DC << eol;
    }
    rep(i, 0, q) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        cout << (prefSuf[a] > b ? "YES" : "NO") << '\n';
    }
}

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