| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 896813 |
2024-01-02T08:34:23 Z |
Nelt |
Werewolf (IOI18_werewolf) |
C++17 |
|
330 ms |
196040 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(pp(ll, ll)) st[N << 1];
vv(ll) pref[N << 1];
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]));
pref[i].resize(st[i].size());
pref[i][0] = st[i][0].S;
for (ll j = 1; j < st[i].size(); j++)
pref[i][j] = max(pref[i][j - 1], st[i][j].S);
}
}
bool 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)
{
pos = upper_bound(allc(st[l]), mpr(r1, INF)) - st[l].begin() - 1;
if (pos >= 0 and pos < st[l].size() and pref[l][pos] >= l1)
return true;
l++;
}
if (r & 1)
{
r--;
pos = upper_bound(allc(st[r]), mpr(r1, INF)) - st[r].begin() - 1;
if (pos >= 0 and pos < st[r].size() and pref[r][pos] >= l1)
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] = {mpr(-INF, INF)};
for (ll i = 1; i <= n; i++)
st[d[i] + sz - 1] = {mpr(f1[i], 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 'void build()':
werewolf.cpp:103:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for (ll j = 1; j < st[i].size(); j++)
| ~~^~~~~~~~~~~~~~
werewolf.cpp: In function 'bool query(long long int, long long int, long long int, long long int)':
werewolf.cpp:115:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | if (pos >= 0 and pos < st[l].size() and pref[l][pos] >= l1)
| ~~~~^~~~~~~~~~~~~~
werewolf.cpp:123:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | if (pos >= 0 and pos < st[r].size() and pref[r][pos] >= l1)
| ~~~~^~~~~~~~~~~~~~
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:148:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | for (ll i = 0; i < X.size(); i++)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
43 ms |
89532 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
43 ms |
89532 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
330 ms |
196040 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
43 ms |
89532 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
