oj.uz

Submission #878042

# Submission time Handle Problem Language Result Execution time Memory
878042 2023-11-24T03:26:28 Z kh0i Joker (BOI20_joker) C++17
49 / 100
 1910 ms 30500 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");
    }
}

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(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:161:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:162:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12888 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 4 ms 12892 KB Output is correct
9 Correct 5 ms 13404 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 4 ms 12892 KB Output is correct
14 Correct 3 ms 12888 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 3 ms 12892 KB Output is correct
17 Correct 3 ms 12892 KB Output is correct
18 Correct 3 ms 12892 KB Output is correct
19 Correct 3 ms 13004 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct
21 Correct 3 ms 12892 KB Output is correct
22 Correct 3 ms 12892 KB Output is correct
23 Correct 3 ms 12888 KB Output is correct
24 Correct 3 ms 12892 KB Output is correct
25 Correct 3 ms 12888 KB Output is correct
26 Correct 3 ms 12892 KB Output is correct
27 Correct 3 ms 12996 KB Output is correct
28 Correct 3 ms 12892 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12888 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 4 ms 12892 KB Output is correct
9 Correct 5 ms 13404 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 4 ms 12892 KB Output is correct
14 Correct 3 ms 12888 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 3 ms 12892 KB Output is correct
17 Correct 3 ms 12892 KB Output is correct
18 Correct 3 ms 12892 KB Output is correct
19 Correct 3 ms 13004 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct
21 Correct 3 ms 12892 KB Output is correct
22 Correct 3 ms 12892 KB Output is correct
23 Correct 3 ms 12888 KB Output is correct
24 Correct 3 ms 12892 KB Output is correct
25 Correct 3 ms 12888 KB Output is correct
26 Correct 3 ms 12892 KB Output is correct
27 Correct 3 ms 12996 KB Output is correct
28 Correct 3 ms 12892 KB Output is correct
29 Correct 55 ms 12892 KB Output is correct
30 Correct 91 ms 13124 KB Output is correct
31 Correct 85 ms 13148 KB Output is correct
32 Correct 65 ms 13168 KB Output is correct
33 Correct 47 ms 13148 KB Output is correct
34 Correct 92 ms 13148 KB Output is correct
35 Correct 96 ms 13160 KB Output is correct
36 Correct 25 ms 13148 KB Output is correct
37 Correct 57 ms 13148 KB Output is correct
38 Correct 56 ms 13376 KB Output is correct
39 Correct 64 ms 13144 KB Output is correct
40 Correct 55 ms 13156 KB Output is correct
41 Correct 57 ms 13148 KB Output is correct
42 Correct 57 ms 13148 KB Output is correct
43 Correct 47 ms 13144 KB Output is correct
44 Correct 67 ms 13148 KB Output is correct
45 Correct 85 ms 13160 KB Output is correct
46 Correct 94 ms 13148 KB Output is correct
47 Correct 52 ms 13148 KB Output is correct
48 Correct 61 ms 13144 KB Output is correct
49 Correct 74 ms 13148 KB Output is correct
50 Correct 88 ms 12892 KB Output is correct
51 Correct 52 ms 13132 KB Output is correct
52 Correct 65 ms 13148 KB Output is correct
53 Correct 78 ms 13144 KB Output is correct
54 Correct 95 ms 13148 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 680 ms 26652 KB Output is correct
4 Correct 634 ms 29192 KB Output is correct
5 Correct 1334 ms 29488 KB Output is correct
6 Correct 766 ms 28104 KB Output is correct
7 Correct 759 ms 27788 KB Output is correct
8 Correct 1300 ms 26572 KB Output is correct
9 Correct 1730 ms 27256 KB Output is correct
10 Correct 1863 ms 29024 KB Output is correct
11 Correct 1330 ms 27556 KB Output is correct
12 Correct 1484 ms 29160 KB Output is correct
13 Correct 649 ms 26068 KB Output is correct
14 Correct 1304 ms 26872 KB Output is correct
15 Correct 1910 ms 28832 KB Output is correct
16 Correct 1902 ms 29316 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12888 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 4 ms 12892 KB Output is correct
9 Correct 5 ms 13404 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 4 ms 12892 KB Output is correct
14 Correct 3 ms 12888 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 3 ms 12892 KB Output is correct
17 Correct 3 ms 12892 KB Output is correct
18 Correct 3 ms 12892 KB Output is correct
19 Correct 3 ms 13004 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct
21 Correct 3 ms 12892 KB Output is correct
22 Correct 3 ms 12892 KB Output is correct
23 Correct 3 ms 12888 KB Output is correct
24 Correct 3 ms 12892 KB Output is correct
25 Correct 3 ms 12888 KB Output is correct
26 Correct 3 ms 12892 KB Output is correct
27 Correct 3 ms 12996 KB Output is correct
28 Correct 3 ms 12892 KB Output is correct
29 Correct 680 ms 26652 KB Output is correct
30 Correct 634 ms 29192 KB Output is correct
31 Correct 1334 ms 29488 KB Output is correct
32 Correct 766 ms 28104 KB Output is correct
33 Correct 759 ms 27788 KB Output is correct
34 Correct 1300 ms 26572 KB Output is correct
35 Correct 1730 ms 27256 KB Output is correct
36 Correct 1863 ms 29024 KB Output is correct
37 Correct 1330 ms 27556 KB Output is correct
38 Correct 1484 ms 29160 KB Output is correct
39 Correct 649 ms 26068 KB Output is correct
40 Correct 1304 ms 26872 KB Output is correct
41 Correct 1910 ms 28832 KB Output is correct
42 Correct 1902 ms 29316 KB Output is correct
43 Correct 675 ms 27700 KB Output is correct
44 Correct 662 ms 30500 KB Output is correct
45 Correct 615 ms 30376 KB Output is correct
46 Correct 817 ms 28980 KB Output is correct
47 Correct 782 ms 28992 KB Output is correct
48 Correct 1647 ms 28468 KB Output is correct
49 Correct 1833 ms 30120 KB Output is correct
50 Correct 1197 ms 28196 KB Output is correct
51 Correct 1403 ms 29620 KB Output is correct
52 Correct 1423 ms 30376 KB Output is correct
53 Correct 665 ms 27048 KB Output is correct
54 Correct 1547 ms 28268 KB Output is correct
55 Correct 1830 ms 29700 KB Output is correct
56 Correct 1818 ms 30224 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12888 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 4 ms 12892 KB Output is correct
9 Correct 5 ms 13404 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 4 ms 12892 KB Output is correct
14 Correct 3 ms 12888 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 3 ms 12892 KB Output is correct
17 Correct 3 ms 12892 KB Output is correct
18 Correct 3 ms 12892 KB Output is correct
19 Correct 3 ms 13004 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct
21 Correct 3 ms 12892 KB Output is correct
22 Correct 3 ms 12892 KB Output is correct
23 Correct 3 ms 12888 KB Output is correct
24 Correct 3 ms 12892 KB Output is correct
25 Correct 3 ms 12888 KB Output is correct
26 Correct 3 ms 12892 KB Output is correct
27 Correct 3 ms 12996 KB Output is correct
28 Correct 3 ms 12892 KB Output is correct
29 Correct 55 ms 12892 KB Output is correct
30 Correct 91 ms 13124 KB Output is correct
31 Correct 85 ms 13148 KB Output is correct
32 Correct 65 ms 13168 KB Output is correct
33 Correct 47 ms 13148 KB Output is correct
34 Correct 92 ms 13148 KB Output is correct
35 Correct 96 ms 13160 KB Output is correct
36 Correct 25 ms 13148 KB Output is correct
37 Correct 57 ms 13148 KB Output is correct
38 Correct 56 ms 13376 KB Output is correct
39 Correct 64 ms 13144 KB Output is correct
40 Correct 55 ms 13156 KB Output is correct
41 Correct 57 ms 13148 KB Output is correct
42 Correct 57 ms 13148 KB Output is correct
43 Correct 47 ms 13144 KB Output is correct
44 Correct 67 ms 13148 KB Output is correct
45 Correct 85 ms 13160 KB Output is correct
46 Correct 94 ms 13148 KB Output is correct
47 Correct 52 ms 13148 KB Output is correct
48 Correct 61 ms 13144 KB Output is correct
49 Correct 74 ms 13148 KB Output is correct
50 Correct 88 ms 12892 KB Output is correct
51 Correct 52 ms 13132 KB Output is correct
52 Correct 65 ms 13148 KB Output is correct
53 Correct 78 ms 13144 KB Output is correct
54 Correct 95 ms 13148 KB Output is correct
55 Incorrect 43 ms 19792 KB Output isn't correct
56 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12888 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 4 ms 12892 KB Output is correct
9 Correct 5 ms 13404 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 4 ms 12892 KB Output is correct
14 Correct 3 ms 12888 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 3 ms 12892 KB Output is correct
17 Correct 3 ms 12892 KB Output is correct
18 Correct 3 ms 12892 KB Output is correct
19 Correct 3 ms 13004 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct
21 Correct 3 ms 12892 KB Output is correct
22 Correct 3 ms 12892 KB Output is correct
23 Correct 3 ms 12888 KB Output is correct
24 Correct 3 ms 12892 KB Output is correct
25 Correct 3 ms 12888 KB Output is correct
26 Correct 3 ms 12892 KB Output is correct
27 Correct 3 ms 12996 KB Output is correct
28 Correct 3 ms 12892 KB Output is correct
29 Correct 55 ms 12892 KB Output is correct
30 Correct 91 ms 13124 KB Output is correct
31 Correct 85 ms 13148 KB Output is correct
32 Correct 65 ms 13168 KB Output is correct
33 Correct 47 ms 13148 KB Output is correct
34 Correct 92 ms 13148 KB Output is correct
35 Correct 96 ms 13160 KB Output is correct
36 Correct 25 ms 13148 KB Output is correct
37 Correct 57 ms 13148 KB Output is correct
38 Correct 56 ms 13376 KB Output is correct
39 Correct 64 ms 13144 KB Output is correct
40 Correct 55 ms 13156 KB Output is correct
41 Correct 57 ms 13148 KB Output is correct
42 Correct 57 ms 13148 KB Output is correct
43 Correct 47 ms 13144 KB Output is correct
44 Correct 67 ms 13148 KB Output is correct
45 Correct 85 ms 13160 KB Output is correct
46 Correct 94 ms 13148 KB Output is correct
47 Correct 52 ms 13148 KB Output is correct
48 Correct 61 ms 13144 KB Output is correct
49 Correct 74 ms 13148 KB Output is correct
50 Correct 88 ms 12892 KB Output is correct
51 Correct 52 ms 13132 KB Output is correct
52 Correct 65 ms 13148 KB Output is correct
53 Correct 78 ms 13144 KB Output is correct
54 Correct 95 ms 13148 KB Output is correct
55 Correct 680 ms 26652 KB Output is correct
56 Correct 634 ms 29192 KB Output is correct
57 Correct 1334 ms 29488 KB Output is correct
58 Correct 766 ms 28104 KB Output is correct
59 Correct 759 ms 27788 KB Output is correct
60 Correct 1300 ms 26572 KB Output is correct
61 Correct 1730 ms 27256 KB Output is correct
62 Correct 1863 ms 29024 KB Output is correct
63 Correct 1330 ms 27556 KB Output is correct
64 Correct 1484 ms 29160 KB Output is correct
65 Correct 649 ms 26068 KB Output is correct
66 Correct 1304 ms 26872 KB Output is correct
67 Correct 1910 ms 28832 KB Output is correct
68 Correct 1902 ms 29316 KB Output is correct
69 Correct 675 ms 27700 KB Output is correct
70 Correct 662 ms 30500 KB Output is correct
71 Correct 615 ms 30376 KB Output is correct
72 Correct 817 ms 28980 KB Output is correct
73 Correct 782 ms 28992 KB Output is correct
74 Correct 1647 ms 28468 KB Output is correct
75 Correct 1833 ms 30120 KB Output is correct
76 Correct 1197 ms 28196 KB Output is correct
77 Correct 1403 ms 29620 KB Output is correct
78 Correct 1423 ms 30376 KB Output is correct
79 Correct 665 ms 27048 KB Output is correct
80 Correct 1547 ms 28268 KB Output is correct
81 Correct 1830 ms 29700 KB Output is correct
82 Correct 1818 ms 30224 KB Output is correct
83 Incorrect 43 ms 19792 KB Output isn't correct
84 Halted 0 ms 0 KB -