oj.uz

답안 #915786

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
915786 2024-01-24T17:19:22 Z Amr Joker (BOI20_joker) C++14
25 / 100
 244 ms 32592 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++)
    {
        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--;
        }

        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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 15448 KB Output is correct
2 Correct 9 ms 15448 KB Output is correct
3 Correct 11 ms 15452 KB Output is correct
4 Correct 11 ms 15452 KB Output is correct
5 Correct 10 ms 15452 KB Output is correct
6 Correct 10 ms 15536 KB Output is correct
7 Correct 10 ms 15328 KB Output is correct
8 Incorrect 10 ms 15312 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 15448 KB Output is correct
2 Correct 9 ms 15448 KB Output is correct
3 Correct 11 ms 15452 KB Output is correct
4 Correct 11 ms 15452 KB Output is correct
5 Correct 10 ms 15452 KB Output is correct
6 Correct 10 ms 15536 KB Output is correct
7 Correct 10 ms 15328 KB Output is correct
8 Incorrect 10 ms 15312 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 15448 KB Output is correct
2 Correct 9 ms 15448 KB Output is correct
3 Correct 220 ms 31596 KB Output is correct
4 Correct 216 ms 31612 KB Output is correct
5 Correct 219 ms 32108 KB Output is correct
6 Correct 208 ms 31724 KB Output is correct
7 Correct 226 ms 31900 KB Output is correct
8 Correct 226 ms 31716 KB Output is correct
9 Correct 228 ms 30972 KB Output is correct
10 Correct 218 ms 31368 KB Output is correct
11 Correct 214 ms 32592 KB Output is correct
12 Correct 229 ms 32124 KB Output is correct
13 Correct 221 ms 31148 KB Output is correct
14 Correct 230 ms 31896 KB Output is correct
15 Correct 244 ms 32220 KB Output is correct
16 Correct 218 ms 32512 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 15448 KB Output is correct
2 Correct 9 ms 15448 KB Output is correct
3 Correct 11 ms 15452 KB Output is correct
4 Correct 11 ms 15452 KB Output is correct
5 Correct 10 ms 15452 KB Output is correct
6 Correct 10 ms 15536 KB Output is correct
7 Correct 10 ms 15328 KB Output is correct
8 Incorrect 10 ms 15312 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 15448 KB Output is correct
2 Correct 9 ms 15448 KB Output is correct
3 Correct 11 ms 15452 KB Output is correct
4 Correct 11 ms 15452 KB Output is correct
5 Correct 10 ms 15452 KB Output is correct
6 Correct 10 ms 15536 KB Output is correct
7 Correct 10 ms 15328 KB Output is correct
8 Incorrect 10 ms 15312 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 15448 KB Output is correct
2 Correct 9 ms 15448 KB Output is correct
3 Correct 11 ms 15452 KB Output is correct
4 Correct 11 ms 15452 KB Output is correct
5 Correct 10 ms 15452 KB Output is correct
6 Correct 10 ms 15536 KB Output is correct
7 Correct 10 ms 15328 KB Output is correct
8 Incorrect 10 ms 15312 KB Output isn't correct
9 Halted 0 ms 0 KB -