Submission #1054225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054225		PetreaIon	Joker (BOI20_joker)	C++14	0 / 100	2069 ms	5008 KiB

Joker

#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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29