# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
896696 |
2024-01-01T21:45:55 Z |
Nelt |
Werewolf (IOI18_werewolf) |
C++17 |
|
864 ms |
192244 KB |
#include "werewolf.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/* DEFINES */
#define S second
#define F first
#define ll long long
#define ull unsigned long long
#define ld long double
#define npos ULLONG_MAX
#define INF LLONG_MAX
#define vv(a) vector<a>
#define pp(a, b) pair<a, b>
#define pq(a) priority_queue<a>
#define qq(a) queue<a>
#define ss(a) set<a>
#define mm(a, b) map<a, b>
#define ump(a, b) unordered_map<a, b>
#define ANDROID \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define elif else if
#define endl "\n"
#define allc(a) begin(a), end(a)
#define all(a) a, a + sizeof(a) / sizeof(a[0])
#define pb push_back
#define logi(a) __lg(a)
#define sqrt(a) sqrtl(a)
#define mpr make_pair
#define ins insert
using namespace std;
using namespace __gnu_pbds;
using namespace __cxx11;
typedef char chr;
typedef basic_string<chr> str;
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 2e5 + 5;
vv(ll) sufg[N], prefg[N], adj[N], adj1[N];
ll d[N], d1[N], f[N], f1[N];
struct Dsu
{
ll n, ans;
vv(ll) dsu;
Dsu(ll sz = 1)
{
n = sz;
ans = n;
dsu.resize(n + 1, 0);
init();
}
void init()
{
for (ll i = 1; i <= n; i++)
dsu[i] = -1;
}
bool Union(ll x, ll y, bool flg)
{
x = repr(x), y = repr(y);
if (x == y)
return false;
if (flg and (x > y))
swap(x, y);
if (!flg and (x < y))
swap(x, y);
ans--;
dsu[y] += dsu[x];
dsu[x] = y;
return true;
}
ll repr(ll x)
{
if (dsu[x] < 0)
return x;
return dsu[x] = repr(dsu[x]);
}
ll query()
{
return ans;
}
ll size(ll x)
{
return -dsu[repr(x)];
}
};
vv(ll) st[N << 2];
ll sz;
void build()
{
for (ll i = sz - 1; i >= 1; i--)
merge(allc(st[i << 1]), allc(st[i << 1 | 1]), back_inserter(st[i]));
}
int query(ll l, ll r, ll l1, ll r1)
{
ll pos;
for (l += sz - 1, r += sz; l < r; l >>= 1, r >>= 1)
{
if (l & 1)
{
if (upper_bound(allc(st[l]), r1) - lower_bound(allc(st[l]), l1) > 0)
return true;
l++;
}
if (r & 1)
{
r--;
if (upper_bound(allc(st[r]), r1) - lower_bound(allc(st[r]), l1) > 0)
return true;
}
}
return false;
}
ll timer = 1;
void prefdfs(ll v)
{
d[v] = timer++;
for (ll to : prefg[v])
prefdfs(to);
f[v] = timer++;
}
void sufdfs(ll v)
{
d1[v] = timer++;
for (ll to : sufg[v])
sufdfs(to);
f1[v] = timer++;
}
std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y, std::vector<int> St, std::vector<int> E, std::vector<int> L, std::vector<int> R)
{
sz = (n << 1);
ll q = St.size();
for (ll i = 0; i < X.size(); i++)
X[i]++, Y[i]++, adj[min(X[i], Y[i])].pb(max(X[i], Y[i])), adj1[max(X[i], Y[i])].pb(min(X[i], Y[i]));
vv(pp(ll, ll)) sufproc[n + 1], prefproc[n + 1];
ll sufrep[q], prefrep[q];
for (ll i = 0; i < q; i++)
St[i]++, E[i]++, L[i]++, R[i]++, sufproc[L[i]].pb(mpr(St[i], i)), prefproc[R[i]].pb(mpr(E[i], i));
Dsu dsu(n);
for (ll i = 1; i <= n; i++)
{
for (ll j : adj1[i])
if (i != dsu.repr(j))
{
prefg[i].pb(dsu.repr(j));
dsu.Union(i, j, true);
}
for (auto [j, ind] : prefproc[i])
prefrep[ind] = dsu.repr(j);
}
dsu = Dsu(n);
for (ll i = n; i >= 1; i--)
{
for (ll j : adj[i])
if (i != dsu.repr(j))
{
sufg[i].pb(dsu.repr(j));
dsu.Union(i, j, false);
}
for (auto [j, ind] : sufproc[i])
sufrep[ind] = dsu.repr(j);
}
timer = 1;
prefdfs(n);
timer = 1;
sufdfs(1);
for (ll i = sz; i < (sz << 1); i++)
st[i] = {INF};
for (ll i = 1; i <= n; i++)
st[d[i] + sz - 1] = {d1[i]};
build();
// cout << "OK\n";
vv(int) ans;
// for (ll i = 0; i < q; i++)
// cout << d1[sufrep[i]] << " " << f1[sufrep[i]] << endl;
for (ll i = 0; i < q; i++)
ans.pb(query(d[prefrep[i]], f[prefrep[i]], d1[sufrep[i]], f1[sufrep[i]]));
return ans;
}
Compilation message
werewolf.cpp: In function 'int query(long long int, long long int, long long int, long long int)':
werewolf.cpp:102:8: warning: unused variable 'pos' [-Wunused-variable]
102 | ll pos;
| ^~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:139:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | for (ll i = 0; i < X.size(); i++)
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
44124 KB |
Output is correct |
2 |
Correct |
11 ms |
44216 KB |
Output is correct |
3 |
Correct |
11 ms |
44312 KB |
Output is correct |
4 |
Correct |
9 ms |
44124 KB |
Output is correct |
5 |
Correct |
11 ms |
44120 KB |
Output is correct |
6 |
Correct |
9 ms |
44124 KB |
Output is correct |
7 |
Correct |
9 ms |
44120 KB |
Output is correct |
8 |
Correct |
10 ms |
44124 KB |
Output is correct |
9 |
Correct |
10 ms |
44124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
44124 KB |
Output is correct |
2 |
Correct |
11 ms |
44216 KB |
Output is correct |
3 |
Correct |
11 ms |
44312 KB |
Output is correct |
4 |
Correct |
9 ms |
44124 KB |
Output is correct |
5 |
Correct |
11 ms |
44120 KB |
Output is correct |
6 |
Correct |
9 ms |
44124 KB |
Output is correct |
7 |
Correct |
9 ms |
44120 KB |
Output is correct |
8 |
Correct |
10 ms |
44124 KB |
Output is correct |
9 |
Correct |
10 ms |
44124 KB |
Output is correct |
10 |
Correct |
15 ms |
46168 KB |
Output is correct |
11 |
Correct |
14 ms |
45916 KB |
Output is correct |
12 |
Correct |
17 ms |
46320 KB |
Output is correct |
13 |
Correct |
15 ms |
46172 KB |
Output is correct |
14 |
Correct |
16 ms |
46076 KB |
Output is correct |
15 |
Correct |
15 ms |
46172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
557 ms |
179768 KB |
Output is correct |
2 |
Correct |
440 ms |
183604 KB |
Output is correct |
3 |
Correct |
436 ms |
180092 KB |
Output is correct |
4 |
Correct |
558 ms |
181304 KB |
Output is correct |
5 |
Correct |
609 ms |
180464 KB |
Output is correct |
6 |
Correct |
671 ms |
180144 KB |
Output is correct |
7 |
Correct |
497 ms |
176696 KB |
Output is correct |
8 |
Correct |
429 ms |
183860 KB |
Output is correct |
9 |
Correct |
474 ms |
179960 KB |
Output is correct |
10 |
Correct |
403 ms |
178572 KB |
Output is correct |
11 |
Correct |
413 ms |
180536 KB |
Output is correct |
12 |
Correct |
564 ms |
181040 KB |
Output is correct |
13 |
Correct |
551 ms |
191536 KB |
Output is correct |
14 |
Correct |
579 ms |
191028 KB |
Output is correct |
15 |
Correct |
560 ms |
190888 KB |
Output is correct |
16 |
Correct |
558 ms |
190904 KB |
Output is correct |
17 |
Correct |
492 ms |
177448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
44124 KB |
Output is correct |
2 |
Correct |
11 ms |
44216 KB |
Output is correct |
3 |
Correct |
11 ms |
44312 KB |
Output is correct |
4 |
Correct |
9 ms |
44124 KB |
Output is correct |
5 |
Correct |
11 ms |
44120 KB |
Output is correct |
6 |
Correct |
9 ms |
44124 KB |
Output is correct |
7 |
Correct |
9 ms |
44120 KB |
Output is correct |
8 |
Correct |
10 ms |
44124 KB |
Output is correct |
9 |
Correct |
10 ms |
44124 KB |
Output is correct |
10 |
Correct |
15 ms |
46168 KB |
Output is correct |
11 |
Correct |
14 ms |
45916 KB |
Output is correct |
12 |
Correct |
17 ms |
46320 KB |
Output is correct |
13 |
Correct |
15 ms |
46172 KB |
Output is correct |
14 |
Correct |
16 ms |
46076 KB |
Output is correct |
15 |
Correct |
15 ms |
46172 KB |
Output is correct |
16 |
Correct |
557 ms |
179768 KB |
Output is correct |
17 |
Correct |
440 ms |
183604 KB |
Output is correct |
18 |
Correct |
436 ms |
180092 KB |
Output is correct |
19 |
Correct |
558 ms |
181304 KB |
Output is correct |
20 |
Correct |
609 ms |
180464 KB |
Output is correct |
21 |
Correct |
671 ms |
180144 KB |
Output is correct |
22 |
Correct |
497 ms |
176696 KB |
Output is correct |
23 |
Correct |
429 ms |
183860 KB |
Output is correct |
24 |
Correct |
474 ms |
179960 KB |
Output is correct |
25 |
Correct |
403 ms |
178572 KB |
Output is correct |
26 |
Correct |
413 ms |
180536 KB |
Output is correct |
27 |
Correct |
564 ms |
181040 KB |
Output is correct |
28 |
Correct |
551 ms |
191536 KB |
Output is correct |
29 |
Correct |
579 ms |
191028 KB |
Output is correct |
30 |
Correct |
560 ms |
190888 KB |
Output is correct |
31 |
Correct |
558 ms |
190904 KB |
Output is correct |
32 |
Correct |
492 ms |
177448 KB |
Output is correct |
33 |
Correct |
658 ms |
180272 KB |
Output is correct |
34 |
Correct |
195 ms |
85764 KB |
Output is correct |
35 |
Correct |
640 ms |
184024 KB |
Output is correct |
36 |
Correct |
626 ms |
180408 KB |
Output is correct |
37 |
Correct |
664 ms |
183900 KB |
Output is correct |
38 |
Correct |
654 ms |
181572 KB |
Output is correct |
39 |
Correct |
864 ms |
189148 KB |
Output is correct |
40 |
Correct |
604 ms |
189548 KB |
Output is correct |
41 |
Correct |
555 ms |
181816 KB |
Output is correct |
42 |
Correct |
406 ms |
179096 KB |
Output is correct |
43 |
Correct |
581 ms |
189636 KB |
Output is correct |
44 |
Correct |
625 ms |
182132 KB |
Output is correct |
45 |
Correct |
556 ms |
189804 KB |
Output is correct |
46 |
Correct |
444 ms |
188728 KB |
Output is correct |
47 |
Correct |
574 ms |
191288 KB |
Output is correct |
48 |
Correct |
542 ms |
191796 KB |
Output is correct |
49 |
Correct |
546 ms |
192056 KB |
Output is correct |
50 |
Correct |
564 ms |
192244 KB |
Output is correct |
51 |
Correct |
586 ms |
189788 KB |
Output is correct |
52 |
Correct |
529 ms |
190264 KB |
Output is correct |