oj.uz

Submission #1112107

# Submission time Handle Problem Language Result Execution time Memory
1112107 2024-11-13T16:33:51 Z Ciprian Joker (BOI20_joker) C++14
0 / 100
 2000 ms 9672 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pi pair<int,int>
const int N=2e5+4;
vector<int> root(N), dist(N);
int find(int x){
    if(x==root[x])return x;
    
    return find(root[x]);
}
int cnt(int x){
    if(x==root[x])return dist[x];
    return dist[x] + cnt(root[x]);
    
}
bool unify(int x, int y){
    int a=find(x);
    int b=find(y);
    int c1=cnt(x), c2=cnt(y);
   // cout<<a<<" "<<b<<endl;
    
    if(a==b && c1%2==c2%2){
        return true;
    }if(a!=b){
        root[b]=a;
        dist[b]=1;
    }
    
    return false;
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    vector<pi> edge;
    for(int j=0; j<m; j++){
        int u,v;
        cin>>u>>v;
        edge.push_back({u,v});
    }for(int j=0; j<q; j++){
        int l,r;
        cin>>l>>r;
        l--;
        r--;
        for(int i=1; i<=n; i++)root[i]=i, dist[i]=0;
        string ans="NO";
        for(int i=0; i<l; i++){
            auto p=edge[i];
            if(unify(p.first, p.second)){
                ans="YES";
                //cout<<cnt(p.first)<<" "<<cnt(p.second)<<endl;
            }
        }for(int i=r+1; i<m; i++){
            auto p=edge[i];
            if(unify(p.first, p.second)){
                ans="YES";
                //cout<<cnt(p.first)<<" "<<cnt(p.second)<<endl;
            }
        }cout<<ans<<endl;
    }

    return 0;
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3408 KB Output is correct
2 Correct 3 ms 3420 KB Output is correct
3 Execution timed out 2045 ms 9672 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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