이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
struct Query {
int start, halt, left, right, idx; };
using pii = pair<int, int>;
const int N = 2e5 + 5;
vector<int> members[N];
map<int, int> dist[N];
int far[N], siz[N], dsu[N], up[N];
unordered_map<int, int> mp[N];
vector<Query> qs;
vector<pii> edgs;
int n, m, q;
static int get_far(int nod) {
while (far[nod])
nod = far[nod];
return nod; }
static bool join(int a, int b) {
int _up = min(a, b);
a = get_far(a);
b = get_far(b);
if (a == b)
return false;
if (siz[b] > siz[a])
swap(a, b);
far[b] = a;
up[b] = _up;
siz[a]+= siz[b];
return true; }
static bool magic_join(int a, int b) {
a = dsu[a];
b = dsu[b];
if (a == b)
return false;
if (members[b].size() > members[a].size())
swap(a, b);
for (auto i: members[b]) {
dsu[i] = a;
while (i != 0) {
auto it = mp[i].find(b);
if (it == end(mp[i]))
break;
auto &ref = mp[i][a];
ref = max(ref, it->second);
mp[i].erase(it);
i = far[i]; } }
members[a].insert(end(members[a]), begin(members[b]), end(members[b]));
members[b].clear();
return true; }
static void build_dsu() {
sort(begin(edgs), end(edgs), [&](const pii &a, const pii &b) {
return min(a.x, a.y) > min(b.x, b.y); });
for (const auto &e: edgs)
join(e.x, e.y);
for (int i = 1; i <= n; ++i) {
int dist = 2e9, nod = i;
while (nod) {
mp[nod][i] = dist;
dist = min(dist, up[nod]);
nod = far[nod]; } } }
static void initialize() {
fill(siz, siz + n + 1, 1);
for (int i = 1; i <= n; ++i) {
dsu[i] = i;
mp[i].max_load_factor(0.25);
members[i].push_back(i); } }
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
vector<int> ant;
int edg_ptr;
n = N;
q = S.size();
m = X.size();
qs.resize(q);
ant.resize(q);
edgs.resize(m);
for (int i = 0; i < m; ++i)
edgs[i] = {X[i] + 1, Y[i] + 1};
for (int i = 0; i < q; ++i)
qs[i] = {E[i] + 1, S[i] + 1, L[i] + 1, R[i] + 1, i};
initialize();
build_dsu();
sort(begin(qs), end(qs), [&](const Query &a, const Query &b) { return a.right < b.right; });
sort(begin(edgs), end(edgs), [&](const pii &a, const pii &b) {
return max(a.x, a.y) < max(b.x, b.y); });
edg_ptr = 0;
for (const auto &query: qs) {
while (edg_ptr < m && max(edgs[edg_ptr].x, edgs[edg_ptr].y) <= query.right) { // join things accessible in start form
magic_join(edgs[edg_ptr].x, edgs[edg_ptr].y);
++edg_ptr; }
int halt = query.halt, start = query.start, dist = 0;
while (halt) {
auto ith = mp[halt].find(dsu[query.halt]), its = mp[halt].find(dsu[query.start]);
if (ith != end(mp[halt]) && its != end(mp[halt]))
dist = max(dist, min(its->second, ith->second));
halt = far[halt]; }
if (dsu[query.start] == dsu[query.halt] || dist >= query.left)
ant[query.idx] = 1; }
return ant; }
#ifdef HOME
int main() {
ifstream fi("werewolf.in");
ofstream fo("werewolf.out");
int n, m, q;
fi >> n >> m >> q;
vector<int> x(m), y(m), s(q), e(q), l(q), r(q);
for (int j = 0; j < m; ++j)
fi >> x[j] >> y[j];
for (int i = 0; i < q; ++i)
fi >> s[i] >> e[i] >> l[i] >> r[i];
vector<int> ans = check_validity(n, x, y, s, e, l, r);
for (auto i: ans)
fo << i << '\n';
return 0; }
#endif
컴파일 시 표준 에러 (stderr) 메시지
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:115:26: warning: unused variable 'start' [-Wunused-variable]
int halt = query.halt, start = query.start, dist = 0;
^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |