Submission #1228435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228435		Aldas25	Joker (BOI20_joker)	C++20	14 / 100	2095 ms	7176 KiB

Joker

#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
 
#include <bits/stdc++.h>
 
using namespace std;
 
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<piii> viii;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MAXN = 1000100, MAXK = 23;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e16;
const ld PI = asin(1) * 2;
 
void setIO () {
    FAST_IO;
}
 
void setIO (string s) {
    setIO();
    freopen((s+".in").c_str(),"r",stdin);
    freopen((s+".out").c_str(),"w",stdout);
}
 
int n, m, q;
 
int cycleFound = 0;
int par[MAXN], sz[MAXN];
int unitCnt = 0;
 
 
 
//stack<pair<int, pii>> st; /// {v, par[v], sz[v]}
stack<int> st;
int find (int a) {
    if (par[a] == a) return a;
    //par[a] = find(par[a]);
    return find(par[a]);
}
bool same (int a, int b){
    return find(a) == find(b);
}
bool inCycle (int a) {
    int nA = (a > n ? (a-n) : (a+n));
    return same(a, nA);
}
void unite (int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return;
 
 
   // bool wassame = same(a, nA);
 
    if (sz[a] < sz[b]) swap(a,b);
 
    //sizes.push(st.size());
    //st.push({b, {par[b], sz[b]});
    st.push(b);
    unitCnt++;
    par[b] = a;
    sz[a] += sz[b];
 
    if (inCycle(b)) {
        cycleFound++;
       // cout << " cyclefoind = " << a << " " << nA << endl;
    }
}
void rollback() {
    /*auto pp = st.top();
    st.pop();
    int b = st.f;
    int prevPar = st.s.f;
    int prevSz = st.s.s;
    sz[b] = prevSz;
    sz[par[b]] -= sz[b];
    par[b] = prevPar;*/
 
    int b = st.top();
    if (inCycle(b)) cycleFound--;
    st.pop();
    sz[par[b]] -= sz[b];
    par[b] = b;
    unitCnt--;
}
void resetDSU () {
    while (!st.empty()) {st.pop();}
    FOR(i ,1 ,2*n) par[i] = i;
    FOR(i ,1, 2*n) sz[i] = 1;
    cycleFound = false;
    unitCnt= 0;
}
 
 
//vi adj[MAXN];
 
pii edges[MAXN];
 
void addE (int id) {
    if (id > m) return;
    if (id < 1) return;
    int u = edges[id].f;
    int v = edges[id].s;
    unite (u, v+n);
    unite (v, u+n);
   // cout <<"  added " << u << "-" << (v+n) << "  and  " << v << "-" << (u+n) << endl;
}
 
int last[MAXN];
 
void rec (int l1, int l2, int r1, int r2) {
 
    int tmp = unitCnt;
 
    int lmid = (l1+l2)/2;
    FOR(i, l1, lmid-1) addE(i);
 
    int rmid;
 
    for (int i = r2; i >= r1; i--){
        addE(i);
        if (cycleFound) {
            last[lmid] = i;
            rmid = i;
            break;
        }
    }
 
   // cout << "   rec [" << l1 << "," << l2 << "]  [" << r1 << "," << r2 << "]" << endl;
   // cout << "  lmid = " << lmid << " rmid = " << rmid << endl;
 
    while (unitCnt > tmp) {
        rollback();
    }
 
    if (l1 <= lmid-1) {
        FOR(i, rmid+1, r2) addE(i);
        rec(l1, lmid-1, r1, rmid);
    }
 
    while (unitCnt > tmp) {
        rollback();
    }
 
    if(lmid+1 <= l2) {
        FOR(i, l1, lmid) addE(i);
        rec(lmid+1, l2, max(lmid+1, r1), r2);
    }
 
    while (unitCnt > tmp) {
        rollback();
    }
}
 
int main() {
    setIO();
 
    cin >> n >> m >> q;
    FOR(i, 1, m) {
        int u, v; cin >> u >> v;
        edges[i] = {u,v};
    }
 
    resetDSU();
 
    rec(1, m, 1, m+1);
 
   // FOR(i ,1, m) cout << " i = " << i << "  last =  "<< last[i] << endl;
 
    REP(q) {
        int le, ri; cin >> le >> ri;
        if (ri < last[le]) cout << "YES\n";
        else cout << "NO\n";
    }
 
    return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'void setIO(std::string)':
Joker.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen((s+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen((s+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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