Submission #930587

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
930587	2024-02-20T07:30:01 Z	UmairAhmadMirza	Joker (BOI20_joker)	C++17	25 / 100	429 ms	22976 KB

Joker

#include <bits/stdc++.h>
using namespace std;
int const N=2e5+5;
vector<int> adj[N];
bool dep[N];
int rep[N];
vector<int> com[N];
// int dp[N][N];
bool merge(int a,int b){
  int ra=a;
  int rb=b;
  a=rep[a];
  b=rep[b];
  // cout<<ra<<' '<<rb<<endl;
  if(a==b){
    if(dep[ra]==dep[rb])
      return 0;
    return 1;
  }
  if(com[a].size()>com[b].size()){
    swap(a,b);
    swap(ra,rb);
  }
  bool sw=0;
  if(dep[ra]==dep[rb])
    sw=1;
  for(auto i:com[a]){
    com[b].push_back(i);
    rep[i]=b;
    dep[i]^=sw;
  }
  com[a].clear();
  return 1;
}
int main() 
{
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
      com[i].push_back(i);
      rep[i]=i;
    }
    vector<pair<int,int>> edge;
    for(int i=0;i<m;i++){
      int a,b;
      cin>>a>>b;
      if(a>b)
        swap(a,b);
      edge.push_back({a,b});
    }
    int k=m;
    reverse(edge.begin(),edge.end());
    for(auto e:edge){
      k--;
      // cout<<"Include := "<<node<<endl;
      if(merge(e.first,e.second)==0)
        break;
    }
    // cout<<k<<endl;
    // cout<<k<<endl;
    for(int i=0;i<q;i++){
      int l,r;
      cin>>l>>r;
      if(r<=k)
        cout<<"YES"<<endl;
      else
        cout<<"NO"<<endl;
    }
    return 0;
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	10588 KB	Output is correct
2	Correct	3 ms	10588 KB	Output is correct
3	Incorrect	4 ms	10588 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	4 ms	10588 KB	Output is correct
2	Correct	3 ms	10588 KB	Output is correct
3	Correct	391 ms	17308 KB	Output is correct
4	Correct	408 ms	22976 KB	Output is correct
5	Correct	399 ms	20936 KB	Output is correct
6	Correct	429 ms	19308 KB	Output is correct
7	Correct	399 ms	20384 KB	Output is correct
8	Correct	374 ms	17440 KB	Output is correct
9	Correct	382 ms	19540 KB	Output is correct
10	Correct	393 ms	22128 KB	Output is correct
11	Correct	405 ms	18992 KB	Output is correct
12	Correct	401 ms	21388 KB	Output is correct
13	Correct	377 ms	16068 KB	Output is correct
14	Correct	400 ms	17848 KB	Output is correct
15	Correct	403 ms	20996 KB	Output is correct
16	Correct	419 ms	22228 KB	Output is correct