oj.uz

Submission #1054225

# Submission time Handle Problem Language Result Execution time Memory
1054225 2024-08-12T07:46:40 Z PetreaIon Joker (BOI20_joker) C++14
0 / 100
 2000 ms 5008 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
vector<int> counter_point;
vector<int> last_c;//Vedem cum se conecteaza grafurile deci, daca se formeaza 2 grafuri atunci vedem daca unul din ele are numar impar de noduri
int n,m,q;
int l,r;
vector <pair<int,int>> c;
void trans(int num,int num1)
{
    for(int i=1;i<=n;i++)
    {
        if(last_c[i]==num)
        last_c[i]=num1;
    }
}
void last_counter()
{
    last_c.push_back(0);
    for(int i=1;i<=n;i++)
    {
        if(counter_point[i]>=2)
        {
            last_c.push_back(i);//E vslid daca are numarul sau
        }
        else
            last_c.push_back(0);//E invalid daca e zero
    }
    vector<int> graf_counter(n,0);
    for(int i=1;i<=m;i++)
    {
        if(last_c[c[i].first]!=0&&last_c[c[i].second]!=0&&last_c[c[i].first]!=last_c[c[i].second])
        {
            trans(last_c[c[i].first],last_c[c[i].second]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        graf_counter[last_c[i]]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(graf_counter[i]%2!=0)
        {
            cout<<"YES";
            return ;
        }
    }
    cout<<"NO";
}
void find_num(int num)
{
    for(int i=1;i<=m;i++)
    {
        if(c[i].first==num)
        {
            counter_point[c[i].second]--;
            if(counter_point[c[i].second]==1)
                find_num(c[i].second);
            return ;
        }
        if(c[i].second==num)
        {
            counter_point[c[i].first]--;
            if(counter_point[c[i].first]==1)
                find_num(c[i].first);
            return ;
        }
    }

}
void valid()
{
    for(int i=0;i<=n;i++)
    {
        counter_point.push_back(0);
    }
    for(int i=1;i<l;i++)
    {
        counter_point[c[i].first]++;
        counter_point[c[i].second]++;
    }
    for(int i=r+1;i<=m;i++)
    {
        counter_point[c[i].first]++;
        counter_point[c[i].second]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(counter_point[i]==1)
        {
            find_num(i);
        }
    }
    int counter=0;
    for(int i=1;i<=n;i++)
    {
        if(counter_point[i]>=2)
            counter++;
    }
    if(counter%2!=0)
        cout<<"YES";
    else
    {
        last_counter();
    }
}
int main()
{

    int aux,aux1;
    cin>>n>>m>>q;
    c.push_back(make_pair(0,0));

    for(int i=0;i<m;i++)//citim conexiunile de baza
    {
        cin>>aux>>aux1;
        c.push_back(make_pair(aux,aux1));
    }
    for(int i=0;i<q;i++)
    {
        cin>>l>>r;
        valid();
    }
    return 0;
}
/*
6 8 2
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
4 8
4 7
*/

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 2069 ms 5008 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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