oj.uz

답안 #800238

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
800238 2023-08-01T12:36:28 Z TB_ Joker (BOI20_joker) C++17
25 / 100
 169 ms 62936 KB 
#include <bits/stdc++.h>
using namespace std;

// #undef _GLIBCXX_DEBUG                // disable run-time bound checking, etc
// #pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
// #pragma GCC optimize ("unroll-loops")

// #pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
// #pragma GCC target("movbe")                                      // byte swap
// #pragma GCC target("aes,pclmul,rdrnd")                           // encryption
// #pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") // SIMD

// #include <bits/extc++.h>
// using namespace __gnu_pbds;
// template<class T>using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
// template<class T>using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long
#define INF (ll)1e9+7
#define fo(i, n) for(int i=0;i<((ll)n);i++)
#define deb(x) cout << #x << " = " << x << endl;
#define deb2(x, y) cout << #x << " = " << x << ", " << #y << " = " << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define LSOne(S) ((S) & (-S))
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
inline int readint(){ int v = 0; char c; while((c = getchar()) != EOF && c != ' ' && c != '\n'){ v *= 10; v += c - '0'; } return v; }
inline int readintsigned() { int v = 0; int sign = 1; char c = getchar(); if (c == '-') { sign = -1; } else { v += c - '0'; } while ((c = getchar()) != EOF && c != ' ' && c != '\n') { v *= 10; v += c - '0'; } return v * sign; }
inline string readstring() { string s; char c; while ((c = getchar()) != EOF && c != '\n' && c != ' ') { s.push_back(c); } return s; }
template <class result_t=std::chrono::milliseconds,class clock_t=std::chrono::steady_clock,class duration_t = std::chrono::milliseconds>
auto since(std::chrono::time_point<clock_t, duration_t> const& start){return std::chrono::duration_cast<result_t>(clock_t::now() - start);}
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vpii> vvpii;
typedef vector<vpl> vvpl;



struct UnionFind{
    vl degree, height, p, siz, extraHeight;
    vector<vvpl> updates; // pUpdates, heightUpdate, sizUpdate
    vi possibleUpdate, extraHeightUpdate;
    int n;
    int possible = 0;
    UnionFind(int n) : n(n) {
        height.assign(n, 0);
        extraHeight.assign(n, 0);
        degree.assign(n, 0); 
        p.assign(n, 0); 
        siz.assign(n, 1); 
        fo(i, n) p[i] = i;
    }

    int find(int x){
        if(x == p[x]) return x;
        // updates[updates.size()-1][0].pb({x, p[x]});
        updates[updates.size()-1][1].pb({x, height[x]});
        int res = find(p[x]);
        height[x] = height[p[x]]+1+extraHeight[x];
        return res;
    }


    void addEdge(int a, int b){
        possibleUpdate.pb(possible);
        extraHeightUpdate.pb(-1);
        updates.pb({{}, {}, {}});
        int a2 = find(a);
        int b2 = find(b);
        if(a2==b2){
            if(height[a]%2 == height[b]%2) possible++;
        }else{
            if(siz[b2] > siz[a2]) {
                swap(a2, b2);
                swap(a, b);
            }
            updates[updates.size()-1][2].pb({a2, siz[a2]});
            updates[updates.size()-1][0].pb({b2, p[b2]});
            siz[a2] += siz[b2];
            p[b2] = a2;
            if((height[b2]%2 == height[b]%2)^(height[a2]%2 == height[a]%2)){
                extraHeight[b2]++;
                extraHeightUpdate[extraHeightUpdate.size()-1] = b2;
            }
        }
    }  


    void backtrack(){
        possible = possibleUpdate[possibleUpdate.size()-1];
        int heightupdate = extraHeightUpdate[extraHeightUpdate.size()-1];
        if(heightupdate != -1) extraHeight[heightupdate]--;
        for(auto up : updates[possibleUpdate.size()-1][0]) p[up.F] = up.S;
        for(auto up : updates[possibleUpdate.size()-1][1]) height[up.F] = up.S;
        for(auto up : updates[possibleUpdate.size()-1][2]) siz[up.F] = up.S;
        updates.pop_back();
        possibleUpdate.pop_back();
    }  
};


int main() {
    // cout << fixed << setprecision(20);
    // auto start = std::chrono::steady_clock::now(); // since(start).count()
    cin.tie(0)->sync_with_stdio(0);

    int n, m, q, from, to, que;
    vpl edges;
    cin >> n >> m >> q;
    fo(i, m){
        cin >> from >> to;
        edges.pb({from-1, to-1});
    }

    vector<vector<tuple<int, int, int>>> queries(1000);
    fo(x, q){
        cin >> from >> to;
        queries[from/((int)sqrt(n))].pb({to-1, from-1, x});
    }
    fo(i, 1000){
        sort(rall(queries[i]));
    }
    UnionFind uf(n);
    vi ans(q, 0);
    fo(section, 1000){
        int lo = 0, hi = m-1;
        for(auto query : queries[section]){
            tie(to, from, que) = query;
            fo(i, hi-to) uf.addEdge(edges[hi-i].F,edges[hi-i].S);
            hi=to;

            fo(i, from-lo) 
                uf.addEdge(edges[lo+i].F, edges[lo+i].S);
            if(uf.possible) ans[que] = 1;
            fo(i, from-((int)sqrt(n))*section)
                uf.backtrack();
            lo = ((int)sqrt(n))*section;
        }
        while(uf.possibleUpdate.size())
            uf.backtrack();
    }
    fo(i, q) cout << (ans[i]?"YES\n":"NO\n");


    return 0;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 131 ms 54248 KB Output is correct
4 Correct 154 ms 58456 KB Output is correct
5 Correct 160 ms 58340 KB Output is correct
6 Correct 147 ms 54764 KB Output is correct
7 Correct 150 ms 62936 KB Output is correct
8 Correct 146 ms 54384 KB Output is correct
9 Correct 150 ms 56316 KB Output is correct
10 Correct 169 ms 60044 KB Output is correct
11 Correct 146 ms 55472 KB Output is correct
12 Correct 152 ms 56624 KB Output is correct
13 Correct 142 ms 53000 KB Output is correct
14 Correct 146 ms 54940 KB Output is correct
15 Correct 158 ms 58668 KB Output is correct
16 Correct 164 ms 60368 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -