Submission #1167726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167726		knhatdev	Joker (BOI20_joker)	C++20	0 / 100	266 ms	30880 KiB

Joker

#include<bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define iv pair<ii, ii>
#define fi first
#define se second
#define task "ODD"
using namespace std;

const int N = 1e6 + 5, mod = 1e9 + 7;
int n, m, q, L, R, par[N], sz[N];
int check, ans[N];
vector<iv> his;
struct edge{
    int u, v;
} e[N];
struct query{
    int l, r, id;
} qr[N];


int acs(int u){
    while(u != par[u]) u = par[u];
    return u;
}

void join(int u, int v, int type){
    // cout << u << ' ' << v << '\n';
    u = acs(u); v = acs(v);
    if(u == v){
        // cout << "cc" << u << ' ' << v << '\n' << '\n';
        check++;
        his.push_back({{1, type}, {0, 0}});
    } else {
        // cout << u << ' ' << v << "vv\n";
        if(sz[u] < sz[v]) swap(u, v);
        his.push_back({{2, type}, {v, par[v]}});
        par[v] = u;
        sz[u] += sz[v];
    }
}

void rollback() {
    iv x = his.back();
    his.pop_back();
    if(x.fi.se == 1)
        L++;
    else if(x.fi.se == 2)
        R--;

    if(x.fi.fi == 1){
        check--;
    } else {
        int v = x.se.fi, parv = x.se.se;
        // cout << v << ' ' << parv << '\n';
        sz[par[v]] -= sz[v];
        par[v] = parv;
    }
}

void add(int id, int type){
    // cout << e[id].u << ' ' << e[id].v << ' ' << id << '\n';
    join(e[id].u + n, e[id].v, 0);
    join(e[id].u, e[id].v + n, type);
}
main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if(fopen(task ".inp", "r")){
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
    cin >> n >> m >> q;
    for(int i = 1; i <= 2*n; i++){
        par[i] = i;
        sz[i] = 1;
    }
    for(int i = 1; i <= m; i++){
        cin >> e[i].u >> e[i].v;
        e[i + m] = e[i];
    }
    for(int i = 1; i <= q; i++){
        cin >> qr[i].r >> qr[i].l;
        qr[i].l++;
        qr[i].r += m - 1;
        qr[i].id = i;
        // cout << qr[i].l << ' ' << qr[i].r << '\n';
    }
    sort(qr + 1, qr + 1 + q, [](query x, query y){
        int S = sqrt(m);
        if(x.l/S != y.l/S){
           return x.l/S < y.l/S;
        }
        return x.r < y.r;
    });
    L = m + 1, R = m;
    for(int i = 1; i <= q; i++){
        // cout << qr[i].id << ' ';
        // cout << L << ' ' << R << '\n';
        while(L < qr[i].l || R > qr[i].r){
            if(L == m + 1 && R == m)
                break;
            // cout << L << ' ' << R << '\n';
            rollback();
        }
        // cout << check << '\n';
        // cout << L << ' ' << R << '\n';
        // cout << qr[i].l << ' ' << qr[i].r << '\n';
        while(L > qr[i].l){
            add(--L, 1);
            // cout << L << ' ' << R << '\n';
        }
        while(R < qr[i].r){
            add(++R, 2);
            // cout << L << ' ' << R << '\n';
        }
        // cout << L << ' ' << R << '\n';
        // cout << L << ' ' << R << '\n';
        // cout << check << '\n';
        if(check)
            ans[qr[i].id] = 1;
        else
            ans[qr[i].id] = 0;
        // cout << '\n';
    }
    for(int i = 1; i <= q; i++)
        if(ans[i]) cout << "YES\n";
        else cout << "NO\n";
}

Compilation message (stderr)

Joker.cpp:66:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   66 | main(){
      | ^~~~
Joker.cpp: In function 'int main()':
Joker.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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