oj.uz

Submission #1049276

# Submission time Handle Problem Language Result Execution time Memory
1049276 2024-08-08T15:52:50 Z windowwife Joker (BOI20_joker) C++17
25 / 100
 130 ms 14288 KB 
#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 4e5 + 2;
int n, m, q, max_r[maxn], u[maxn], v[maxn], l, r, par[maxn];
vector<pair<int, int>> rb;
int find_set (int u)
{
    if (par[u] < 0) return u;
    return find_set(par[u]);
}
void union_set (int u, int v)
{
    int pu = find_set(u), pv = find_set(v);
    if (pu == pv) return;
    if (par[pu] > par[pv]) swap(pu, pv);
    rb.push_back({pu, par[pu]});
    rb.push_back({pv, par[pv]});
    par[pu] += par[pv];
    par[pv] = pu;
}
void rollback ()
{
    if (rb.empty()) return;
    par[rb.back().first] = rb.back().second;
    rb.pop_back();
}
void pbs (int low, int high, int r)
{
    if (low > high) return;
    //cout << low << " " << high << " " << r << endl;
    int mid = (low + high)/2, tmp = rb.size();
    for (int i = low; i <= mid; i++)
    {
        //cout << i << endl;
        union_set(u[i], v[i] + n);
        union_set(u[i] + n, v[i]);
        if (find_set(u[i]) == find_set(u[i] + n))
        {
            for (int j = mid; j <= high; j++) max_r[j] = r;
            while ((int)rb.size() > tmp) rollback();
            pbs(low, mid - 1, r);
            return;
        }
    }
    int tmp2 = rb.size();
    for (int i = r - 1; i > low; i--)
    {
        union_set(u[i], v[i] + n);
        union_set(u[i] + n, v[i]);
        if (find_set(u[i]) == find_set(u[i] + n))
        {
            max_r[mid] = i;
            break;
        }
    }
    while ((int)rb.size() > tmp2) rollback();
    pbs(mid + 1, high, r);
    while ((int)rb.size() > tmp) rollback();
    for (int i = r - 1; i >= max(max_r[mid], low + 1); i--)
    {
        union_set(u[i], v[i] + n);
        union_set(u[i] + n, v[i]);
        if (find_set(u[i]) == find_set(u[i] + n))
        {
            for (int j = low; j <= mid; j++) max_r[j] = max_r[mid];
            return;
        }
    }
    pbs(low, mid - 1, max_r[mid]);
}
int main ()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i <= 2*n; i++) par[i] = -1;
    for (int i = 1; i <= m; i++) cin >> u[i] >> v[i];
    pbs(1, m, m + 1);
    while (q--)
    {
        cin >> l >> r;
        cout << (r < max_r[l] ? "YES" : "NO") << '\n';
    }
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 130 ms 9732 KB Output is correct
4 Correct 93 ms 13820 KB Output is correct
5 Correct 62 ms 14288 KB Output is correct
6 Correct 67 ms 10488 KB Output is correct
7 Correct 59 ms 9992 KB Output is correct
8 Correct 85 ms 8200 KB Output is correct
9 Correct 82 ms 9216 KB Output is correct
10 Correct 113 ms 9408 KB Output is correct
11 Correct 91 ms 10192 KB Output is correct
12 Correct 101 ms 9488 KB Output is correct
13 Correct 82 ms 6864 KB Output is correct
14 Correct 81 ms 7880 KB Output is correct
15 Correct 102 ms 9992 KB Output is correct
16 Correct 109 ms 9408 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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