Submission #869051

#	Time	Username	Problem	Language	Result	Execution time	Memory
869051		prohacker	Joker (BOI20_joker)	C++14	0 / 100	101 ms	6988 KiB

Joker

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int,int>
#define mp make_pair

using namespace std;

const int N = 2e5+10;
const int INF = INT_MAX;
const int mod = 1e9+7;

int n,m,t;
pair<int,int> edges[N];
int color[N],lab[N];
int cnt,lst[N];
stack<int> st;

void make_set() {
    for(int i = 1 ; i <= n ; i++) {
        lab[i] = i;
        color[i] = 0;
    }
}

pii Find(int u) {
    if(u == lab[u]) {
        return pii(u,color[u]);
    }
    pii p = Find(lab[u]);
    lab[u] = p.first;
    color[u] = (color[u]^p.second);
    return pii(lab[u],color[u]);
}

void join(int u, int v) {
    pii hihi = Find(u);
    pii hehe = Find(v);
    if(hihi.first != hehe.first) {
        lab[hehe.first] = hihi.first;
        color[hehe.first] = (color[u]^color[v]^1);
        st.push(hehe.first);
        return;
    }
    if(hihi.second == hehe.second) {
        cnt++;
        st.push(-1);
    }
}

void roll_back(int lim) {
    while(st.size() > lim) {
        int p = st.top();
        st.pop();
        if(p == -1) {
            cnt--;
        }
        else {
            lab[p] = p;
            color[p] = 0;
        }
    }
}

void solve(int l, int r, int L, int R) {
    if(l > r) {
        return;
    }
    int mid = l + r >> 1;
    int lim1 = st.size();
    for(int i = l ; i <= mid ; i++) {
        join(edges[i].first,edges[i].second);
    }
    int lim2 = st.size();
    int best = R;
    while(best and !cnt) {
        best--;
        if(!best) {
            break;
        }
        join(edges[best].first,edges[best].second);
    }
    lst[mid] = best+1;
    roll_back(lim2);
    solve(mid+1,r,best,R);
    roll_back(lim1);
    for(int i = R-1 ; i >= max(l,best) ; i--) {
        join(edges[i].first,edges[i].second);
    }
    solve(l,mid-1,L,best);
    roll_back(lim1);
}

signed main()
{
    if (fopen("solve.inp", "r")) {
        freopen("solve.inp", "r", stdin);
        freopen("solve.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> t;
    for(int i = 1 ; i <= m ; i++) {
        int u,v; cin >> u >> v;
        edges[i] = {u,v};
    }
    make_set();
    edges[0] = {0,1};
    solve(0,m,0,m+1);
    while(t--) {
        int l,r; cin >> l >> r;
        if(r < lst[l-1]) {
            cout << "YES" << '\n';
        }
        else {
            cout << "NO" << '\n';
        }
    }
    return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'void roll_back(int)':
Joker.cpp:52:21: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |     while(st.size() > lim) {
      |           ~~~~~~~~~~^~~~~
Joker.cpp: In function 'void solve(int, int, int, int)':
Joker.cpp:69:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |     int mid = l + r >> 1;
      |               ~~^~~
Joker.cpp: In function 'int main()':
Joker.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen("solve.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen("solve.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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