| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 611943 | fvogel499 | 늑대인간 (IOI18_werewolf) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "werewolf.h"
#include <bits/stdc++.h>
#define sz(x) ((x).size())
using namespace std;
const int inf = 1e9;
const int p2 = 1<<18;
struct Segtree {
Segtree() {
t = new int [p2*2];
for (int i = 0; i < p2*2; i++) t[i] = -inf;
}
~Segtree() {
delete [] t;
}
void upd(int x, int v) {
for (x += p2; x; x /= 2) {
t[x] = max(t[x], v);
}
}
int get(int b, int e) {
int r = -inf;
b += p2;
e += p2;
while (b <= e) {
if (b%2 == 1) {
r = max(r, t[b]);
b++;
}
if (e%2 == 0) {
r = max(r, t[e]);
e--;
}
b /= 2;
e /= 2;
}
return r;
}
int* t;
};
vector<int> calc(const int n, std::vector<int> edgeX, std::vector<int> edgeY, std::vector<int> queryX, std::vector<int> queryY, std::vector<int> queryLB, std::vector<int> queryRB, bool sw = false) {
vector<int> graph [n];
for (int i = 0; i < sz(edgeX); i++) {
graph[edgeX[i]].push_back(edgeY[i]);
graph[edgeY[i]].push_back(edgeX[i]);
}
vector<int> path;
for (int i = 0; i < n; i++) if (sz(graph[i]) == 1) {
bool vis [n];
for (int j = 0; j < n; j++) vis[j] = false;
int x = i;
while (1) {
vis[x] = true;
path.push_back(x);
bool ch = false;
for (int y : graph[x]) if (!vis[y]) {
x = y;
ch = true;
break;
}
if (!ch) {
break;
}
}
break;
}
assert(sz(path) == n);
// if (sw) {
// reverse(path.begin(), path.end());
// }
// int invPath [n];
// for (int i = 0; i < n; i++) invPath[path[i]] = i;
// const int nbQ = sz(queryX);
// for (int i = 0; i < nbQ; i++) {
// queryX[i] = invPath[queryX[i]];
// queryY[i] = invPath[queryY[i]];
// }
// vector<int> queriesSmallerThan [n];
// int latestPerQuery [nbQ];
// vector<int> queriesBiggerThan [n];
// int earliestPerQuery [nbQ];
// for (int i = 0; i < nbQ; i++) {
// if (queryLB[i] >= 1) {
// queriesSmallerThan[queryLB[i] - 1].push_back(i);
// }
// else {
// latestPerQuery[i] = -1;
// }
// if (queryRB[i]+1 < n) {
// queriesBiggerThan[queryRB[i] + 1].push_back(i);
// }
// else {
// earliestPerQuery[i] = n;
// }
// }
Segtree st = Segtree();
// for (int i = 0; i < n; i++) {
// st.upd(invPath[i], invPath[i]);
// for (int j : queriesSmallerThan[i]) {
// latestPerQuery[j] = st.get(queryX[j], queryY[j]);
// }
// }
st = Segtree();
// for (int i = n-1; i >= 0; i--) {
// st.upd(invPath[i], -invPath[i]);
// for (int j : queriesBiggerThan[i]) {
// earliestPerQuery[j] = -st.get(queryX[j], queryY[j]);
// }
// }
// vector<int> res(nbQ, -1);
// vector<int> askPref [n];
// for (int i = 0; i < nbQ; i++) {
// if (queryX[i] > queryY[i]) {
// res[i] = -1;
// }
// else {
// res[i] = 0;
// int x = min(earliestPerQuery[i]-1, n-1);
// assert(0 <= x && x < n);
// askPref[x].push_back(i);
// }
// }
// st = Segtree();
// for (int i = 0; i < n; i++) {
// st.upd(path[i], i);
// for (int j : askPref[i]) {
// int loc = st.get(queryLB[j], queryRB[j]);
// if (loc >= latestPerQuery[j]+1) {
// res[j] = 1;
// }
// else {
// res[j] = 0;
// }
// }
// }
return res;
}
std::vector<int> check_validity(const int n, std::vector<int> edgeX, std::vector<int> edgeY, std::vector<int> queryX, std::vector<int> queryY, std::vector<int> queryLB, std::vector<int> queryRB) {
vector<int> resA = calc(n, edgeX, edgeY, queryX, queryY, queryLB, queryRB, false);
vector<int> resB = calc(n, edgeX, edgeY, queryX, queryY, queryLB, queryRB, true);
vector<int> merge(size(resA));
for (int i = 0; i < size(resA); i++) {
if (resA[i] != -1) {
// assert(resB[i] == -1);
merge[i] = resA[i];
}
else {
// assert(resB[i] != -1);
merge[i] = resB[i];
}
}
return merge;
}