oj.uz

Submission #1038336

# Submission time Handle Problem Language Result Execution time Memory
1038336 2024-07-29T17:01:00 Z amine_aroua Joker (BOI20_joker) C++17
14 / 100
 2000 ms 19144 KB 
#include<bits/stdc++.h>
using namespace std;

vector<pair<int ,int>> edges;
struct DSU
{
    vector<int> e;
    vector<int> col;
    vector<vector<int>> children;
    bool bip;
    vector<vector<int>> hist;
    void init(int n)
    {
        bip = 1;
        e.assign(n , -1);
        col.assign(n , 0);
        children.assign(n , {});
        for(int i = 0 ; i < n ;i++)
            children[i].push_back(i);
    }
    int get(int x)
    {
        return (e[x] < 0 ? x : get(e[x]));
    }
    bool is_bip()
    {
        return bip;
    }
    void unite(int u , int v)
    {
        if(u == v)
            return ;
        bool same_col = col[u] == col[v];
        u = get(u) , v = get(v);
        if(u == v)
        {
            hist.push_back({-1 , -1 , -1 , -1 ,same_col ,bip});
            if(same_col)
            {
                bip = 0;
            }
            return ;
        }
        if(e[u] > e[v])
        {
            swap(u , v);
        }
        hist.push_back({u , v , e[u] , e[v] ,same_col, bip});
        e[u]+=e[v];
        e[v] = u;
        for(auto node : children[v])
        {
            col[node]^=same_col;
            children[u].push_back(node);
        }
        children[v].clear();
    }
    void roll_back()
    {
        auto last = hist.back();
        hist.pop_back();
        if(last[0] == -1)
        {
            bip = last.back();
        }
        else
        {
            e[last[0]] = last[2];
            e[last[1]] = last[3];
            for(int i = 0 ; i < (-last[3]) ; i++)
            {
                auto tp = children[last[0]].back();
                children[last[0]].pop_back();
                children[last[1]].push_back(tp);
                col[tp]^=last[4];
            }
            reverse(children[last[1]].begin() , children[last[1]].end());
        }
    }
    void roll_back(int x)
    {
        while (x--)
        {
            roll_back();
        }
        
    }
    void clear()
    {
        roll_back((int)hist.size());
    }
}dsu;
int n , m , q;
vector<int> nxt;
void solve(int l , int r , int optl , int optr)
{
    if(l > r)
        return ;
    int mid = (l + r)/2;
    int ops = 0;
    for(int i = l ; i < mid ; i++)
    {
        ops++;
        dsu.unite(edges[i].first , edges[i].second);
    }
    int opt = optr;
    for(int i = optr ; i >= max(mid , optl) ; i--)
    {
        if(!dsu.is_bip())
        {
            break;
        }
        opt = i;
        if(i < m)
        {
            ops++;
            dsu.unite(edges[i].first , edges[i].second);
        }
    }
    nxt[mid] = opt;
    dsu.roll_back(ops);
    ops = 0;
    for(int i = opt + 1 ; i <= optr ;i++)
    {
        if(i < m)
        {
            dsu.unite(edges[i].first , edges[i].second);
            ops++;
        }
    }
    solve(l , mid - 1 , optl , opt);
    dsu.roll_back(ops);
    ops = 0;
    for(int i = l ; i <= mid ; i++)
    {
        ops++;
        dsu.unite(edges[i].first , edges[i].second);
    }
    solve(mid + 1 , r , opt , optr);
    dsu.roll_back(ops);
    ops = 0;
}
signed main()
{
    cin>>n>>m>>q;
    nxt.assign(m , m);
    dsu.init(n);
    for(int i = 0 ; i < m ; i++)
    {
        int u , v;
        cin>>u>>v;
        u-- , v--;
        edges.push_back({u , v});
    }
    solve(0 , m - 1 , 0 , m);
    for(int i = 0 ; i <n ; i++)
    {
        assert(dsu.e[i] == -1);
    }
    for(int i = 0 ; i< q; i++)
    {
        int l , r;
        cin>>l>>r;
        l-- , r--;
        if(nxt[l] <= r)
        {
            cout<<"NO\n";
        }
        else
        {
            cout<<"YES\n";
        }
    }
}

