| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 858680 |
2023-10-09T04:33:16 Z |
maks007 |
Joker (BOI20_joker) |
C++14 |
|
373 ms |
5596 KB |
#include "bits/stdc++.h"
using namespace std;
vector <int> p, rk;
int get(int v) {
if(v == p[v]) return v;
return p[v] = get(p[v]);
}
void unite(int a, int b) {
a = get(a);
b = get(b);
if(a == b) return;
if(rk[a] < rk[b]) swap(a, b);
rk[a] += rk[b];
p[b]=a;
}
signed main () {
int n, m, q;
cin >> n >> m >> q;
rk.resize(n);
p.resize(n);
for(int i = 0; i < n; i ++) rk[i]=1, p[i]=i;
vector <pair <int,int>> edge;
for(int i = 0; i < m; i ++) {
int u, v;
cin >> u >> v;
edge.push_back({u-1, v-1});
}
int suff[m+1];
suff[m] = 0;
for(int i = m - 1; i >= 0; i --) {
if(suff[i+1] == 0){
if(get(edge[i].first) == get(edge[i].second) && (rk[get(edge[i].first)] % 2== 1)) {
suff[i]=1;
continue;
}
suff[i]=0;
unite(edge[i].first, edge[i].second);
}else suff[i] = 1;
}
while(q --) {
int l, r;
cin >> l >> r;
l --, r --;
if(suff[r+1]) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
373 ms |
5596 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
