# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1015132 | deera | Werewolf (IOI18_werewolf) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
deque<int> line;
int NUM;
map<int, vector<int>> roads;
vector<int> minT;
vector<int> maxT;
void build_minT(int n) {
if (n >= NUM) {
minT[n] = line[n - NUM];
return;
} else {
build_minT(2 * n);
build_minT(2 * n + 1);
minT[n] = min(minT[2 * n], minT[2 * n + 1]);
}
}
int query_minT(int a, int b) {
if (a == b) return minT[a + NUM];
if (a > b) return INT_MAX;
a += NUM;
b += NUM;
int res = INT_MAX;
while (a <= b) {
if (a % 2 == 1) {
res = min(res, minT[a]);
a++;
}
if (b % 2 == 0) {
res = min(res, minT[b]);
b--;
}
a /= 2;
b /= 2;
}
return res;
}
void build_maxT(int n) {
if (n >= NUM) {
maxT[n] = line[n - NUM];
return;
} else {
build_maxT(2 * n);
build_maxT(2 * n + 1);
maxT[n] = max(maxT[2 * n], maxT[2 * n + 1]);
}
}
int query_maxT(int a, int b) {
if (a == b) return maxT[a + NUM];
if (a > b) return INT_MIN;
a += NUM;
b += NUM;
int res = INT_MIN;
while (a <= b) {
if (a % 2 == 1) {
res = max(res, maxT[a]);
a++;
}
if (b % 2 == 0) {
res = max(res, maxT[b]);
b--;
}
a /= 2;
b /= 2;
}
return res;
}
void make_line(bool x) {
if (x == true) {
int last = line.back();
vector<int> a = roads[last];
if (a.size() == 1) {
if (a[0] != line[line.size() - 2]) {
line.push_back(a[0]);
}
make_line(false);
} else {
if (a[0] == line[line.size() - 2]) {
line.push_back(a[1]);
make_line(true);
} else {
line.push_back(a[0]);
make_line(true);
}
}
} else {
int last = line.front();
vector<int> a = roads[last];
if (a.size() == 1) {
line.push_front(a[0]);
return;
} else {
if (a[0] == line[1]) {
line.push_back(a[1]);
make_line(false);
} else {
line.push_back(a[0]);
make_line(false);
}
}
}
}
int[] check_validity(int N, int[] X, int[] Y, int[] S, int[] E, int[] L, int[] R) {
NUM = N;
for(int i=1;i<=N;i++) {
vector<int> a;
roads[i] = a;
}
for(int i=0;i<X.size();i++) {
roads[X[i]].push_back(Y[i]);
roads[Y[i]].push_back(X[i]);
}
for (auto i: roads) {
if (i.second.size() == 1) {
line.push_back(i.first);
line.push_back(i.second[0]);
break;
}
}
while (true) {
vector<int> next = roads[line.back()];
if (next.size() == 1) {
break;
} else {
if (next[0] == line[line.size() - 2]) {
line.push_back(next[1]);
} else {
line.push_back(next[0]);
}
}
}
minT.resize(2 * NUM);
maxT.resize(2 * NUM);
build_minT(1);
build_maxT(1);
vector<int> ans;
for(int q=0;q<S.size();q++) {
int s = S[q];
int e = E[q];
int l = L[q];
int r = R[q];
int mid = (s + e) / 2;
while (true) {
if (s >= e) {
ans.push_back(1);
break;
}
int minR = query_minT(s, mid);
int maxR = query_maxT(mid + 1, e);
if (minR <= l && maxR >= r) {
ans.push_back(0);
} else if (minR <= l) {
e = mid;
mid = (s + e) / 2;
} else if (maxR >= r) {
s = mid + 1;
mid = (s + e) / 2;
} else {
ans.push_back(1);
break;
}
}
}
return ans;
}