oj.uz

Submission #878746

# Submission time Handle Problem Language Result Execution time Memory
878746 2023-11-25T07:16:45 Z kh0i Joker (BOI20_joker) C++17
25 / 100
 1930 ms 31900 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

using ll = long long;
using pii = pair<int, int>;

#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    assert(l <= r);
    return uniform_int_distribution<ll> (l, r)(rng);
}

const int N = 2e5 + 3;

int n, m, q, L[N], R[N];
vector<pii> g[N];
pii e[N];

// contain no odd cycle -> bipartite graph

namespace Sub12{
    bool valid_input(){
        return n <= 2000 and m <= 2000 and q <= 2000;
    }

    int vis[N];

    bool dfs(int u, int l, int r, int col){
        bool ok = 1;
        vis[u] = col;
        for(auto [v, id] : g[u]){
            if(l <= id and id <= r)
                continue;
            if(vis[v])
                ok &= (vis[u] != vis[v]);
            else
                ok &= dfs(v, l, r, col ^ 3);
        }
        return ok;
    }

    void solve(){
        for(int i = 1; i <= q; ++i){
            bool bipartite = 1;
            for(int u = 1; u <= n; ++u)
                vis[u] = 0;
            for(int u = 1; u <= n; ++u){
                if(!vis[u])
                    bipartite &= dfs(u, L[i], R[i], 1);
            }
            cout << (bipartite ? "NO\n" : "YES\n");
        }
    }
}

struct DSU{
    bool bipartite = 1;
    vector<pii> p;
    int n;

    void init(int _n){
        n = _n;
        p.resize(n + 2);
        for(int i = 1; i <= n; ++i)
            p[i] = {i, 0};
    }

    pii find_set(int u){
        if(u != p[u].F){
            int parity = p[u].S;
            p[u] = find_set(p[u].F);
            p[u].S ^= parity;
        }
        return p[u];
    }

    void add_edge(int u, int v){
        pii pu = find_set(u);
        u = pu.F;
        pii pv = find_set(v);
        v = pv.F;
        int x = pu.S, y = pv.S;
        if(u == v){
            bipartite &= (x != y);
            return;
        }
        p[v] = {u, x ^ y ^ 1};
    }
};

namespace Sub34{
    bool valid_input(){
        bool ok = 1;
        for(int i = 1; i <= q; ++i)
            ok &= (L[i] <= 200);
        return ok;
    }

    int ans[N];
    vector<pii> d[N];

    void solve(){
        for(int i = 1; i <= q; ++i){
            d[L[i]].push_back({R[i], i});
        }
        for(int i = 1; i <= min(200, m); ++i){
            DSU dsu;
            dsu.init(n);
            for(int j = 1; j < i; ++j){
                dsu.add_edge(e[j].F, e[j].S);
            }
            sort(all(d[i]), [](pii &x, pii &y) -> bool{
                 return x.F < y.F;
            });

            for(int j = m; j >= i; --j){
                while(!d[i].empty() and d[i].back().F == j){
                    ans[d[i].back().S] = dsu.bipartite;
                    d[i].pop_back();
                }
                dsu.add_edge(e[j].F, e[j].S);
            }
        }
        for(int i = 1; i <= q; ++i)
            cout << (ans[i] ? "NO\n" : "YES\n");
    }
}

struct DSU_Rollback{
    struct Data{
        int u, parity_u, sz_u, v, parity_v, sz_v;
        bool bipartite;
        int t;
    };

    bool bipartite;
    vector<pii> p;
    vector<int> sz;
    vector<Data> op;

    void init(int _n){
        bipartite = 1;
        p.resize(n + 2);
        sz.resize(n + 2, 1);
        for(int i = 1; i <= n; ++i)
            p[i] = {i, 0};
    }

    pii find_set(int u){
        if(u == p[u].F)
            return p[u];
        int parity = p[u].S;
        pii x = find_set(p[u].F);
        x.S ^= parity;
        return x;
    }

    void join_sets(int u, int v, int t){
        pii pu = find_set(u), pv = find_set(v);
        u = pu.F, v = pv.F;
        int x = pu.S, y = pv.S;

        if(u == v){
            if(x == y and bipartite){
                op.push_back({u, x, sz[u], v, y, sz[v], bipartite, t});
                bipartite = 0;
            }
            return;
        }
        if(sz[u] < sz[v])
            swap(u, v);
        op.push_back({u, x, sz[u], v, y, sz[v], bipartite, t});
        p[v] = {u, x ^ y ^ 1};
        sz[u] += sz[v];
    }