Subtask #1
6.0 / 6.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 372 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 5 ms 604 KB Output is correct
30 Correct 6 ms 604 KB Output is correct
31 Correct 6 ms 600 KB Output is correct
32 Correct 5 ms 600 KB Output is correct
33 Correct 5 ms 604 KB Output is correct
34 Correct 6 ms 784 KB Output is correct
35 Correct 6 ms 604 KB Output is correct
36 Correct 10 ms 604 KB Output is correct
37 Correct 6 ms 604 KB Output is correct
38 Correct 11 ms 604 KB Output is correct
39 Correct 5 ms 600 KB Output is correct
40 Correct 5 ms 604 KB Output is correct
41 Correct 5 ms 604 KB Output is correct
42 Correct 6 ms 700 KB Output is correct
43 Correct 5 ms 604 KB Output is correct
44 Correct 5 ms 604 KB Output is correct
45 Correct 6 ms 604 KB Output is correct
46 Correct 6 ms 604 KB Output is correct
47 Correct 5 ms 604 KB Output is correct
48 Correct 6 ms 600 KB Output is correct
49 Correct 6 ms 604 KB Output is correct
50 Correct 8 ms 612 KB Output is correct
51 Correct 6 ms 600 KB Output is correct
52 Correct 5 ms 616 KB Output is correct
53 Correct 6 ms 604 KB Output is correct
54 Correct 6 ms 604 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 2085 ms 19108 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 372 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Execution timed out 2085 ms 19108 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 372 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 5 ms 604 KB Output is correct
30 Correct 6 ms 604 KB Output is correct
31 Correct 6 ms 600 KB Output is correct
32 Correct 5 ms 600 KB Output is correct
33 Correct 5 ms 604 KB Output is correct
34 Correct 6 ms 784 KB Output is correct
35 Correct 6 ms 604 KB Output is correct
36 Correct 10 ms 604 KB Output is correct
37 Correct 6 ms 604 KB Output is correct
38 Correct 11 ms 604 KB Output is correct
39 Correct 5 ms 600 KB Output is correct
40 Correct 5 ms 604 KB Output is correct
41 Correct 5 ms 604 KB Output is correct
42 Correct 6 ms 700 KB Output is correct
43 Correct 5 ms 604 KB Output is correct
44 Correct 5 ms 604 KB Output is correct
45 Correct 6 ms 604 KB Output is correct
46 Correct 6 ms 604 KB Output is correct
47 Correct 5 ms 604 KB Output is correct
48 Correct 6 ms 600 KB Output is correct
49 Correct 6 ms 604 KB Output is correct
50 Correct 8 ms 612 KB Output is correct
51 Correct 6 ms 600 KB Output is correct
52 Correct 5 ms 616 KB Output is correct
53 Correct 6 ms 604 KB Output is correct
54 Correct 6 ms 604 KB Output is correct
55 Execution timed out 2065 ms 19144 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 372 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 5 ms 604 KB Output is correct
30 Correct 6 ms 604 KB Output is correct
31 Correct 6 ms 600 KB Output is correct
32 Correct 5 ms 600 KB Output is correct
33 Correct 5 ms 604 KB Output is correct
34 Correct 6 ms 784 KB Output is correct
35 Correct 6 ms 604 KB Output is correct
36 Correct 10 ms 604 KB Output is correct
37 Correct 6 ms 604 KB Output is correct
38 Correct 11 ms 604 KB Output is correct
39 Correct 5 ms 600 KB Output is correct
40 Correct 5 ms 604 KB Output is correct
41 Correct 5 ms 604 KB Output is correct
42 Correct 6 ms 700 KB Output is correct
43 Correct 5 ms 604 KB Output is correct
44 Correct 5 ms 604 KB Output is correct
45 Correct 6 ms 604 KB Output is correct
46 Correct 6 ms 604 KB Output is correct
47 Correct 5 ms 604 KB Output is correct
48 Correct 6 ms 600 KB Output is correct
49 Correct 6 ms 604 KB Output is correct
50 Correct 8 ms 612 KB Output is correct
51 Correct 6 ms 600 KB Output is correct
52 Correct 5 ms 616 KB Output is correct
53 Correct 6 ms 604 KB Output is correct
54 Correct 6 ms 604 KB Output is correct
55 Execution timed out 2085 ms 19108 KB Time limit exceeded
56 Halted 0 ms 0 KB -