oj.uz

Submission #648634

# Submission time Handle Problem Language Result Execution time Memory
648634 2022-10-07T08:41:32 Z mychecksedad Joker (BOI20_joker) C++17
25 / 100
 198 ms 39140 KB 
/* Author : Mychecksdead */
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define oset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 2e5+10, F = 2147483646, K = 20;

struct Dsu {
    vector<int> s;
    vector<pair<int, int>> p;
    vector<bool> bp;
    Dsu(int n){
        s.resize(n+1, 1);
        p.resize(n+1);
        bp.resize(n+1);
        for(int i = 0; i <= n; ++i) p[i] = {i, 0}, bp[i] = 1;
    }
    pair<int, int> find_set(int v) {
        if (v != p[v].first) {
            int parity = p[v].second;
            p[v] = find_set(p[v].first);
            p[v].second ^= parity;
        }
        return p[v];
    }
    void merge(int a, int b){
        pair<int, int> pa = find_set(a);
        a = pa.first;
        int x = pa.second;

        pair<int, int> pb = find_set(b);
        b = pb.first;
        int y = pb.second;

        if (a == b) {
            if (x == y)
                bp[a] = 0;
        } else {
            if (s[a] < s[b])
                swap (a, b);
            p[b] = make_pair(a, x^y^1);
            bp[a] = bp[b] & bp[a];
            s[a] += s[b];
        }
    }
};


int n, m, q, l, r;
bool ok;
vector<pair<int, int>> g[N], edges;
bitset<M> vis, pos;
void dfs(int v, int p, bool c){
    vis[v] = 1;
    pos[v] = c;
    for(auto k: g[v]){
        int u = k.first;
        if(l <= k.second && k.second <= r) continue;
        if(u != p){
            if(vis[u])
                ok |= pos[v] == pos[u];
            else
                dfs(u, v, !c);
        }
    }
}
void solve(){
    cin >> n >> m >> q;
    for(int i = 0; i < m; ++i){
        int u, v; cin >> u >> v;
        g[u].pb({v, i + 1});
        g[v].pb({u, i + 1});
        edges.pb({u, v});
    }
    // if(n <= 2000){
    //     for(int i = 0; i < q; ++i){
    //         cin >> l >> r;
    //         vis = 0;
    //         ok = 0;
    //         for(int v = 1; v <= n; ++v) if(!ok && !vis[v]) dfs(v, v, 0);
    //         if(ok) cout << "YES\n";
    //         else cout << "NO\n";
    //     }
    // }
    // else{
        vector<pair<int, int>> queries[205];
        vector<int> qq(q + 1);
        for(int i = 1; i <= q; ++i){
            cin >> l >> r;
            queries[l].pb({r, i});
        }
        for(int i = 1; i <= 200; ++i){
            if(queries[i].empty()) continue;
            Dsu d(n);
            ok = 0;
            for(int j = 1; j < i; ++j){
                d.merge(edges[j - 1].first, edges[j - 1].second);
                ok |= !d.bp[edges[j - 1].first] | !d.bp[edges[j - 1].second];
            }
            sort(all(queries[i]), [&](const pair<int, int> &a, const pair<int, int> &b){
                return a.first > b.first;
            });
            int cur = m;
            for(auto k: queries[i]){
                while(cur > k.first){
                    d.merge(edges[cur - 1].first, edges[cur - 1].second);
                    ok |= !d.bp[d.find_set(edges[cur - 1].first).first] | !d.bp[d.find_set(edges[cur - 1].second).first];
                    cur--;
                }
                qq[k.second] = ok;
            }
        }
        for(int i = 1; i <= q; ++i) cout << (qq[i] ? "YES\n" : "NO\n");
    // }
}



int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        cout << '\n';
    }
    return 0;
 
}

Compilation message

Joker.cpp: In function 'int main()':
Joker.cpp:131:16: warning: unused variable 'aa' [-Wunused-variable]
  131 |     int T = 1, aa;
      |                ^~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23724 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Incorrect 12 ms 23764 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23724 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Incorrect 12 ms 23764 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23724 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 116 ms 34192 KB Output is correct
4 Correct 143 ms 37168 KB Output is correct
5 Correct 186 ms 36976 KB Output is correct
6 Correct 160 ms 37944 KB Output is correct
7 Correct 148 ms 37880 KB Output is correct
8 Correct 162 ms 37048 KB Output is correct
9 Correct 144 ms 37876 KB Output is correct
10 Correct 198 ms 39140 KB Output is correct
11 Correct 142 ms 37580 KB Output is correct
12 Correct 147 ms 38588 KB Output is correct
13 Correct 119 ms 36284 KB Output is correct
14 Correct 166 ms 36900 KB Output is correct
15 Correct 196 ms 38056 KB Output is correct
16 Correct 180 ms 39056 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23724 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Incorrect 12 ms 23764 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23724 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Incorrect 12 ms 23764 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23724 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Incorrect 12 ms 23764 KB Output isn't correct
5 Halted 0 ms 0 KB -