oj.uz

Submission #1031132

# Submission time Handle Problem Language Result Execution time Memory
1031132 2024-07-22T15:18:09 Z kl0989e Joker (BOI20_joker) C++17
0 / 100
 220 ms 42232 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
#define all(x) (x).begin(),(x).end()

const int maxn=2e5+10;
vector<pi> edge(maxn);
vi head(maxn);
vi col(maxn,1);
vi depth(maxn,1);
vector<vi> changes;
bool is_bipartite=1;

pi get(int a) {
    if (a==head[a]) {
        return {a,col[a]};
    }
    else {
        pi temp=get(head[a]);
        temp.se^=col[a];
        return temp;
    }
}

void unite(int a, int b) {
    int cola,colb;
    //cout << a << ' ' << b << '\n';
    tie(a,cola)=get(a);
    tie(b,colb)=get(b);
    if (a==b) {
        if (cola==colb && is_bipartite) {
            is_bipartite=0;
        }
    }
    if (depth[a]<depth[b]) {
        swap(a,b);
    }
    changes.pb({b,head[b],col[b],a,int(depth[a]==depth[b])});
    head[b]=a;
    col[b]=cola^colb^1;
    depth[a]+=int(depth[a]==depth[b]);
}

void rollback(int k) {
    while (changes.size()>k) {
        vi t=changes.back();
        changes.pop_back();
        head[t[0]]=t[1];
        col[t[0]]=t[2];
        depth[t[3]]-=t[4];
    }
}

int n,m,q;
vector<bool> ans(maxn);
vector<vector<vi>> queries(maxn);
vi mn(4*maxn,1e9),mx(4*maxn,-1e9);

void add(int l, int r, int i, int v=1, int tl=0, int tr=m-1) {
    mn[v]=min(mn[v],l);
    mx[v]=max(mx[v],r);
    if (tl==tr) {
        queries[tl].pb({l,r,i});
    }
    else {
        int tm=tl+(tr-tl)/2;
        if (l<=tm) {
            add(l,r,i,v*2,tl,tm);
        }
        else {
            add(l,r,i,v*2+1,tm+1,tr);
        }
    }
}

void dfs(int l_added=0, int r_added=m-1, int v=1, int tl=0, int tr=m-1) {
    if (mn[v]==1e9) {
        return;
    }
    bool temp_is_bip=is_bipartite;
    int temp_sze=changes.size();
    while (l_added<mn[v]) {
        unite(edge[l_added].fi,edge[l_added].se);
        l_added++;
        if (!is_bipartite) {
            l_added=m;
            r_added=-1;
        }
    }
    while (r_added>mx[v]) {
        unite(edge[r_added].fi,edge[r_added].se);
        r_added--;
        if (!is_bipartite) {
            l_added=m;
            r_added=-1;
        }
    }
    if (tl==tr) {
        sort(all(queries[tl]),[](vi a, vi b){return a[1]>b[1];});
        for (auto temp:queries[tl]) {
            while (r_added>temp[1]) {
                unite(edge[r_added].fi,edge[r_added].se);
                r_added--;
                if (!is_bipartite) {
                    r_added=-1;
                }
            }
            ans[temp[2]]=is_bipartite;
        }
    }
    else {
        int tm=tl+(tr-tl)/2;
        dfs(l_added,r_added,v*2,tl,tm);
        dfs(l_added,r_added,v*2+1,tm+1,tr);
    }
    is_bipartite=temp_is_bip;
    rollback(temp_sze);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    iota(all(head),0);
    for (int i=0; i<m; i++) {
        cin >> edge[i].fi >> edge[i].se;
        edge[i].fi--;
        edge[i].se--;
    }
    int l,r;
    for (int i=0; i<q; i++) {
        cin >> l >> r;
        add(l-1,r-1,i);
    }
    dfs();
    for (int i=0; i<q; i++) {
        cout << (ans[i]?"NO\n":"YES\n");
    }
    return 0;
}

Compilation message

Joker.cpp: In function 'void rollback(int)':
Joker.cpp:51:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |     while (changes.size()>k) {
      |            ~~~~~~~~~~~~~~^~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15196 KB Output is correct
2 Correct 6 ms 15196 KB Output is correct
3 Correct 6 ms 15356 KB Output is correct
4 Correct 8 ms 15196 KB Output is correct
5 Correct 6 ms 15376 KB Output is correct
6 Correct 6 ms 15196 KB Output is correct
7 Correct 6 ms 15196 KB Output is correct
8 Incorrect 6 ms 15196 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15196 KB Output is correct
2 Correct 6 ms 15196 KB Output is correct
3 Correct 6 ms 15356 KB Output is correct
4 Correct 8 ms 15196 KB Output is correct
5 Correct 6 ms 15376 KB Output is correct
6 Correct 6 ms 15196 KB Output is correct
7 Correct 6 ms 15196 KB Output is correct
8 Incorrect 6 ms 15196 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15196 KB Output is correct
2 Correct 6 ms 15196 KB Output is correct
3 Correct 220 ms 36856 KB Output is correct
4 Correct 199 ms 42232 KB Output is correct
5 Correct 191 ms 32504 KB Output is correct
6 Correct 202 ms 36896 KB Output is correct
7 Correct 194 ms 36896 KB Output is correct
8 Incorrect 184 ms 31992 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15196 KB Output is correct
2 Correct 6 ms 15196 KB Output is correct
3 Correct 6 ms 15356 KB Output is correct
4 Correct 8 ms 15196 KB Output is correct
5 Correct 6 ms 15376 KB Output is correct
6 Correct 6 ms 15196 KB Output is correct
7 Correct 6 ms 15196 KB Output is correct
8 Incorrect 6 ms 15196 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15196 KB Output is correct
2 Correct 6 ms 15196 KB Output is correct
3 Correct 6 ms 15356 KB Output is correct
4 Correct 8 ms 15196 KB Output is correct
5 Correct 6 ms 15376 KB Output is correct
6 Correct 6 ms 15196 KB Output is correct
7 Correct 6 ms 15196 KB Output is correct
8 Incorrect 6 ms 15196 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15196 KB Output is correct
2 Correct 6 ms 15196 KB Output is correct
3 Correct 6 ms 15356 KB Output is correct
4 Correct 8 ms 15196 KB Output is correct
5 Correct 6 ms 15376 KB Output is correct
6 Correct 6 ms 15196 KB Output is correct
7 Correct 6 ms 15196 KB Output is correct
8 Incorrect 6 ms 15196 KB Output isn't correct
9 Halted 0 ms 0 KB -