제출 #105916

#제출 시각아이디문제언어결과실행 시간메모리
105916Anai늑대인간 (IOI18_werewolf)C++14
0 / 100
1400 ms331400 KiB
#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 far[], int nod) { while (far[nod]) nod = far[nod]; return nod; } static bool join(int far[], int siz[], int a, int b) { int _up = min(a, b); a = get_far(far, a); b = get_far(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); auto &ref = mp[i][a]; ref = min(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(); } 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(far, siz, 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.left < b.left; }); 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) { magic_join(edgs[edg_ptr].x, edgs[edg_ptr].y); ++edg_ptr; } int halt = query.halt, start = dsu[query.start], dist = 2e9; while (halt) { auto it = mp[halt].find(start); if (it != end(mp[halt])) dist = min(dist, it->second); halt = far[halt]; } if (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]; fi >> 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 'bool magic_join(int, int)':
werewolf.cpp:60:22: warning: control reaches end of non-void function [-Wreturn-type]
  members[b].clear(); }
                      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...