oj.uz

Submission #973179

# Submission time Handle Problem Language Result Execution time Memory
973179 2024-05-01T15:26:54 Z vladilius Joker (BOI20_joker) C++17
0 / 100
 118 ms 46392 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

struct dsu{
    vector<pair<int&, int>> hist;
    vector<int> sz, p;
    int n, S;
    dsu(int ns){
        n = ns;
        p.resize(2 * n + 1);
        sz.resize(2 * n + 1);
        for (int i = 1; i <= 2 * n; i++){
            p[i] = i;
            sz[i] = 1;
        }
    }
    void save(){
        S = (int) hist.size();
    }
    int get(int v){
        if (p[v] != v){
            return get(p[v]);
        }
        return v;
    }
    int op(int v){
        return v + n;
    }
    void roll_back(){
        while (hist.size() != S){
            hist.back().ff = hist.back().ss;
            hist.pop_back();
        }
    }
    void unite(int x, int y){
        x = get(x); y = get(y);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x, y);
        hist.pb({p[x], p[x]});
        hist.pb({sz[y], sz[y]});
        p[x] = y;
        sz[y] += sz[x];
    }
    bool add(int x, int y){
        if (!x) return 0;
        unite(x, op(y));
        unite(y, op(x));
        return (get(x) == get(y));
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, M, q; cin>>n>>M>>q;
    vector<pii> ed = {{0, 0}};
    for (int i = 1; i <= M; i++){
        int u, v; cin>>u>>v;
        ed.pb({u, v});
    }
    ed.pb({0, 0});
    
    vector<int> last(M + 1);
    dsu T(n);
    function<void(int, int, pii)> solve = [&](int l, int r, pii R){
        if (l > r) return;
        assert(r <= R.ss);
        // [1, l - 1] U [R.ss + 1, M]
        int m = (l + r) / 2;
        
        T.save();
        for (int i = l; i < m; i++){
            T.add(ed[i].ff, ed[i].ss);
        }
        int j = 1;
        for (int i = R.ss; i >= m; i--){
            if (T.add(ed[i].ff, ed[i].ss)){
                j = i;
                break;
            }
        }
        last[m] = j - 1;
        T.roll_back();

        if (R.ff <= last[m]){
            T.save();
            for (int i = last[m] + 1; i <= R.ss; i++){
                T.add(ed[i].ff, ed[i].ss);
            }
            // [1, l - 1] U [last[m] + 1, M]
            solve(l, m - 1, {R.ff, last[m]});
            T.roll_back();
        }
        else {
            for (int i = l; i <= m; i++){
                last[i] = 0;
            }
        }
        
        T.save();
        for (int i = l; i <= m; i++){
            T.add(ed[i].ff, ed[i].ss);
        }
        // [1, m] U [R.ss + 1, M]
        solve(m + 1, r, {max(last[m], m + 1), R.ss});
        T.roll_back();
    };

    vector<int> all;
    for (int i = 1; i <= M; i++) all.pb(i);
    solve(1, M, {0, M + 1});
    
    while (q--){
        int l, r; cin>>l>>r;
        cout<<((r <= last[l]) ? "YES" : "NO")<<"\n";
    }
}

Compilation message

Joker.cpp: In member function 'void dsu::roll_back()':
Joker.cpp:35:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int&, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |         while (hist.size() != S){
      |                ~~~~~~~~~~~~^~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 0 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 0 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 118 ms 17828 KB Output is correct
4 Runtime error 77 ms 46392 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 0 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 0 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 0 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -