oj.uz

Submission #1093586

# Submission time Handle Problem Language Result Execution time Memory
1093586 2024-09-27T04:34:36 Z ntdaccode Joker (BOI20_joker) C++17
6 / 100
 71 ms 14136 KB 
#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int mod=1e9+7;
const int M=2e5+10;
const int N=1e3+10;
const int SIZE=316;
int n,m,q;
int x[M],y[M];
struct query
{
  int l,r,idx;
}Q[M];
int ret[M];
// dsu
int id[M];
int dd[M],lz[M];
#define tp tuple<int,int,int,int>
stack<tp> sk;
stack<tp> ks;
int finded(int u,int &v)
{
  v^=lz[u];
  return id[u] < 0 ? u : finded(id[u],v);
}
bool unioned(int tt ,int u,int v)
{
  int pos=0,pos2=0;
  u=finded(u,pos);
  v=finded(v,pos2);

  if(u==v)
  {
    if(pos==pos2) return true;
    return false;
  }
  if(id[u]>id[v]) swap(u,v);
  if(tt!=0)
  {
  sk.push({tt,id[u],id[v],pos==pos2});
  ks.push({tt,u,v,pos==pos2});
  }
  if(pos==pos2) lz[v]^=1;
  id[u]+=id[v];
  id[v]=u;
  return false;
}
int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  #define task "1"
  if(fopen(task".inp","r"))
  {
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
  }
  cin >> n >> m >> q;
  fori(i,1,m) cin >> x[i] >> y[i];
  fori(i,1,q)
  {
    cin >> Q[i].l >> Q[i].r ;
    Q[i].idx=i;
  }
  sort(Q+1,Q+q+1,[&] (const query a,const query b)
       {
         if(a.l/SIZE==b.l/SIZE) return a.r> b.r;
         return  a.l<b.l;
       });
  memset(id,-1,sizeof(id));
  int r=m;
  bool ok=0;
  fori(i,1,q)
  {
   // cout << Q[i].l << " " << Q[i].r << "ds\n";
    if(Q[i-1].l/SIZE!=Q[i].l/SIZE)
    {
      while(!sk.empty())
      {
        auto[tt,idu,idv,dog] = sk.top();
        auto[tt2,u,v,cho] = ks.top();
        sk.pop();
        ks.pop();
        lz[v]^=dog;
        id[u]=idu;
        id[v]=idv;
      }
      fori(j,max(1,(Q[i-1].l/SIZE)*SIZE),(Q[i].l/SIZE)*SIZE-1) if(unioned(0,x[j],y[j])) ok=1;
      r=m;
    }
    bool okk=0;
    while(Q[i].r<r&&r/SIZE!=Q[i].l/SIZE)
    {
      if(x[r]==y[r]) continue;
      if(unioned(1,x[r],y[r])) okk=1;
      r--;
    }
    //if(Q[i].l==2&&Q[i].r==6) cout << r << " ";
    if(ok||okk) ret[Q[i].idx]=1;
    else
    {
      int ook=0;
      int cnt=6;
      fori(j,max(1,(Q[i].l/SIZE)*SIZE),Q[i].l-1)
      {
        if(x[j]==y[j]) continue;
        if(unioned(2,x[j],y[j])) ook=1;
      }
      fori(j,Q[i].r+1,r)
      {
        if(x[r]==y[r]) continue;
        if(unioned(2,x[j],y[j])) ook=1;
      }

      while(!sk.empty())
      {
        auto[tt,idu,idv,cho] = sk.top();
        auto[tt2,u,v,dog] = ks.top();
        if(tt!=2) break;
        sk.pop();
        ks.pop();
        lz[v]^=dog;
        id[u]=idu;
        id[v]=idv;
      }

      if(ook) ret[Q[i].idx]=1;
    }

  }
  fori(i,1,q)
  {
    if(ret[i]) cout << "YES\n";
    else cout << "NO\n";
  }
}

Compilation message

Joker.cpp: In function 'int32_t main()':
Joker.cpp:109:11: warning: unused variable 'cnt' [-Wunused-variable]
  109 |       int cnt=6;
      |           ^~~
Joker.cpp:61:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:62:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1112 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 2 ms 1236 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 1 ms 1236 KB Output is correct
15 Correct 2 ms 1116 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 1 ms 1116 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Correct 2 ms 1368 KB Output is correct
20 Correct 1 ms 1116 KB Output is correct
21 Correct 1 ms 1156 KB Output is correct
22 Correct 1 ms 1288 KB Output is correct
23 Correct 2 ms 1116 KB Output is correct
24 Correct 2 ms 1116 KB Output is correct
25 Correct 1 ms 1116 KB Output is correct
26 Correct 1 ms 1116 KB Output is correct
27 Correct 1 ms 1116 KB Output is correct
28 Correct 1 ms 1116 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1112 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 2 ms 1236 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 1 ms 1236 KB Output is correct
15 Correct 2 ms 1116 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 1 ms 1116 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Correct 2 ms 1368 KB Output is correct
20 Correct 1 ms 1116 KB Output is correct
21 Correct 1 ms 1156 KB Output is correct
22 Correct 1 ms 1288 KB Output is correct
23 Correct 2 ms 1116 KB Output is correct
24 Correct 2 ms 1116 KB Output is correct
25 Correct 1 ms 1116 KB Output is correct
26 Correct 1 ms 1116 KB Output is correct
27 Correct 1 ms 1116 KB Output is correct
28 Correct 1 ms 1116 KB Output is correct
29 Correct 11 ms 1368 KB Output is correct
30 Incorrect 5 ms 1412 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1112 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 2 ms 1236 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 1 ms 1236 KB Output is correct
15 Correct 2 ms 1116 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 1 ms 1116 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Correct 2 ms 1368 KB Output is correct
20 Correct 1 ms 1116 KB Output is correct
21 Correct 1 ms 1156 KB Output is correct
22 Correct 1 ms 1288 KB Output is correct
23 Correct 2 ms 1116 KB Output is correct
24 Correct 2 ms 1116 KB Output is correct
25 Correct 1 ms 1116 KB Output is correct
26 Correct 1 ms 1116 KB Output is correct
27 Correct 1 ms 1116 KB Output is correct
28 Correct 1 ms 1116 KB Output is correct
29 Incorrect 71 ms 14136 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1112 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 2 ms 1236 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 1 ms 1236 KB Output is correct
15 Correct 2 ms 1116 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 1 ms 1116 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Correct 2 ms 1368 KB Output is correct
20 Correct 1 ms 1116 KB Output is correct
21 Correct 1 ms 1156 KB Output is correct
22 Correct 1 ms 1288 KB Output is correct
23 Correct 2 ms 1116 KB Output is correct
24 Correct 2 ms 1116 KB Output is correct
25 Correct 1 ms 1116 KB Output is correct
26 Correct 1 ms 1116 KB Output is correct
27 Correct 1 ms 1116 KB Output is correct
28 Correct 1 ms 1116 KB Output is correct
29 Correct 11 ms 1368 KB Output is correct
30 Incorrect 5 ms 1412 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1112 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 2 ms 1236 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 1 ms 1236 KB Output is correct
15 Correct 2 ms 1116 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 1 ms 1116 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Correct 2 ms 1368 KB Output is correct
20 Correct 1 ms 1116 KB Output is correct
21 Correct 1 ms 1156 KB Output is correct
22 Correct 1 ms 1288 KB Output is correct
23 Correct 2 ms 1116 KB Output is correct
24 Correct 2 ms 1116 KB Output is correct
25 Correct 1 ms 1116 KB Output is correct
26 Correct 1 ms 1116 KB Output is correct
27 Correct 1 ms 1116 KB Output is correct
28 Correct 1 ms 1116 KB Output is correct
29 Correct 11 ms 1368 KB Output is correct
30 Incorrect 5 ms 1412 KB Output isn't correct
31 Halted 0 ms 0 KB -