oj.uz

Submission #915791

# Submission time Handle Problem Language Result Execution time Memory
915791 2024-01-24T17:34:40 Z Amr Joker (BOI20_joker) C++14
25 / 100
 281 ms 30996 KB 
#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=2e5+7;
#define ll int
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;
}
ll n , m , q;
pair<ll,ll> p[N];
pair<ll,ll>  a[N];
vector<vector<ll> > qe(N,vector<ll> (3));
ll ans[N];
ll siz[N];
ll cycles = 0;
vector<vector<ll>> roll;
ll sqr = 4;
bool cmp(vector<ll> x, vector<ll> y)
{
    if(x[0]/sqr==y[0]/sqr) return x[1] < y[1];
    return x[0]<y[0];
}
pair<ll,ll> get(ll x)
{
    if(p[x].first==x) return {x,0};
    pair<ll,ll> ho = get(p[x].first);
    return {ho.first, p[x].second^ho.second};
}
void nonmerge(vector<ll> v)
{
    ll x= v[0] , y = v[1] , b = v[2];
    if(b==1)
    {
    siz[y] -= siz[x];
    p[x] = {x,0};
    return;
    }
    else
    {
        if(b==2) cycles--; return;
    }
}
void merg(ll x, ll y)
{

    pair<ll,ll> paix = get(x);
    pair<ll,ll> paiy = get(y);
    if(paix.first==paiy.first)
    {
        if(paix.second==paiy.second) {cycles++;roll.push_back({x,y,2});}
        else
        roll.push_back({x,y,0});
    }
    else
    {
        ll xx = paix.first , yy = paiy.first;
        if(siz[xx]<siz[yy])
        {
            p[xx] = {yy,(paix.second==paiy.second)};
            siz[yy] +=siz[xx];
            roll.push_back({xx,yy,1});
        }
        else
        {
            p[yy] = {xx,(paix.second==paiy.second)};
            siz[xx]+=siz[yy];
            roll.push_back({yy,xx,1});
        }
    }
}
void solve()
{

    cin >> n >> m >> q;
    sqr = max(1,m/int(sqrt(q)));
    for(int i = 1; i <= n; i++) p[i] = {i,0},siz[i] = 1;
    for(int i = 1; i <= m; i++) cin >> a[i].first >> a[i].second;
    for(int i = 1; i <= q; i++)
    {
        cin >> qe[i][0] >> qe[i][1];
    }
    for(int i = 1; i <= q; i++) qe[i][2] = i;
    sort(qe.begin()+1,qe.begin()+q+1,cmp);
    //for(int i = 1; i <= q; i++) cout << qe[i][1] << " "; cout << endl;
    ll st = 0, en = m+1;
    for(int i = 1; i <= q; i++)
    {
        if(i!=1&&qe[i-1][0]/sqr!=qe[i][0]/sqr)
        {
            while(roll.sz)
            {
            nonmerge(roll.back());
            roll.pop_back();
            }
        st = 0, en = m+1;
        }
        ll l = qe[i][0] , r = qe[i][1];


        while(roll.sz&&st!=0&&st/sqr>=l/sqr)
        {
            //
            nonmerge(roll.back());
            roll.pop_back();
            st--;
        }
        //cout << st << " ";
        while(roll.sz&&en<=r)
        {
            //
            nonmerge(roll.back());
            roll.pop_back();
            en++;
        }
        while(en>r+1)
        {
            en--;
            merg(a[en].first,a[en].second);

            // mege en
        }
        while(st<l-1)
        {
            st++;
            merg(a[st].first,a[st].second);
          //  cout << cycles << endl;
            // merge st;
        }
        //cout << endl;
        //for(int i = 1; i <= n; i++) cout << p[i].first << " " << p[i].second << endl;
       // cout << l << " " << r << ": " << st << " " << en<< " " << cycles  << endl;
         ans[qe[i][2]] = bool(cycles);
    }
    for(int i = 1; i <= q; i++)
    {
        if(ans[i]) Yes; else No;
    }
}
int main(){
    //freopen("friday.in","r",stdin);
    //freopen("friday.out","w",stdout);
    fast;
    //cin >> TT;
    while(TT--)
        solve();

    return 0;
}

Compilation message

Joker.cpp: In function 'void nonmerge(std::vector<int>)':
Joker.cpp:62:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   62 |         if(b==2) cycles--; return;
      |         ^~
Joker.cpp:62:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   62 |         if(b==2) cycles--; return;
      |                            ^~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15452 KB Output is correct
2 Correct 11 ms 15452 KB Output is correct
3 Correct 10 ms 15452 KB Output is correct
4 Correct 11 ms 15308 KB Output is correct
5 Correct 12 ms 15448 KB Output is correct
6 Correct 11 ms 15452 KB Output is correct
7 Correct 12 ms 15452 KB Output is correct
8 Incorrect 11 ms 15448 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15452 KB Output is correct
2 Correct 11 ms 15452 KB Output is correct
3 Correct 10 ms 15452 KB Output is correct
4 Correct 11 ms 15308 KB Output is correct
5 Correct 12 ms 15448 KB Output is correct
6 Correct 11 ms 15452 KB Output is correct
7 Correct 12 ms 15452 KB Output is correct
8 Incorrect 11 ms 15448 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15452 KB Output is correct
2 Correct 11 ms 15452 KB Output is correct
3 Correct 265 ms 30184 KB Output is correct
4 Correct 261 ms 30752 KB Output is correct
5 Correct 248 ms 30024 KB Output is correct
6 Correct 270 ms 30960 KB Output is correct
7 Correct 225 ms 29928 KB Output is correct
8 Correct 223 ms 29304 KB Output is correct
9 Correct 225 ms 29688 KB Output is correct
10 Correct 281 ms 30996 KB Output is correct
11 Correct 225 ms 29948 KB Output is correct
12 Correct 264 ms 30204 KB Output is correct
13 Correct 229 ms 30092 KB Output is correct
14 Correct 253 ms 30196 KB Output is correct
15 Correct 269 ms 29944 KB Output is correct
16 Correct 271 ms 30452 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15452 KB Output is correct
2 Correct 11 ms 15452 KB Output is correct
3 Correct 10 ms 15452 KB Output is correct
4 Correct 11 ms 15308 KB Output is correct
5 Correct 12 ms 15448 KB Output is correct
6 Correct 11 ms 15452 KB Output is correct
7 Correct 12 ms 15452 KB Output is correct
8 Incorrect 11 ms 15448 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15452 KB Output is correct
2 Correct 11 ms 15452 KB Output is correct
3 Correct 10 ms 15452 KB Output is correct
4 Correct 11 ms 15308 KB Output is correct
5 Correct 12 ms 15448 KB Output is correct
6 Correct 11 ms 15452 KB Output is correct
7 Correct 12 ms 15452 KB Output is correct
8 Incorrect 11 ms 15448 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15452 KB Output is correct
2 Correct 11 ms 15452 KB Output is correct
3 Correct 10 ms 15452 KB Output is correct
4 Correct 11 ms 15308 KB Output is correct
5 Correct 12 ms 15448 KB Output is correct
6 Correct 11 ms 15452 KB Output is correct
7 Correct 12 ms 15452 KB Output is correct
8 Incorrect 11 ms 15448 KB Output isn't correct
9 Halted 0 ms 0 KB -