oj.uz

Submission #963722

# Submission time Handle Problem Language Result Execution time Memory
963722 2024-04-15T14:15:16 Z Pring Joker (BOI20_joker) C++17
0 / 100
 190 ms 15852 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

const int MXN = 200005;
int n, m, q, x, y;
int eu[MXN], ev[MXN];
int l[MXN], L;

struct DSU {
    int p[MXN * 2];
    vector<pii> st;
    vector<bool> isb;
    void init(int n) {
        fill(p + 1, p + n * 2 + 1, -1);
        st.clear();
        isb.clear();
        isb.push_back(0);
    }
    int find(int x) {
        return (p[x] < 0 ? x : find(p[x]));
    }
    bool onion(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            st.push_back(mp(0, 0));
            st.push_back(mp(0, 0));
            return false;
        }
        if (p[x] > p[y]) swap(x, y);
        st.push_back(mp(x, p[x]));
        st.push_back(mp(y, p[y]));
        p[x] += p[y];
        p[y] = x;
        return true;
    }
    void undo() {
        p[st.back().fs] = st.back().sc;
        st.pop_back();
        p[st.back().fs] = st.back().sc;
        st.pop_back();
    }
    bool ONION(int x, int y) {
        onion(x, y + n);
        onion(x + n, y);
        bool f = (isb.back() | (find(x) == find(y)));
        isb.push_back(f);
        return f;
    }
    void BACK() {
        undo();
        undo();
        isb.pop_back();
    }
} dsu;

bool ODD_CYCLE() {
    dsu.init(n);
    FOR(i, 0, m) if (dsu.ONION(eu[i], ev[i])) return false;
    return true;
}

void MOVE() {
    while (!dsu.isb.back()) {
        dsu.ONION(eu[L], ev[L]);
        L++;
    }
}

void MOVE(int x) {
    while (L < x) {
        dsu.ONION(eu[L], ev[L]);
        L++;
    }
    while (L > x) {
        dsu.BACK();
        L--;
    }
}

void calc(int sl, int sr) {
    debug(sl, sr);
    if (sl > sr) return;
    int pl = L;
    int mid = (sl + sr) >> 1;
    for (int i = sr; i > mid; i--) dsu.ONION(eu[i - 1], ev[i - 1]);
    MOVE();
    l[mid] = max(0, L - 1);
    debug(mid, l[mid]);
    MOVE(pl);
    calc(sl, mid - 1);
    for (int i = mid; i < sr; i++) dsu.BACK();
    MOVE(l[mid]);
    calc(mid + 1, sr);
    MOVE(pl);
}

void miku() {
    cin >> n >> m >> q;
    FOR(i, 0, m) cin >> eu[i] >> ev[i];
    if (ODD_CYCLE()) {
        while (q--) cout << "NO" << '\n';
        return;
    }
    dsu.init(n);
    calc(0, m);
    // FOR(i, 0, m + 1) cout << l[i] << '\n';
    FOR(i, 0, m + 1) debug(i, l[i]);
    while (q--) {
        cin >> x >> y;
        debug(y, l[y]);
        cout << (l[y] >= x - 1 ? "NO" : "YES") << '\n';
    }
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

Compilation message

Joker.cpp: In function 'void calc(int, int)':
Joker.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Joker.cpp:102:5: note: in expansion of macro 'debug'
  102 |     debug(sl, sr);
      |     ^~~~~
Joker.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Joker.cpp:109:5: note: in expansion of macro 'debug'
  109 |     debug(mid, l[mid]);
      |     ^~~~~
Joker.cpp: In function 'void miku()':
Joker.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Joker.cpp:128:22: note: in expansion of macro 'debug'
  128 |     FOR(i, 0, m + 1) debug(i, l[i]);
      |                      ^~~~~
Joker.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Joker.cpp:131:9: note: in expansion of macro 'debug'
  131 |         debug(y, l[y]);
      |         ^~~~~

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Incorrect 190 ms 15852 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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