| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 729621 | t6twotwo | 자리 배치 (IOI18_seats) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int M = X.size();
int Q = S.size();
vector<vector<int>> adj(N);
for (int i = 0; i < M; i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
if (N <= 3000 && M <= 6000 && Q <= 3000) {
vector<int> p(N);
function<int(int)> find = [&](int x) {
return x == p[x] ? x : p[x] = find(p[x]);
};
vector<vector<int>> s(N);
auto unite = [&](int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return;
}
if (s[x].size() > s[y].size()) {
swap(x, y);
}
for (int z : s[x]) {
p[z] = y;
s[y].push_back(z);
}
};
for (int i = 0; i < N; i++) {
p[i] = i;
s[i] = {i};
}
vector hi(N, vector<int>(N, -1));
for (int x = N - 1; x >= 0; x--) {
hi[x][x] = x;
for (int y : adj[x]) {
if (y < x || find(x) == find(y)) {
continue;
}
for (int u : s[find(x)]) {
for (int v : s[find(y)]) {
hi[u][v] = x;
hi[v][u] = x;
}
}
unite(x, y);
}
}
for (int i = 0; i < N; i++) {
p[i] = i;
s[i] = {i};
}
vector lo(N, vector<int>(N, -1));
for (int x = 0; x < N; x++) {
lo[x][x] = x;
for (int y : adj[x]) {
if (y > x || find(x) == find(y)) {
continue;
}
for (int u : s[find(x)]) {
for (int v : s[find(y)]) {
lo[u][v] = x;
lo[v][u] = x;
}
}
unite(x, y);
}
}
vector<int> ans(Q);
for (int i = 0; i < Q; i++) {
for (int j = L[i]; j <= R[i]; j++) {
if (hi[S[i]][j] >= L[i] && lo[j][E[i]] <= R[i]) {
ans[i] = 1;
}
}
}
return ans;
} else {
vector<int> A;
for (int i = 0; i < N; i++) {
if (adj[i].size() == 1) {
A.push_back(i);
A.push_back(adj[i][0]);
}
}
while (A.size() < N) {
int x = A[A.size() - 2];
int y = A[A.size() - 1];
A.push_back(adj[y][0] ^ adj[y][1] ^ x);
}
vector<int> lg(N + 1);
for (int i = 2; i <= N; i++) {
lg[i] = lg[i / 2] + 1;
}
vector smin(N, vector<int>(lg[N] + 1));
vector smax(N, vector<int>(lg[N] + 1));
for (int i = 0; i < N; i++) {
smin[i][0] = A[i];
smax[i][0] = A[i];
}
for (int j = 0; j < lg[N]; j++) {
for (int i = 0; i + (2 << j) <= N; i++) {
smin[i][j + 1] = min(smin[i][j], smin[i + (1 << j)][j]);
smax[i][j + 1] = max(smax[i][j], smax[i + (1 << j)][j]);
}
}
auto qmin = [&](int l, int r) {
if (l == r) {
return N;
}
int k = lg[r - l];
return min(smin[l][k], smin[r - (1 << k)][k]);
};
auto qmax = [&](int l, int r) {
if (l == r) {
return -1;
}
int k = lg[r - l];
return max(smax[l][k], smax[r - (1 << k)][k]);
};
vector<int> B(N);
for (int i = 0; i < N; i++) {
B[A[i]] = i;
}
vector<int> ans(Q);
for (int i = 0; i < Q; i++) {
if (S[i] < L[i] || E[i] > R[i]) {
continue;
}
int x = B[S[i]], u = -1;
int y = B[E[i]], v = -1;
if (x < y) {
int lo = x, hi = y;
while (lo < hi) {
int mi = (lo + hi + 1) / 2;
if (qmin(lo, mi + 1) >= L[i]) {
lo = mi;
} else {
hi = mi - 1;
}
}
u = lo;
lo = x, hi = y;
while (lo < hi) {
int mi = (lo + hi) / 2;
if (qmax(mi, y + 1) <= R[i]) {
hi = mi;
} else {
lo = mi + 1;
}
}
v = lo;
} else {
int lo = x, hi = y;
while (lo < hi) {
int mi = (lo + hi + 1) / 2;
if (qmax(lo, mi + 1) <= R[i]) {
lo = mi;
} else {
hi = mi - 1;
}
}
u = lo;
lo = x, hi = y;
while (lo < hi) {
int mi = (lo + hi) / 2;
if (qmin(mi, y + 1) <= R[i]) {
hi = mi;
} else {
lo = mi + 1;
}
}
v = lo;
}
if (v <= u) {
ans[i] = 1;
}
}
return ans;
}
}