제출 #105936

#제출 시각아이디문제언어결과실행 시간메모리
105936Anai늑대인간 (IOI18_werewolf)C++14
0 / 100
3269 ms168804 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 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...