Submission #751926

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
751926	2023-06-01T20:14:47 Z	Ronin13	Joker (BOI20_joker)	C++14	Compilation error	0 ms	0 KB

Joker

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
#define pii pair<int,int>
using namespace std;
const int nmax = 400001;
 
stack <pair<pair<int, bool> , pair<int, bool> > > st;
 
pii p[nmax];
int sz[nmax];
bool good[nmax];
void make_set(int v){
    p[v] = {v, 0};
    sz[v] = 1;
    good[v] = true;
}
 
pair <int,int> find_set(int v){
    if(v == p[v].f){
        return {v, 0};
    }
    pii x = find_set(p[v].f);
    return {x.f, x.s ^ p[v].s};
}
 
bool union_sets(int a, int b){
    pii A = find_set(a);
    pii B = find_set(b);
    if(A.f == B.f){
        st.push({{A.f, good[A.f]}, {A.f, good[A.f]}});
        good[A.f] &= (A.s != B.s);
        return good[A.f];
    }
    if(sz[A.f] < sz[B.f])
        swap(A, B);
    st.push({{B.f, good[B.f]}, {A.f, good[A.f]}});
    good[A.f] &= good[B.f];
    sz[A.f] += sz[B.f];
    p[B.f] = {A.f, A.s ^ B.s ^ 1};
 
    return good[A.f];
}
 
void rollback(int Sz){
    while(st.size() > Sz){
        int x = st.top().f.f;
        p[x] = {x, 0};
      if(x != st.top().s.f){
        good[x] = st.top().f.s;
        good[st.top().s.f] = st.top().s.s;
        sz[st.top().s.f] -=sz[st.top().f.f];}
        st.pop();
    }
}
 
int u[nmax], v[nmax];
int ans[nmax];
bool good1;
void divi(int l1, int l2, int r1, int r2){
    if(l1 > l2) return;
    int m = (l1 + l2) / 2;
    int s1 = st.size();
    bool good = good1;
    bool pr = good1;
    for(int i = l1; i < m; i++)
        good &= union_sets(u[i], v[i]);
    good1 = good;
    int s = st.size();
    ans[m] = m;
    for(int i = r2; i >= r1; i--){
        if(!good){ ans[m] = i + 1; break;}
        if(i == m){
            ans[m] = i;
            break;
        }
        good &= union_sets(u[i], v[i]);
    }
    rollback(s);
    good1 &= union_sets(u[m], v[m]);
    divi(m + 1, l2, ans[m], r2);
    rollback(s1);
    int s2 = st.size();
    bool pr1 = pr;
    good1 = pr;
    for(int i = r2; i > ans[m]; i--){
        good1 &= union_sets(v[i], u[i]);
    }
    divi(l1, m - 1, r1, ans[m]);
    rollback(s2);
    good1 = pr1;
}
 
int main(){
    good1 = true;
    int n, m, q; cin >> n >> m >> q;
    for(int i = 1; i <= n; i++)
        make_set(i);
    for(int i = 1; i <= m; i++){
        cin >> u[i] >> v[i];
    }
    divi(1, m, 1, m);
 
    while(q--){
        int l, r; cin >>l >> r;
        r < ans[l] ? cout << "YES\n" : cout << "NO\n";
    }
}

Compilation message

Joker.cpp:54:2: error: extended character   is not valid in an identifier
   54 |       if(x != st.top().s.f){
      |  ^
Joker.cpp:54:5: error: extended character   is not valid in an identifier
   54 |       if(x != st.top().s.f){
      |    ^
Joker.cpp:54:8: error: extended character   is not valid in an identifier
   54 |       if(x != st.top().s.f){
      |      ^
Joker.cpp:55:2: error: extended character   is not valid in an identifier
   55 |         good[x] = st.top().f.s;
      |  ^
Joker.cpp:55:5: error: extended character   is not valid in an identifier
   55 |         good[x] = st.top().f.s;
      |    ^
Joker.cpp:55:8: error: extended character   is not valid in an identifier
   55 |         good[x] = st.top().f.s;
      |      ^
Joker.cpp:55:11: error: extended character   is not valid in an identifier
   55 |         good[x] = st.top().f.s;
      |        ^
Joker.cpp:57:2: error: extended character   is not valid in an identifier
   57 |         sz[st.top().s.f] -=sz[st.top().f.f];}
      |  ^
Joker.cpp:57:5: error: extended character   is not valid in an identifier
   57 |         sz[st.top().s.f] -=sz[st.top().f.f];}
      |    ^
Joker.cpp:57:8: error: extended character   is not valid in an identifier
   57 |         sz[st.top().s.f] -=sz[st.top().f.f];}
      |      ^
Joker.cpp:57:11: error: extended character   is not valid in an identifier
   57 |         sz[st.top().s.f] -=sz[st.top().f.f];}
      |        ^
Joker.cpp:58:2: error: extended character   is not valid in an identifier
   58 |         st.pop();
      |  ^
Joker.cpp:58:5: error: extended character   is not valid in an identifier
   58 |         st.pop();
      |    ^
Joker.cpp:58:8: error: extended character   is not valid in an identifier
   58 |         st.pop();
      |      ^
Joker.cpp:58:11: error: extended character   is not valid in an identifier
   58 |         st.pop();
      |        ^
Joker.cpp: In function 'void rollback(int)':
Joker.cpp:51:21: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<std::pair<int, bool>, std::pair<int, bool> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |     while(st.size() > Sz){
      |           ~~~~~~~~~~^~~~
Joker.cpp:54:2: error: '\U000000a0' was not declared in this scope
   54 |       if(x != st.top().s.f){
      |  ^
Joker.cpp:58:4: error: expected ';' before '\U000000a0'
   58 |         st.pop();
      |   ^~
      |   ;