oj.uz

Submission #878750

# Submission time Handle Problem Language Result Execution time Memory
878750 2023-11-25T07:20:08 Z kh0i Joker (BOI20_joker) C++17
25 / 100
 1947 ms 31816 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()]);
            add_time[m + 1] = ++timer;
            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){
                dsu.rollback(add_time[R[x] + 1]);

                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 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19032 KB Output is correct
5 Correct 4 ms 18876 KB Output is correct
6 Correct 4 ms 19088 KB Output is correct
7 Correct 4 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 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19032 KB Output is correct
5 Correct 4 ms 18876 KB Output is correct
6 Correct 4 ms 19088 KB Output is correct
7 Correct 4 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 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 681 ms 28720 KB Output is correct
4 Correct 665 ms 31816 KB Output is correct
5 Correct 1338 ms 31544 KB Output is correct
6 Correct 788 ms 30056 KB Output is correct
7 Correct 801 ms 30068 KB Output is correct
8 Correct 1316 ms 29120 KB Output is correct
9 Correct 1761 ms 30004 KB Output is correct
10 Correct 1873 ms 31644 KB Output is correct
11 Correct 1359 ms 29760 KB Output is correct
12 Correct 1531 ms 31144 KB Output is correct
13 Correct 657 ms 28388 KB Output is correct
14 Correct 1303 ms 28976 KB Output is correct
15 Correct 1947 ms 30436 KB Output is correct
16 Correct 1894 ms 31392 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19032 KB Output is correct
5 Correct 4 ms 18876 KB Output is correct
6 Correct 4 ms 19088 KB Output is correct
7 Correct 4 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 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19032 KB Output is correct
5 Correct 4 ms 18876 KB Output is correct
6 Correct 4 ms 19088 KB Output is correct
7 Correct 4 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 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19032 KB Output is correct
5 Correct 4 ms 18876 KB Output is correct
6 Correct 4 ms 19088 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Incorrect 4 ms 19036 KB Output isn't correct
9 Halted 0 ms 0 KB -