제출 #100485

#제출 시각아이디문제언어결과실행 시간메모리
100485jeff늑대인간 (IOI18_werewolf)C++14
100 / 100
1265 ms100064 KiB
#include <bits/stdc++.h> #include "werewolf.h" using namespace std; int N, A[800000], id[400000], f[200000], l[2][2][400000], y, z; pair<int, int> B[800000]; vector<int> adj[2][400000], rs; vector<pair<int, int> > v; vector<tuple<int, int, int, int, int> > qr; inline int frt(int i) {return i == id[i] ? i : id[i] = frt(id[i]);} inline void ufds(int t, int a, int b) { a = frt(a); b = frt(b); if (a == b) return; adj[t][a].push_back(y); adj[t][b].push_back(y); adj[t][y].push_back(a); adj[t][y].push_back(b); id[a] = id[b] = y++; } void it(int t, int i, int o) { l[t][0][i] = z; for (int j = 0; j < adj[t][i].size(); ++j) if (o != adj[t][i][j]) it(t, adj[t][i][j], i); if (i < N) { if (!t) f[z++] = i; else ++z; } l[t][1][i] = z - 1; } void init(int i, int a, int b) { A[i] = INT_MAX; B[i] = make_pair(a, b); if (a >= b) return; init(i * 2, a, (a + b) / 2); init(i * 2 + 1, (a + b) / 2 + 1, b); } int q(int i, int a, int b) { if (b < B[i].first || B[i].second < a) return INT_MAX; if (a <= B[i].first && B[i].second <= b) return A[i]; return min(q(i * 2, a, b), q(i * 2 + 1, a, b)); } void u(int i, int p, int v) { if (p < B[i].first || B[i].second < p) return; if (p <= B[i].first && B[i].second <= p) {A[i] = v; return;} u(i * 2, p, v); u(i * 2 + 1, p, v); A[i] = min(A[i * 2], A[i * 2 + 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) { N = _N; int M = X.size(), Q = S.size(), i, j; rs.assign(Q, 0); for (i = 0; i < Q; ++i) qr.emplace_back(R[i], L[i], E[i], S[i], i); for (i = 0; i < M; ++i) v.emplace_back(max(X[i], Y[i]), min(X[i], Y[i])); sort(v.begin(), v.end()); sort(qr.begin(), qr.end()); iota(id, id + N * 2 - 1, 0); y = N; for (i = j = 0; i < M; ++i) { while (j < Q && get<0>(qr[j]) < v[i].first) get<2>(qr[j]) = frt(get<2>(qr[j])), swap(get<0>(qr[j]), get<1>(qr[j])), ++j; ufds(0, v[i].first, v[i].second); swap(v[i].first, v[i].second); } while (j < Q) get<3>(qr[j]) = frt(get<3>(qr[j])), swap(get<0>(qr[j]), get<1>(qr[j])), ++j; sort(v.begin(), v.end()); sort(qr.begin(), qr.end()); iota(id, id + N * 2 - 1, 0); y = N; for (i = M - 1, j = Q - 1; i > -1; --i) { while (j > -1 && get<0>(qr[j]) > v[i].first) get<3>(qr[j]) = frt(get<3>(qr[j])), --j; ufds(1, v[i].first, v[i].second); } while (j > -1) get<2>(qr[j]) = frt(get<2>(qr[j])), --j; it(0, N * 2 - 2, -1); z = 0; it(1, N * 2 - 2, -1); for (i = 0; i < Q; ++i) get<0>(qr[i]) = l[0][0][get<2>(qr[i])], get<1>(qr[i]) = l[0][1][get<2>(qr[i])]; sort(qr.begin(), qr.end()); init(1, 0, N - 1); for (i = Q - 1, j = N - 1; i > -1; --i) { while (j >= get<0>(qr[i])) u(1, l[1][0][f[j]], j), --j; rs[get<4>(qr[i])] = q(1, l[1][0][get<3>(qr[i])], l[1][1][get<3>(qr[i])]) <= get<1>(qr[i]); } return rs; }

컴파일 시 표준 에러 (stderr) 메시지

werewolf.cpp: In function 'void it(int, int, int)':
werewolf.cpp:26:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[t][i].size(); ++j) if (o != adj[t][i][j]) it(t, adj[t][i][j], i);
                     ~~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...