| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 858776 |
2023-10-09T07:39:28 Z |
maks007 |
Joker (BOI20_joker) |
C++14 |
|
379 ms |
10176 KB |
#include "bits/stdc++.h"
using namespace std;
vector <vector <int> > g;
vector <int> used, rk, p;
int f;
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;
rk[a] += rk[b];
p[b] = a;
}
void dfs(int v, int dist = 1, int p = -1) {
used[v] = dist;
for(auto i : g[v]) {
if(p == i) continue;
if(used[i]==-1) dfs(i, (dist+1)%2, v);
else {
if(used[i] == used[v]) f = 1;
}
}
}
void renname(int v, int p) {
used[v] = 1-used[v];
for(auto i : g[v]) {
if(i == p) continue;
renname(i, v);
}
}
void d(int v, int u) {
if(used[v] + used[u] == -2) {
used[v] = 1;
used[u] = 0;
}else if(used[v] == -1 || used[u] == -1) {
int nul = 0, one = 0;
if(used[u] == -1) swap(u, v);
for(auto i : g[v]) {
if(used[i] == 1) one ++;
else nul ++;
}
if(one == 0) used[v] = 1;
else if(nul == 0) used[v] = 0;
else {
used[v] = 1;
f = 1;
}
}else {
if(used[v] == used[u] && get(u) == get(v)) f = 1;
else {
dfs(v);
}
return;
}
}
signed main () {
int n, m, q;
cin >> n >> m >> q;
g.resize(n);
used.resize(n, -1);
rk.resize(n, 1);
p.resize(n);
for(int i = 0; i < n; i ++) 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});
}
vector <int> suff(m + 1);
suff[m] = 0;
for(int i = m - 1; i >= 0; i --) {
if(suff[i+1] == 1) {
suff[i] = suff[i+1];
continue;
}
g[edge[i].first].push_back(edge[i].second);
g[edge[i].second].push_back(edge[i].first);
unite(edge[i].first, edge[i].second);
f = 0;
d(edge[i].first, edge[i].second);
if(f) suff[i] = 1;
else suff[i] = 0;
}
while(q --) {
int l, r;
cin >> l >> r;
l --, r --;
if(l == 0) {
if(suff[r+1] == 1) cout << "YES\n";
else cout << "NO\n";
continue;
}
for(auto &i : g) i.clear();
for(auto &i : used) i = -1;
for(int i = 0; i < l; i ++) {
g[edge[i].first].push_back(edge[i].second);
g[edge[i].second].push_back(edge[i].first);
}
for(int i = r+1; i < m; i ++) {
g[edge[i].first].push_back(edge[i].second);
g[edge[i].second].push_back(edge[i].first);
}
for(int i = 0; i < n; i ++) {
if(used[i]==-1) {
f = 0;
dfs(i);
if(f) {
cout << "YES\n";
goto end;
}
}
}
cout << "NO\n";
end:;
}
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 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
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 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
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 |
379 ms |
10176 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 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
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 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
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 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
