oj.uz

Submission #869049

# Submission time Handle Problem Language Result Execution time Memory
869049 2023-11-03T03:45:23 Z prohacker Joker (BOI20_joker) C++14
0 / 100
 110 ms 8396 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int,int>
#define mp make_pair

using namespace std;

const int N = 2e5+10;
const int INF = INT_MAX;
const int mod = 1e9+7;

int n,m,t;
pair<int,int> edges[N];
int color[N],lab[N];
int cnt,lst[N];
stack<int> st;

void make_set() {
    for(int i = 1 ; i <= n ; i++) {
        lab[i] = i;
        color[i] = 0;
    }
}

pii Find(int u) {
    if(u == lab[u]) {
        return pii(u,color[u]);
    }
    pii p = Find(lab[u]);
    lab[u] = p.first;
    color[u] = (color[u]^p.second);
    return pii(lab[u],color[u]);
}

void join(int u, int v) {
    pii hihi = Find(u);
    pii hehe = Find(v);
    if(hihi.first != hehe.first) {
        lab[hehe.first] = hihi.first;
        color[hehe.first] = (color[u]^color[v]^1);
        st.push(v);
        return;
    }
    if(hihi.second == hehe.second) {
        cnt++;
        st.push(-1);
    }
}

void roll_back(int lim) {
    while(st.size() > lim) {
        int p = st.top();
        st.pop();
        if(p == -1) {
            cnt--;
        }
        else {
            lab[p] = p;
            color[p] = 0;
        }
    }
}

void solve(int l, int r, int L, int R) {
    if(l > r) {
        return;
    }
    int mid = l + r >> 1;
    int lim1 = st.size();
    for(int i = l ; i <= mid ; i++) {
        join(edges[i].first,edges[i].second);
    }
    int lim2 = st.size();
    int best = R;
    while(best and !cnt) {
        best--;
        if(!best) {
            break;
        }
        join(edges[best].first,edges[best].second);
    }
    lst[mid] = best;
    roll_back(lim2);
    solve(mid+1,r,best,R);
    roll_back(lim1);
    for(int i = r ; i >= mid ; i--) {
        join(edges[i].first,edges[i].second);
    }
    solve(l,mid-1,L,best);
    roll_back(lim1);
}

signed main()
{
    if (fopen("solve.inp", "r")) {
        freopen("solve.inp", "r", stdin);
        freopen("solve.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> t;
    for(int i = 1 ; i <= m ; i++) {
        int u,v; cin >> u >> v;
        edges[i] = {u,v};
    }
    make_set();
    edges[0] = {0,1};
    solve(0,m,0,m+1);
    while(t--) {
        int l,r; cin >> l >> r;
        if(r < lst[l-1]) {
            cout << "YES" << '\n';
        }
        else {
            cout << "NO" << '\n';
        }
    }
    return 0;
}

Compilation message

Joker.cpp: In function 'void roll_back(int)':
Joker.cpp:52:21: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |     while(st.size() > lim) {
      |           ~~~~~~~~~~^~~~~
Joker.cpp: In function 'void solve(int, int, int, int)':
Joker.cpp:69:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |     int mid = l + r >> 1;
      |               ~~^~~
Joker.cpp: In function 'int main()':
Joker.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen("solve.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen("solve.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Incorrect 0 ms 2396 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 2392 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Incorrect 0 ms 2396 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Incorrect 110 ms 8396 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 2392 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Incorrect 0 ms 2396 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 2392 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Incorrect 0 ms 2396 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 2392 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Incorrect 0 ms 2396 KB Output isn't correct
6 Halted 0 ms 0 KB -