| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 877011 |
2023-11-22T17:08:35 Z |
fanwen |
Joker (BOI20_joker) |
C++17 |
|
24 ms |
46412 KB |
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define file(name) \
if(fopen(name".inp", "r")) \
freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \
const int MAX = 5e5 + 5;
struct Edge {
int u, v;
int get(int x) {
return x ^ u ^ v;
}
} e[MAX];
int n, m, q;
vector <int> adj[MAX];
namespace sub1 {
bool check() {
return max({n, m, q}) <= 5000;
}
int dd[MAX];
bool solve(int l, int r) {
fill(dd + 1, dd + n + 1, -1);
bool ans = true;
function <void(int, int)>
dfs = [&] (int u, int c) {
dd[u] = c;
for (int i : adj[u]) if(i < l || i > r) {
int v = e[i].get(u);
if(dd[v] == -1) {
dfs(v, 1 ^ c);
} else {
if(c == dd[v]) {
ans = false;
}
}
}
};
for (int u = 1; u <= n; ++u) if(dd[u] == -1) {
dfs(u, 0);
}
return ans;
}
void solve() {
while(q--) {
int l, r; cin >> l >> r;
cout << (solve(l, r) ? "NO" : "YES") << '\n';
}
exit(0);
}
}
struct Query {
int l, r, id;
} queries[MAX];
int ans[MAX];
namespace sub2 {
bool check() {
for (int i = 1; i <= q; ++i) {
if(queries[i].l != 1) {
return false;
}
}
return true;
}
int rank[MAX];
pair <int, int> par[MAX];
bool bipartite[MAX];
void make_set(int v) {
par[v] = make_pair(v, 0);
rank[v] = 0;
bipartite[v] = true;
}
pair <int, int> find_set(int u) {
if(u != par[u].fi) {
int parity = par[u].se;
par[u] = find_set(par[u].fi);
par[u].se ^= parity;
}
return par[u];
}
bool total = true;
bool merge(int a, int b) {
pair <int, int> pa = find_set(a); a = pa.fi; int x = pa.se;
pair <int, int> pb = find_set(b); b = pb.fi; int y = pb.se;
if(a == b) {
if(x == y) {
bipartite[a] = false;
total = false;
}
return false;
}
if(rank[a] < rank[b]) swap(a, b);
par[b] = make_pair(a, 1 ^ x ^ y);
bipartite[a] &= bipartite[b];
if(rank[a] == rank[b]) rank[a]++;
return true;
}
void solve() {
sort(queries + 1, queries + q + 1, [&] (const Query &a, const Query &b) {
return a.r > b.r;
});
int j = m;
for (int i = 1; i <= n; ++i) make_set(i);
for (int i = 1; i <= q; ++i) {
while(j >= 1 && j > queries[i].r) {
merge(e[j].u, e[j].v);
j--;
}
ans[queries[i].id] = total;
}
for (int i = 1; i <= q; ++i) {
cout << (ans[i] ? "NO" : "YES") << '\n';
}
exit(0);
}
}
namespace sub3 {
bool check() {
return true;
}
struct save {
int u, v, ranku, rankv, cnt;
};
vector <save> tmp;
int lab[MAX], wei[MAX], dp[MAX];
int find(int u) {
return lab[u] < 0 ? u : find(lab[u]);
}
int get_w(int u) {
return lab[u] < 0 ? 0 : wei[u] ^ get_w(lab[u]);
}
bool merge(int u, int v, int cnt) {
int w = 1 ^ get_w(u) ^ get_w(v);
u = find(u), v = find(v);
assert(u != 0 && v != 0);
if(u == v) {
return w == 0;
}
if(lab[u] > lab[v]) swap(u, v);
tmp.push_back({u, v, lab[u], lab[v], cnt});
lab[u] += lab[v];
lab[v] = u;
wei[v] = w;
return true;
}
void rollback(int l, int r) {
if(l > r) return;
while(!tmp.empty() && tmp.back().cnt >= l && tmp.back().cnt <= r) {
auto [u, v, labu, labv, _] = tmp.back(); tmp.pop_back();
lab[u] = labu, lab[v] = labv;
wei[v] = 0;
}
}
void dnc(int l, int r, int optL, int optR) {
if(l > r) return;
int mid = l + r >> 1;
for (int i = l; i < mid; i++) {
merge(e[i].u, e[i].v, i);
}
int optM = -1;
for (int i = optR; i >= max(optL, mid); --i) {
if(!merge(e[i].u, e[i].v, i)) {
optM = i + 1;
break;
}
}
optM = min(m, optM);
dp[mid] = optM;
rollback(optM, optR);
merge(e[mid].u, e[mid].v, mid);
dnc(mid + 1, r, optM, optR);
rollback(l, mid);
for (int i = optM + 1; i <= optR; ++i) {
merge(e[i].u, e[i].v, i);
}
dnc(l, mid - 1, optL, optM);
rollback(optM + 1, optR);
}
void solve() {
memset(lab, -1, sizeof lab);
dnc(1, m, 1, m);
for (int i = 1; i <= q; ++i) {
int l = queries[i].l, r = queries[i].r;
cout << (dp[l] > r ? "YES" : "NO") << '\n';
}
}
}
void you_make_it(void) {
cin >> n >> m >> q;
for (int i = 1; i <= m; ++i) {
cin >> e[i].u >> e[i].v;
adj[e[i].u].push_back(i);
adj[e[i].v].push_back(i);
}
// if(sub1::check()) sub1::solve();
for (int i = 1; i <= q; ++i) cin >> queries[i].l >> queries[i].r, queries[i].id = i;
if(sub3::check()) sub3::solve();
}
signed main() {
#ifdef LOCAL
freopen("TASK.inp", "r", stdin);
freopen("TASK.out", "w", stdout);
#endif
file("joker");
auto start_time = chrono::steady_clock::now();
cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
you_make_it();
auto end_time = chrono::steady_clock::now();
cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;
return (0 ^ 0);
}
// Dream it. Wish it. Do it.
Compilation message
Joker.cpp: In function 'void sub3::dnc(int, int, int, int)':
Joker.cpp:192:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
192 | int mid = l + r >> 1;
| ~~^~~
Joker.cpp: In function 'int main()':
Joker.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
10 | freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:250:5: note: in expansion of macro 'file'
250 | file("joker");
| ^~~~
Joker.cpp:10:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
10 | freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:250:5: note: in expansion of macro 'file'
250 | file("joker");
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
46412 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
46412 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
46412 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
46412 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
46412 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
46412 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
