Submission #973351

#	Time	Username	Problem	Language	Result	Execution time	Memory
973351		vladilius	Joker (BOI20_joker)	C++17	14 / 100	2063 ms	26144 KiB

Joker

#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;
    vector<bool> f;
    int n;
    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;
        }
    }
    int get(int v){
        if (p[v] != v){
            return get(p[v]);
        }
        return v;
    }
    int op(int v){
        return v + n;
    }
    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(pii P){
        auto [x, y] = P;
        if (!x) return 0;
        unite(x, op(y));
        unite(y, op(x));
        bool k = ((!f.empty() && f.back()) | (get(x) == get(y)));
        f.pb(k);
        return k;
    }
    void clear(){
        while (!hist.empty()){
            hist.back().ff = hist.back().ss;
            hist.pop_back();
        }
        f.clear();
    }
};

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});
    }
    dsu T(n);
    for (int i = 1; i <= M; i++){
        T.add(ed[i]);
    }
    if (!T.f.back()){
        for (int i = 1; i <= q; i++){
            cout<<"NO"<<"\n";
        }
        return 0;
    }
    T.clear();
    
    vector<int> last(M + 1);
    function<void(int, int, pii)> solve = [&](int l, int r, pii R){
        if (l > r) return;

        vector<int> x1(2 * n + 1);
        for (int i = 1; i <= 2 * n; i++){
            x1[i] = T.get(i);
        }

        int m = (l + r) / 2;
        int S = (int) T.hist.size(), Sf = (int) T.f.size();
        for (int i = l; i < m; i++){
            T.add(ed[i]);
        }
        
        int i = R.ss;
        while (T.f.empty() || !T.f.back()){
            T.add(ed[i--]);
        }
        last[m] = i;
        while (T.hist.size() != S){
            T.hist.back().ff = T.hist.back().ss;
            T.hist.pop_back();
        }
        while (T.f.size() != Sf){
            T.f.pop_back();
        }
        
        S = (int) T.hist.size(); Sf = (int) T.f.size();
        for (int i = last[m] + 1; i <= R.ss; i++){
            T.add(ed[i]);
        }
        solve(l, m - 1, {R.ff, last[m]});
        while (T.hist.size() != S){
            T.hist.back().ff = T.hist.back().ss;
            T.hist.pop_back();
        }
        while (T.f.size() != Sf){
            T.f.pop_back();
        }
        
        S = (int) T.hist.size(); Sf = (int) T.f.size();
        for (int i = l; i <= m; i++){
            T.add(ed[i]);
        }
        solve(m + 1, r, {last[m], R.ss});
        while (T.hist.size() != S){
            T.hist.back().ff = T.hist.back().ss;
            T.hist.pop_back();
        }
        while (T.f.size() != Sf){
            T.f.pop_back();
        }
    };
    
    solve(1, M, {0, M});

    while (q--){
        int l, r; cin>>l>>r;
        cout<<((r <= last[l]) ? "YES" : "NO")<<"\n";
    }
}

Compilation message (stderr)

Joker.cpp: In lambda function:
Joker.cpp:102:30: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int&, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  102 |         while (T.hist.size() != S){
      |                ~~~~~~~~~~~~~~^~~~
Joker.cpp:106:27: warning: comparison of integer expressions of different signedness: 'std::vector<bool>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |         while (T.f.size() != Sf){
      |                ~~~~~~~~~~~^~~~~
Joker.cpp:115:30: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int&, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  115 |         while (T.hist.size() != S){
      |                ~~~~~~~~~~~~~~^~~~
Joker.cpp:119:27: warning: comparison of integer expressions of different signedness: 'std::vector<bool>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  119 |         while (T.f.size() != Sf){
      |                ~~~~~~~~~~~^~~~~
Joker.cpp:128:30: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int&, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  128 |         while (T.hist.size() != S){
      |                ~~~~~~~~~~~~~~^~~~
Joker.cpp:132:27: warning: comparison of integer expressions of different signedness: 'std::vector<bool>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  132 |         while (T.f.size() != Sf){
      |                ~~~~~~~~~~~^~~~~

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