| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 400744 | Jarif_Rahman | 늑대인간 (IOI18_werewolf) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "werewolf.h"
#include <bits/stdc++.h>
#pragma GCC target ("avx")
#pragma GCC target ("avx2")
#pragma GCC target ("ofast")
#pragma GCC target ("fma")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const int lim = 6e5;
struct fenwick_tree{
int n;
vector<int> sm;
fenwick_tree(int _n){
n = _n;
sm.assign(n, 0);
}
void upd(int in, int x){
in++;
while(in <= n) sm[in-1]+=x, in+=in&-in;
}
int sum(int in){
in++;
int s = 0;
while(in >= 1) s+=sm[in-1], in-=in&-in;
return s;
}
int sum(int l, int r){
l--;
int s = sum(r);
if(l >= 0) s-=sum(l);
return s;
}
};
struct reachability_tree{
int n;
vector<int> p;
vector<vector<int>> v;
vector<int> w;
reachability_tree(int _n, int _w){
n = _n;
p.resize(n);
v.resize(n);
w.resize(n, _w);
for(int i = 0; i < n; i++) p[i] = i;
}
inline int get(int x){
if(p[x] != x) p[x] = get(p[x]);
return p[x];
}
void unite(int a, int b, int _w){
a = get(a), b = get(b);
p[a] = n, p[b] = n;
p.pb(n);
v.pb({});
v[n].pb(a);
if(a != b) v[n].pb(b);
w.pb(_w);
n++;
}
};
int n, m, q;
reachability_tree rtl(0, 0), rtr(0, 0);
int szl[lim], szr[lim], posl[lim], posr[lim];
vector<int> al, ar;
int ancl[lim][20], ancr[lim][20];
void dfsl(int nd, int ss){
posl[nd] = al.size();
szl[nd] = 0;
if(rtl.v[nd].empty()){
al.pb(nd);
szl[nd] = 1;
ancl[nd][0] = ss;
return;
}
for(int x: rtl.v[nd]) if(x != ss) dfsl(x, nd);
for(int x: rtl.v[nd]) szl[nd]+=szl[x];
ancl[nd][0] = ss;
}
void dfsr(int nd, int ss){
posr[nd] = ar.size();
szr[nd] = 0;
if(rtr.v[nd].empty()){
ar.pb(nd);
szr[nd] = 1;
ancr[nd][0] = ss;
return;
}
for(int x: rtr.v[nd]) if(x != ss) dfsr(x, nd);
for(int x: rtr.v[nd]) szr[nd]+=szr[x];
ancr[nd][0] = ss;
}
int get_anc_l(int nd, int ss){
for(int i = 0; i < 20; i++){
if(ss%2 == 1) nd = ancl[nd][i];
if(nd == -1) return -1;
ss/=2;
}
return nd;
}
int get_anc_r(int nd, int ss){
for(int i = 0; i < 20; i++){
if(ss%2 == 1) nd = ancr[nd][i];
if(nd == -1) return -1;
ss/=2;
}
return nd;
}
int bsl(int nd, int vl){
int a = 0, b = lim;
while(a < b){
int md = (a+b+1)/2;
int x = get_anc_l(nd, md);
if(x == -1) x = 1e9;
else x = rtl.w[x];
if(x > vl) b = md-1;
else a = md;
}
return get_anc_l(nd, a);
}
int bsr(int nd, int vl){
int a = 0, b = lim;
while(a < b){
int md = (a+b+1)/2;
int x = get_anc_r(nd, md);
if(x == -1) x = -1;
else x = rtr.w[x];
if(x < vl) b = md-1;
else a = md;
}
return get_anc_r(nd, a);
}
vector<int> check_validity(int n, vector<int> U, vector<int> V, vector<int> ss, vector<int> ee, vector<int> L, vector<int> R){
::n = n, m = U.size(), q = ss.size();
pair<int, int> edgel[m], edger[m];
for(int i = 0; i < m; i++) edgel[i] = {U[i], V[i]}, edger[i] = {U[i], V[i]};
sort(edgel, edgel+m, [&](pair<int, int> a, pair<int, int> b){
return max(a.f, a.sc) < max(b.f, b.sc);
});
sort(edger, edger+m, [&](pair<int, int> a, pair<int, int> b){
return min(a.f, a.sc) > min(b.f, b.sc);
});
rtl = reachability_tree(n, 0), rtr = reachability_tree(n, n+1);
for(int i = 0; i < m; i++) rtl.unite(edgel[i].f, edgel[i].sc, max(edgel[i].f, edgel[i].sc)), rtr.unite(edger[i].f, edger[i].sc, min(edger[i].f, edger[i].sc));
for(int i = 0; i < rtl.n; i++) for(int j = 0; j < 20; j++) ancl[i][j] = -1;
for(int i = 0; i < rtr.n; i++) for(int j = 0; j < 20; j++) ancr[i][j] = -1;
dfsl(rtl.n-1, -1);
dfsr(rtr.n-1, -1);
for(int i = 1; i < 20; i++) for(int j = 0; j < rtl.n; j++){
if(ancl[j][i-1] == -1) continue;
ancl[j][i] = ancl[ancl[j][i-1]][i-1];
}
for(int i = 1; i < 20; i++) for(int j = 0; j < rtr.n; j++){
if(ancr[j][i-1] == -1) continue;
ancr[j][i] = ancr[ancr[j][i-1]][i-1];
}
vector<int> ans(q, 0);
pair<int, int> points[n];
for(int i = 0; i < n; i++) points[i] = {posl[i], posr[i]};
sort(points, points+n);
vector<tuple<int, int, int>> query1[n], query2[n];
for(int qq = 0; qq < q; qq++){
int ndl = bsl(ee[qq], R[qq]), ndr = bsr(ss[qq], L[qq]);
int l1 = posl[ndl], r1 = posl[ndl]+szl[ndl]-1;
int l2 = posr[ndr], r2 = posr[ndr]+szr[ndr]-1;
query1[max(l1, r1)].pb({min(l2, r2), max(l2, r2), qq});
if(min(l1, r1) > 0) query2[min(l1, r1)-1].pb({min(l2, r2), max(l2, r2), qq});
}
fenwick_tree bit(n);
int inx = 0;
for(int i = 0; i < n; i++){
while(inx < n && points[inx].f == i){
bit.upd(points[inx].sc, 1);
inx++;
}
for(auto [r1, r2, in]: query1[i]){
ans[in]+=bit.sum(r1, r2);
}
for(auto [r1, r2, in]: query2[i]){
ans[in]-=bit.sum(r1, r2);
}
}
for(int &x: ans) x = min(x, 1);
return ans;
}