| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 896629 |
2024-01-01T19:23:44 Z |
aykhn |
Werewolf (IOI18_werewolf) |
C++17 |
|
950 ms |
318404 KB |
#include "werewolf.h"
#include <bits/stdc++.h>
// author : aykhn
using namespace std;
typedef long long ll;
#define pb push_back
#define ins insert
#define mpr make_pair
#define all(v) v.begin(), v.end()
#define bpc __builtin_popcount
#define bpcll __builtin_popcountll
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define infll 0x3F3F3F3F3F3F3F3F
#define inf 0x3F3F3F3F
struct SegTree
{
int sz = 1;
vector<int> st;
void init(int n)
{
while (sz < n) sz <<= 1;
st.assign(sz << 1, 0);
}
void add(int l, int r, int x, int ind)
{
if (l + 1 == r)
{
st[x]++;
return;
}
int mid = (l + r) >> 1;
if (ind < mid) add(l, mid, 2*x + 1, ind);
else add(mid, r, 2*x + 2, ind);
st[x] = st[2*x + 1] + st[2*x + 2];
}
int get(int l, int r, int x, int lx, int rx)
{
if (l >= rx || r <= lx) return 0;
if (l >= lx && r <= rx) return st[x];
int mid = (l + r) >> 1;
return get(l, mid, 2*x + 1, lx, rx) + get(mid, r, 2*x + 2, lx, rx);
}
};
const int MXN = 1e6 + 6;
const int LOG = 20;
int nh, nw;
vector<int> hum[MXN], wol[MXN];
int eh[MXN], ew[MXN];
int ph[LOG][MXN], pw[LOG][MXN];
int whenh[MXN], whenw[MXN];
array<int, 2> rh[MXN], rw[MXN];
int idh[MXN], idw[MXN], revh[MXN], revw[MXN];
int tim;
int ans[MXN];
vector<array<int, 3>> qin[MXN], qout[MXN];
SegTree st;
void reset()
{
for (int i = 0; i < MXN; i++)
{
eh[i] = ew[i] = -1;
rh[i][0] = rw[i][0] = inf;
rh[i][1] = rw[i][1] = -inf;
wol[i].clear();
hum[i].clear();
}
}
int geth(int x)
{
if (eh[x] < 0) return x;
return eh[x] = geth(eh[x]);
}
void uniteh(int x, int y)
{
int val = min(x, y);
x = geth(x);
y = geth(y);
if (x == y) return;
whenh[nh] = val;
hum[nh].pb(x);
hum[nh].pb(y);
eh[nh] = eh[x] + eh[y];
eh[x] = eh[y] = nh;
nh++;
}
void dfsh(int a)
{
if (hum[a].empty())
{
idh[a] = ++tim;
revh[tim] = a;
rh[a][0] = rh[a][1] = idh[a];
return;
}
for (int v : hum[a])
{
ph[0][v] = a;
dfsh(v);
rh[a][0] = min(rh[a][0], rh[v][0]);
rh[a][1] = max(rh[a][1], rh[v][1]);
}
}
int getw(int x)
{
if (ew[x] < 0) return x;
return ew[x] = getw(ew[x]);
}
void unitew(int x, int y)
{
int val = max(x, y);
x = getw(x);
y = getw(y);
if (x == y) return;
whenw[nw] = val;
wol[nw].pb(x);
wol[nw].pb(y);
ew[nw] = ew[x] + ew[y];
ew[x] = ew[y] = nw;
nw++;
}
void dfsw(int a)
{
if (wol[a].empty())
{
idw[a] = ++tim;
revw[tim] = a;
rw[a][0] = rw[a][1] = idw[a];
return;
}
for (int v : wol[a])
{
pw[0][v] = a;
dfsw(v);
rw[a][0] = min(rw[a][0], rw[v][0]);
rw[a][1] = max(rw[a][1], rw[v][1]);
}
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R)
{
reset();
nh = nw = N;
vector<array<int, 2>> edges;
for (int i = 0; i < X.size(); i++) edges.pb({min(X[i], Y[i]), max(X[i], Y[i])});
sort(all(edges), [&](const array<int, 2> &a, const array<int, 2> &b)
{
return a[0] > b[0];
});
for (const array<int, 2> a : edges) uniteh(a[0], a[1]);
sort(all(edges), [&](const array<int, 2> &a, const array<int, 2> &b)
{
return a[1] < b[1];
});
for (const array<int, 2> a : edges) unitew(a[0], a[1]);
tim = -1;
ph[0][nh - 1] = nh - 1;
dfsh(nh - 1);
tim = -1;
pw[0][nw - 1] = nw - 1;
dfsw(nw - 1);
for (int i = 1; i < LOG; i++) for (int j = 0; j < nh; j++) ph[i][j] = ph[i - 1][ph[i - 1][j]], pw[i][j] = pw[i - 1][pw[i - 1][j]];
int Q = S.size();
for (int i = 0; i < Q; i++)
{
int u = S[i], v = E[i], l = L[i], r = R[i];
for (int j = LOG - 1; j >= 0; j--)
{
if (whenh[ph[j][u]] >= l) u = ph[j][u];
if (whenw[pw[j][v]] <= r) v = pw[j][v];
}
qin[rh[u][0]].pb({rw[v][0], rw[v][1], i});
qout[rh[u][1]].pb({rw[v][0], rw[v][1], i});
}
st.init(nh);
for (int i = 0; i < nh; i++)
{
st.add(0, st.sz, 0, idw[revh[i]]);
for (const array<int, 3> a : qin[i]) ans[a[2]] = st.get(0, st.sz, 0, a[0], a[1] + 1);
for (const array<int, 3> a : qout[i]) ans[a[2]] = (st.get(0, st.sz, 0, a[0], a[1] + 1) > ans[a[2]] ? 1 : 0);
}
vector<int> res;
for (int i = 0; i < Q; i++) res.pb(ans[i]);
return res;
}
Compilation message
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:154:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | for (int i = 0; i < X.size(); i++) edges.pb({min(X[i], Y[i]), max(X[i], Y[i])});
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
211284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
211284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
950 ms |
318404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
211284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
