제출 #1299323

#제출 시각아이디문제언어결과실행 시간메모리
1299323hiepsimauhongJoker (BOI20_joker)C++20
100 / 100
334 ms162364 KiB
#include <bits/stdc++.h>

using namespace std;

//#define int long long

#define FOR(I, L, R) for(int I(L) ; I <= (int)R ; ++I)
#define FOD(I, R, L) for(int I(R) ; I >= (int)L ; --I)
#define FOA(I, A) for(auto &I : A)

#define print(A,L,R) FOR(OK, L, R){if(A[OK]<=-oo / 10||A[OK]>=oo / 10)cout<<"- ";else cout<<A[OK]<<' ';}cout<<'\n';
#define prints(A) FOA(OK, A){cout<<OK<<' ';}cout << '\n';
#define printz(A,L,R) FOR(OK, 1, L){FOR(KO, 1, R){if(A[OK][KO]>-oo / 10&&A[OK][KO]<oo)cout<<A[OK][KO]<<' ';else cout << "- ";} cout << '\n';}cout << '\n';

#define fs first
#define sd second
#define ii pair<int,int>
#define iii pair<int, ii>
#define all(A) A.begin(), A.end()
#define quickly ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FILE "PAIR"

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int oo = 1e9;

struct Modint{
        int x;

        Modint(){x = 0;}
        Modint(int _x){ x = (_x % mod + mod) % mod; }

        inline Modint operator + (const Modint &other) const{ return (x + other.x) % mod; }
        inline Modint operator - (const Modint &other) const{ return (x - other.x + mod) % mod; }
        inline Modint operator * (const Modint &other) const{ return (1LL * x * other.x) % mod; }

        inline void operator += (const Modint &other){ *this = *this + other; }
        inline void operator -= (const Modint &other){ *this = *this - other; }
        inline void operator *= (const Modint &other){ *this = *this * other; }

        friend ostream& operator << (ostream& os, const Modint &t){ return os << t.x; }
};

int n, m, q;
ii edge[N];
int far[N];
bool check[N];

struct per{
        int u, szu, hu, v, szv, hv;
};
vector<per> st[N];

struct DSU{
        int parent[N], sz[N];
        bool h[N];

        void build(){FOR(i, 1, n){parent[i] = i, sz[i] = 1;}}

        int found(int u){
                return (parent[u] == u ? u : found(parent[u]));
        }

        bool wei(int u){
                if(u == parent[u]){
                        return 0;
                }
                return (wei(parent[u]) ^ h[u]);
        }

        bool setting(int u, int v, int x){
                if(u == v) return 1;
                int U = found(u);
                int V = found(v);

                if(sz[U] < sz[V]) swap(U, V);

                st[x].push_back({U, sz[U], h[U], V, sz[V], h[V]});

                if(U != V){
                        if(wei(v) == wei(u)) h[V] ^= 1;
                        parent[V] = U;
                        sz[U] += sz[V];
                        return 1;
                }
                return wei(u) != wei(v);
        }

        void rollback(int x){
                while(!st[x].empty()){
                        int u = st[x].back().u;
                        int v = st[x].back().v;
                        int szu = st[x].back().szu;
                        int szv = st[x].back().szv;
                        int hu = st[x].back().hu;
                        int hv = st[x].back().hv;

                        parent[u] = u;
                        parent[v] = v;

                        sz[u] = szu;
                        sz[v] = szv;

                        h[u] = hu;
                        h[v] = hv;

                        st[x].pop_back();
                }
        }
} dsu;

void dnc(int l, int r, int optl, int optr){
        if(l > r) return;

        int mid = (l + r) >> 1;
        int opt = m + 1;

        FOR(i, l, mid){
                int u = edge[i].fs;
                int v = edge[i].sd;

                check[mid] &= dsu.setting(u, v, mid);
        }

        FOD(i, optr, optl){
                int u = edge[i].fs;
                int v = edge[i].sd;

                if(dsu.setting(u, v, mid)){
                        opt = i;
                }
                else break;
        }
        far[mid] = opt;

        dsu.rollback(mid);

        FOD(i, optr, opt){
                int u = edge[i].fs;
                int v = edge[i].sd;
                dsu.setting(u, v, mid);
        }
        dnc(l, mid - 1, optl, opt);
        dsu.rollback(mid);

        FOR(i, l, mid){
                int u = edge[i].fs;
                int v = edge[i].sd;
                dsu.setting(u, v, mid);
        }
        dnc(mid + 1, r, opt, optr);
        dsu.rollback(mid);
}

signed main(){ quickly
        if(fopen(FILE".inp", "r")){
                freopen(FILE".inp", "r", stdin);
                freopen(FILE".out", "w", stdout);
        }

        cin >> n >> m >> q;

        dsu.build();
        FOR(i, 1, m) check[i] = 1;

        FOR(i, 1, m){
                int u, v;
                cin >> u >> v;
                edge[i] = {u, v};
        }

        check[0] = 1;
        dnc(1, m, 1, m);

        FOR(i, 1, m){
                check[i] &= check[i - 1];
        }

        FOD(i, m, 1){
                int u = edge[i].fs;
                int v = edge[i].sd;
                if(dsu.setting(u, v, 0)){
                        far[0] = i;
                }
                else break;
        }

        while(q--){
                int l, r;
                cin >> l >> r;

                if(check[l - 1] == 0){
                        cout << "YES\n";
                }
                else if(far[l - 1] - r > 1){
                        cout << "YES\n";
                }
                else{
                        cout << "NO\n";
                }
        }
}

컴파일 시 표준 에러 (stderr) 메시지

Joker.cpp: In function 'int main()':
Joker.cpp:157:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |                 freopen(FILE".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:158:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |                 freopen(FILE".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...