// Source: https://oj.uz/problem/view/IOI18_werewolf
//
#include "bits/stdc++.h"
using namespace std;
#define s second
#define f first
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<int> vi;
#define FOR(i, a, b) for (int i = (a); i<b; i++)
bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }
bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }
const int N = 2e5 + 10;
vpii adj[N];
vi p(N + 1, -1), id(N + 1);
int cnt = 0;
vector<vi> kadj(2 * N);
int get(int x) {
return (p[x] > 0) ? x = get(p[x]) : x;
}
void unite(int x, int y) {
x = get(x);
y = get(y);
if (x == y) return;
if (-p[x] < -p[y]) swap(x, y);
int here = cnt++;
kadj[here].pb(id[x]);
kadj[here].pb(id[y]);
// cout << x << y << ' ' << here << ' ' << id[x] << ' ' << id[y] << endl;
p[x] += p[y];
p[y] = x;
id[x] = here;
}
int tin = 0;
void dfs(int cur, vi &rep, vpii &range) {
// cout << cur << endl;
range[cur] = {5 * N, 0};
if (kadj[cur].size() == 0) {
rep[cur] = tin++;
range[cur] = {rep[cur], rep[cur]};
return;
}
for (auto val: kadj[cur]) {
dfs(val, rep, range);
ckmin(range[cur].f, range[val].f);
ckmax(range[cur].s, range[val].s);
}
}
void reorder(vi &rep, vpii &range, vector<vpii> &merge, vector<vpii> &need, vi &finalid) {
// need is what we need to update at each stage of merge
// final is the range for each
FOR(i, 0, N) {
p[i]=-1;
id[i]=i;
}
FOR(i, 0, 2 * N) kadj[i].clear();
cnt = N;
FOR(i, 0, merge.size()) {
for (auto val: merge[i]) {
// pii val = merge[i];
unite(val.f, val.s);
// cout <<i << ' ' << val.f << ' ' << val.s << endl;
}
for (auto val: need[i]) {
// cout << i << val.f << endl;
finalid[val.s] = id[get(val.f)];
}
}
tin = 0;
dfs(cnt-1, rep, range);
// FOR(i, 0, rep.size()) cout << rep[i] << endl;
}
vi bit(N + 1);
void update(int ind, int val) {
ind++;
for (; ind < N; ind += ind & -ind) bit[ind] += val;
}
int pref(int l) {
if (l < 0) return 0;
l++;
int res = 0;
for (; l > 0; l -= l & -l) res += bit[l];
return res;
}
int query(int l, int r) {
return pref(r) - pref(l - 1);
}
vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r) {
FOR(i, 0, x.size()) {
adj[max(x[i], y[i])].pb({x[i], y[i]});
}
vector<vpii> merge(n);
vector<vpii> need(n);
FOR(i, 0, r.size()) {
need[r[i]].pb({e[i], i});
}
FOR(i, 0, N) {
for (auto j: adj[i]) merge[i].pb(j);
}
vi rep1(n);
vpii range(2 * N + 1);
vi finalid(r.size());
reorder(rep1, range, merge, need, finalid);
vpii r1;
FOR(i, 0, finalid.size()) r1.pb(range[finalid[i]]);
vi rep2(n);
FOR(i, 0, n) merge[i].clear();
FOR(i, 0, n) merge[min(x[i], y[i])].pb({x[i], y[i]});
reverse(merge.begin(), merge.end());
FOR(i, 0, n) need[i].clear();
FOR(i, 0, l.size()) {
need[n-l[i]-1].pb({s[i], i});
}
reorder(rep2, range, merge, need, finalid);
vpii r2;
FOR(i, 0, finalid.size()) r2.pb(range[finalid[i]]);
vi in_range(e.size(), 0);
vector<vi> add(n);
vector<vpii> sweep(n);
FOR(i, 0, n) add[rep1[i]].pb(i);
FOR(i, 0, e.size()) {
if (r1[i].f) sweep[r1[i].f-1].pb({i, -1});
sweep[r1[i].s].pb({i, 1});
}
FOR(i, 0, n) {
for (auto val: add[i]) {
// cout << rep2[val] << endl;
update(rep2[val], 1);
}
for (auto val: sweep[i]) {
// cout << r2[val.f].f << ' ' << r2[val.f].s << ' ' << query(r2[val.f].f, r2[val.f].s) << endl;
in_range[val.f] += query(r2[val.f].f, r2[val.f].s) * val.s;
}
}
vi res;
FOR(i, 0, e.size()) res.pb(in_range[i] > 0);
// FOR(i, 0, n) cout << rep1[i] << ' ' << rep2[i] << endl;
// FOR(i, 0, e.size()) cout << r1[i].f << r1[i].s << ' ' << r2[i].f << r2[i].s << endl;
return res;
}
// int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// vi ans = check_validity(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2},
// {4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4});
// for (auto val: ans) cout << val << endl;
// }
Compilation message
werewolf.cpp: In function 'void reorder(vi&, vpii&, std::vector<std::vector<std::pair<int, int> > >&, std::vector<std::vector<std::pair<int, int> > >&, vi&)':
werewolf.cpp:19:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
87 | FOR(i, 0, merge.size()) {
| ~~~~~~~~~~~~~~~~~~
werewolf.cpp:87:2: note: in expansion of macro 'FOR'
87 | FOR(i, 0, merge.size()) {
| ^~~
werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:19:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
134 | FOR(i, 0, x.size()) {
| ~~~~~~~~~~~~~~
werewolf.cpp:134:2: note: in expansion of macro 'FOR'
134 | FOR(i, 0, x.size()) {
| ^~~
werewolf.cpp:19:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
141 | FOR(i, 0, r.size()) {
| ~~~~~~~~~~~~~~
werewolf.cpp:141:2: note: in expansion of macro 'FOR'
141 | FOR(i, 0, r.size()) {
| ^~~
werewolf.cpp:19:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
157 | FOR(i, 0, finalid.size()) r1.pb(range[finalid[i]]);
| ~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:157:2: note: in expansion of macro 'FOR'
157 | FOR(i, 0, finalid.size()) r1.pb(range[finalid[i]]);
| ^~~
werewolf.cpp:19:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
168 | FOR(i, 0, l.size()) {
| ~~~~~~~~~~~~~~
werewolf.cpp:168:2: note: in expansion of macro 'FOR'
168 | FOR(i, 0, l.size()) {
| ^~~
werewolf.cpp:19:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
175 | FOR(i, 0, finalid.size()) r2.pb(range[finalid[i]]);
| ~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:175:2: note: in expansion of macro 'FOR'
175 | FOR(i, 0, finalid.size()) r2.pb(range[finalid[i]]);
| ^~~
werewolf.cpp:19:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
185 | FOR(i, 0, e.size()) {
| ~~~~~~~~~~~~~~
werewolf.cpp:185:2: note: in expansion of macro 'FOR'
185 | FOR(i, 0, e.size()) {
| ^~~
werewolf.cpp:19:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
203 | FOR(i, 0, e.size()) res.pb(in_range[i] > 0);
| ~~~~~~~~~~~~~~
werewolf.cpp:203:2: note: in expansion of macro 'FOR'
203 | FOR(i, 0, e.size()) res.pb(in_range[i] > 0);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
20056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
20056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
314 ms |
90436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
20056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
