oj.uz

Submission #1045668

# Submission time Handle Problem Language Result Execution time Memory
1045668 2024-08-06T06:51:25 Z hirayuu_oj Joker (BOI20_joker) C++17
25 / 100
 2000 ms 28808 KB 
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;

struct odd_cycle {
    int size;
    vector<int> uni;
    int time;
    stack<array<int,4>> memo;
    bool isok;
    odd_cycle(int sz) {
        size=sz;
        time=0;
        isok=false;
        memo.push({-1,-1,0,-1});
        uni.resize(size*2,-1);
    }
    int leader(int p) {
        while(uni[p]>=0)p=uni[p];
        return p;
    }
    void merge(pair<int,int> x) {
        if(isok) {
            time++;
            return;
        }
        int u=x.first;
        int v=x.second;
        int a=leader(u),b=leader(v),c=leader(u+size),d=leader(v+size);
        if(-uni[a]>-uni[d])swap(a,d);
        if(-uni[b]>-uni[c])swap(b,c);
        memo.push({a,uni[a],isok,time});
        memo.push({b,uni[b],isok,time});
        memo.push({c,uni[c],isok,time});
        memo.push({d,uni[d],isok,time});
        if(a!=d) {
            uni[d]+=uni[a];
            uni[a]=d;
        }
        if(b!=c) {
            uni[c]+=uni[b];
            uni[b]=c;
        }
        if(leader(u)==leader(u+size))isok=true;
        time++;
    }
    void undo() {
        time--;
        while(memo.top()[3]==time) {
            isok=memo.top()[2];
            uni[memo.top()[0]]=memo.top()[1];
            memo.pop();
        }
    }

};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,M,Q;
    cin>>N>>M>>Q;
    const int backet=316;
    vector<pair<int,int>> edge(M);
    rep(i,M) {
        int u,v;
        cin>>u>>v;
        edge[i]={u-1,v-1};
    }
    vector<vector<array<int,3>>> query(3+M/backet);
    rep(i,Q) {
        int l,r;
        cin>>l>>r;
        query[(l-1)/backet].push_back({-r,l-1,i});
    }
    vector<string> ans(Q);
    rep(i,3+M/backet) {
        if(query[i].empty())continue;
        sort(all(query[i]));
        odd_cycle uni(N);
        rep(j,backet*i)uni.merge(edge[j]);
        int ri=M;
        rep(j,query[i].size()) {
            int r=-query[i][j][0];
            int l=query[i][j][1];
            int ind=query[i][j][2];
            rng(k,r,ri) {
                uni.merge(edge[k]);
            }
            ri=r;
            rep(k,l%backet) {
                uni.merge(edge[i*backet+k]);
            }
            if(uni.isok)ans[ind]="YES";
            else ans[ind]="NO";
            rep(k,l%backet) {
                uni.undo();
            }
        }
    }
    rep(i,Q) {
        cout<<ans[i]<<"\n";
    }
}

Compilation message

Joker.cpp: In function 'int main()':
Joker.cpp:3:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(i,n) for(int i=0; i<(n); i++)
      |                                ^
Joker.cpp:85:9: note: in expansion of macro 'rep'
   85 |         rep(j,query[i].size()) {
      |         ^~~

Subtask #1
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 Execution timed out 2095 ms 348 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
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 Execution timed out 2095 ms 348 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
25.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 Correct 81 ms 22720 KB Output is correct
4 Correct 76 ms 28808 KB Output is correct
5 Correct 67 ms 18112 KB Output is correct
6 Correct 98 ms 21960 KB Output is correct
7 Correct 68 ms 22404 KB Output is correct
8 Correct 83 ms 21184 KB Output is correct
9 Correct 76 ms 21436 KB Output is correct
10 Correct 95 ms 22276 KB Output is correct
11 Correct 77 ms 22232 KB Output is correct
12 Correct 79 ms 22552 KB Output is correct
13 Correct 96 ms 21028 KB Output is correct
14 Correct 80 ms 21660 KB Output is correct
15 Correct 106 ms 22084 KB Output is correct
16 Correct 84 ms 23488 KB Output is correct

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 Execution timed out 2095 ms 348 KB Time limit exceeded
5 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 Execution timed out 2095 ms 348 KB Time limit exceeded
5 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 Execution timed out 2095 ms 348 KB Time limit exceeded
5 Halted 0 ms 0 KB -