Submission #914322

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
914322	2024-01-21T15:54:02 Z	Amr	Joker (BOI20_joker)	C++14	25 / 100	75 ms	11656 KB

Joker

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define S second
#define F first
#define all(x) (x).begin(),(x).end()
#define sz size()
#define Yes cout << "YES" << endl
#define No cout << "NO" << endl
#define pb(x) push_back(x);
#define endl '\n'
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int N=3e5+7;
ll INF=INT_MAX,mod=1e9+7;
int TT=1;
ll power(ll x, unsigned int y)
{
    ll res = 1;
    x = x; // % mod;
    if (x == 0) return 0;
    while (y > 0)
    {
        if (y & 1) res = (res*x)  ; // % mod;
        y = y>>1;
        x = (x*x) ; // % mod;
    }
    return res;
}
pair<ll,ll> p[N];
ll siz[N];
pair<ll,ll> get(ll x)
{
    if(p[x].F==x) return p[x];
    pair<ll,ll> hi = get(p[x].F);
    return {hi.F,hi.S^p[x].S};
}
pair<ll,ll> a[N];
void solve()
{

    ll n , m, q; cin >> n >> m >> q;
    for(int i = 1; i <= n; i++) siz[i] = 1,p[i] = {i,0};
    ll lst = 0;
    for(int i = 1; i <= m ; i++) cin >> a[i].F >> a[i].S;
    for(int i = m; i >=1; i--)
    {
        ll x = a[i].F , y = a[i].S;
        pair<ll,ll> paix = get(x);
        pair<ll,ll> paiy = get(y);
        ll xx = paix.F, yy = paiy.F;
       // cout << xx << " " << yy << endl;
        if(xx!=yy)
        {
            bool b = (paix.S==paiy.S);
            if(siz[xx]<siz[yy])
            {
                p[xx] = {yy,b};
                siz[yy]+=siz[xx];

            }
            else
            {
                p[yy] = {xx,b};
                siz[xx]+=siz[yy];
            }
        }
        else
        {
            if(paix.S==paiy.S&&lst==0) {lst = i;}
        }
    }
    while(q--)
    {
        ll l, r; cin >> l >> r;
        if(r<lst) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}
int main(){
    //freopen("friday.in","r",stdin);
    //freopen("friday.out","w",stdout);
    fast;
    //cin >> TT;
    while(TT--)
        solve();

    return 0;
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	56 ms	11412 KB	Output is correct
4	Correct	57 ms	11396 KB	Output is correct
5	Correct	64 ms	11408 KB	Output is correct
6	Correct	62 ms	11396 KB	Output is correct
7	Correct	59 ms	11400 KB	Output is correct
8	Correct	54 ms	9556 KB	Output is correct
9	Correct	54 ms	11656 KB	Output is correct
10	Correct	60 ms	11604 KB	Output is correct
11	Correct	66 ms	11348 KB	Output is correct
12	Correct	59 ms	11344 KB	Output is correct
13	Correct	57 ms	9296 KB	Output is correct
14	Correct	75 ms	9216 KB	Output is correct
15	Correct	59 ms	11348 KB	Output is correct
16	Correct	62 ms	11400 KB	Output is correct