oj.uz

Submission #878749

# Submission time Handle Problem Language Result Execution time Memory
878749 2023-11-25T07:19:29 Z kh0i Joker (BOI20_joker) C++17
25 / 100
 1918 ms 31724 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 19092 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 19036 KB Output is correct
6 Correct 4 ms 19032 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Incorrect 4 ms 19032 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 19092 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 19036 KB Output is correct
6 Correct 4 ms 19032 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Incorrect 4 ms 19032 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 19092 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 691 ms 28712 KB Output is correct
4 Correct 650 ms 31724 KB Output is correct
5 Correct 1396 ms 31360 KB Output is correct
6 Correct 808 ms 30084 KB Output is correct
7 Correct 787 ms 29868 KB Output is correct
8 Correct 1293 ms 29228 KB Output is correct
9 Correct 1737 ms 29880 KB Output is correct
10 Correct 1914 ms 31560 KB Output is correct
11 Correct 1342 ms 29724 KB Output is correct
12 Correct 1541 ms 31148 KB Output is correct
13 Correct 658 ms 28308 KB Output is correct
14 Correct 1283 ms 28968 KB Output is correct
15 Correct 1918 ms 30552 KB Output is correct
16 Correct 1853 ms 31304 KB Output is correct

Subtask #4
0 / 10.0

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