    void rollback(int t){
        while(!op.empty() and op.back().t >= t){
            Data &x = op.back();
            op.pop_back();
            p[x.u] = {x.u, x.parity_u};
            sz[x.u]= x.sz_u;
            p[x.v] = {x.v, x.parity_v};
            sz[x.v] = x.sz_v;
            bipartite = x.bipartite;
        }
    }
};

namespace Sub5{
    bool valid_input(){
        return q <= 2000;
    }

    int B, add_time[N];
    vector<int> blk[N];
    int ans[N];

    void solve(){
        B = m / sqrt(q);
        debug(B);
        for(int i = 1; i <= q; ++i)
            blk[(L[i] + B - 1) / B].push_back(i);

        for(int bl = 1; bl < N; ++bl){
            if(blk[bl].empty())
                continue;
            vector<int> &d = blk[bl];
            debug(d);
            sort(all(d), [](int &x, int &y) -> bool {
                 return R[x] < R[y];
            });
            DSU_Rollback dsu;
            dsu.init(n);

            int timer = 0;
            int U = (bl - 1) * B + 1;

            debug(U);

            for(int i = 1; i < U; ++i){
                dsu.join_sets(e[i].F, e[i].S, ++timer);
                add_time[i] = timer;
                debug(e[i], timer);
            }
            debug(R[d.front()]);
            for(int i = m; i >= R[d.front()]; --i){
                dsu.join_sets(e[i].F, e[i].S, ++timer);
                add_time[i] = timer;
                debug(e[i], timer);
            }

            for(int x : d){
                debug(L[x], R[x], add_time[R[x]]);
                dsu.rollback(add_time[R[x]]);

                int last = timer;
                debug(last);

                for(int i = U + 1; i <= L[x]; ++i){
                    dsu.join_sets(e[i].F, e[i].S, ++timer);
                    debug(e[i], timer);
                }

                debug(dsu.bipartite);

                ans[x] = dsu.bipartite;

                dsu.rollback(last);
                timer = last;
            }
        }
        for(int i = 1; i <= q; ++i)
            cout << (ans[i] ? "NO\n" : "YES\n");
    }
};

void solve(){
    cin >> n >> m >> q;
    for(int i = 1; i <= m; ++i){
        int u, v;
        cin >> u >> v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
        e[i] = {u, v};
    }
    for(int i = 1; i <= q; ++i)
        cin >> L[i] >> R[i];
    if(Sub5::valid_input())
        Sub5::solve();
    else if(Sub12::valid_input())
        Sub12::solve();
    else if(Sub34::valid_input())
        Sub34::solve();

}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    #define task "nohome"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int test = 1;
//    cin >> test;
    for(int i = 1; i <= test; ++i){
//        cout << "Case #" << i << ": ";
        solve();
    }
    #ifdef LOCAL
        cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    #endif
    return 0;
}

Compilation message

Joker.cpp: In function 'int32_t main()':
Joker.cpp:293:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  293 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:294:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  294 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 5 ms 19036 KB Output is correct
8 Incorrect 4 ms 19036 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 5 ms 19036 KB Output is correct
8 Incorrect 4 ms 19036 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 663 ms 28876 KB Output is correct
4 Correct 625 ms 31900 KB Output is correct
5 Correct 1333 ms 31364 KB Output is correct
6 Correct 800 ms 30060 KB Output is correct
7 Correct 759 ms 29872 KB Output is correct
8 Correct 1371 ms 29228 KB Output is correct
9 Correct 1688 ms 29888 KB Output is correct
10 Correct 1829 ms 31388 KB Output is correct
11 Correct 1321 ms 29724 KB Output is correct
12 Correct 1521 ms 31148 KB Output is correct
13 Correct 641 ms 28316 KB Output is correct
14 Correct 1316 ms 28972 KB Output is correct
15 Correct 1930 ms 30568 KB Output is correct
16 Correct 1922 ms 31304 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 5 ms 19036 KB Output is correct
8 Incorrect 4 ms 19036 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 5 ms 19036 KB Output is correct
8 Incorrect 4 ms 19036 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 5 ms 19036 KB Output is correct
8 Incorrect 4 ms 19036 KB Output isn't correct
9 Halted 0 ms 0 KB -