| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 112766 | imaxblue | 자리 배치 (IOI18_seats) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define vi vector<int>
#define vpii vector<pii>
#define vp3i vector<p3i>
#define vpll vector<pll>
#define vp3l vector<p3l>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() ((rand() << 14)+rand())
#define scan(X) do{while((X=getchar())<'0'); for(X-='0'; '0'<=(_=getchar()); X=(X<<3)+(X<<1)+_-'0');}while(0)
char _;
#define pi 3.14159265358979323846
#define SZ 800
int n, m, c=0, q;
int ans[200005];
//dsu stuff
int r[200005], min_node[200005], root;
vector<int> com[200005], comu[200005], com3[200005];
//tree stuff
int d[200005], lo[400005], hi[400005], node[400005];
int anc[20][400005];
int lg[400005];
vector<int> tree[200005];
vector<pii> edge;
vector<pair<pii, p3i> > que;
vector<int> pre_lca[200005];
bool mrg(int A, int B){
//cout << "*" << A << ' ' <<B << ' ';
A = r[A]; B = r[B];
//cout << A << ' ' << B << endl;
if (A == B) return 0;
if (com[A].size() < com[B].size()) return mrg(B, A);
for(auto i:com[B]){
com[A].pb(i);
r[i] = A;
}
//cout << A << ' ' << B << ' ' << min_node[A] << ' ' << min_node[B] << endl;
tree[min_node[A]].pb(min_node[B]);
tree[min_node[B]].pb(min_node[A]);
min_node[A] = min(min_node[A], min_node[B]);
return 1;
}
void dfs(int N, int P){
if (P != -1) d[N] = d[P]+1;
node[lo[N] = hi[N] = c++] = N;
for(auto nxt:tree[N]){
if (nxt == P) continue;
dfs(nxt, N);
node[hi[N] = c++] = N;
}
//cout << N << ' ' << P << ' ' << lo[N] << ' ' << hi[N] << endl;
}
void build(){
fox(l, n){
r[l] = l;
min_node[l] = l;
com[l] = vector<int>({l});
}
sort(edge.rbegin(), edge.rend());
fox(l, m){
mrg(edge[l].x, edge[l].y);
}
dfs(0, -1);
fox(l, 2*n){
//cout << node[l] << ' ';
anc[0][l] = node[l];
for (int l2 = 1; l2 <= 19; ++l2){
if ((l + 1 - (1<<l2) < 0)) break;
anc[l2][l] = min(anc[l2-1][l], anc[l2-1][l - (1<<(l2-1))]);
}
}
//cout << endl;
}
int get_anc(int A, int B){
if (lo[A] > lo[B]) return get_anc(B, A);
if (hi[A] > hi[B]) return A;
int lft = hi[A], rit = lo[B];
int len = lg[rit - lft + 1];
//cout << "*" << lft <<' ' << rit << ' ' << len << endl;
return min(anc[len][rit], anc[len][lft + (1<<len) - 1]);
}
bool on[200005];
void dfs2(int N, int P){
for (auto i:tree[N]){
if (i == P) continue;
dfs2(i, N);
on[N]|=on[i];
}
}
void dfs3(int N, int P, int B){
if (on[N]) B = N;
for (auto i:tree[N]){
if (i == P) continue;
dfs3(i, N, B);
}
pre_lca[root][N] = B;
}
void precomp(int A){
root = A;
pre_lca[A] = vector<int>(n);
drain(on);
com3[A].clear();
com3[A].pb(A);
for(auto i:com[A]){
comu[A].pb(i);
}
com[A].clear();
for(auto i:comu[A]){
//cout << i << ' ';
on[i] = 1;
}
//cout << endl;
dfs2(0, -1);
dfs3(0, -1, 0);
//fox(l, n) cout << on[l] << ' '; cout << endl;
//fox(l, n) cout << pre_lca[A][l] << ' '; cout << endl;
}
bool mrg2(int A, int B){
A = r[A]; B = r[B];
if (A == B) return 0;
if (com[A].size() + comu[A].size() < com[B].size() + comu[B].size()) return mrg2(B, A);
//cout << A << ' ' << B << endl;
for(auto i:com[B]){
com[A].pb(i);
r[i] = A;
}
for(auto i:comu[B]){
comu[A].pb(i);
r[i] = A;
}
for (auto i:com3[B]){
com3[A].pb(i);
}
if (com[A].size() > SZ){
precomp(A);
}
return 1;
}
int check(int A, int B){
int res = 0;
A = r[A];
for(auto i:com3[A]){
//cout << pre_lca[i][B] << endl;
res = max(res, pre_lca[i][B]);
}
//res = pre_lca[A][B];
fox(l, com[A].size()){
//cout << com[A][l] << ' ' << B << ' ' << get_anc(com[A][l], B) << endl;
res = max(res, get_anc(com[A][l], B));
}
//cout << "%" << res << endl;
return res;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
m = X.size();
n = N;
lg[0] = -1;
fox1(l, 2*N){
lg[l] = lg[l/2]+1;
}
fox(l, m){
if (X[l] > Y[l]) swap(X[l], Y[l]);
edge.pb(mp(X[l], Y[l]));
que.pb(mp(mp(Y[l], -X[l]), mp(mp(-1, -1), -1)));
}
build();
q = S.size();
fox(l, q){
que.pb(mp(mp(R[l], L[l]), mp(mp(S[l], E[l]), l)));
//cout << L[l] << ' ' << R[l] << ' ' << S[l] << ' ' << E[l] << endl;
}
//return vector<int>();
fox(l, n){
r[l] = l;
com[l] = vector<int>({l});
comu[l] = vector<int>();
}
sort(que.begin(), que.end());
fox(l, que.size()){
int y = que[l].x.x, x = que[l].x.y, s = que[l].y.x.x, e = que[l].y.x.y, i = que[l].y.y;
if (s == -1){
x*=-1;
mrg2(x, y);
} else {
//cout << "*" << x << ' ' << y << ' ' << s << ' ' << e << endl;
if (e > y || s < x){
ans[i] = 0;
continue;
}
ans[i] = (check(e, s) >= x);
//cout << "^" << i << ' ' << x << endl;
}
}
vector<int> ans2 = vector<int>();
fox(l, q ) ans2.pb(ans[l]);
return ans2;
}
/*
int32_t main(){
int n, m, q, s, e, x, y;
vector<int> X, Y, S, E, L, R;
cin >> n >> m >> q;
fox(l, m){
//x = l; y = l+1;
cin >> x >> y;
X.pb(x);
Y.pb(y);
}
fox(l, q){
//s = 0; e = n-1; x = 0; y = n-1;
cin >> s >> e >> x >> y;
S.pb(s);
E.pb(e);
L.pb(x);
R.pb(y);
}
vector<int> v = check_validity(n, X, Y, S, E, L, R);
cout << v.size() << endl;
fox(l, v.size()) cout << v[l] << ' '; cout << endl;
return 0;
}*/
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/