| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 991298 | wood | Werewolf (IOI18_werewolf) | C++17 | 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 "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define vi vector<int>
#define vp32 vector<p32>
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define MOD %1000000007
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//never guess
//never debug without reviewing code
//never try adding ones or substracting them
//only step by step debug when necessay
constexpr int N = 1e6;
struct segtree
{
int size = 1; vi mx, mn;
segtree(int n){while(size<=n) size*=2; mx.resize(N,0); mn.resize(N,INT_MAX);}
void upd(int i, int u){
upd(i,u,0,0,size);
}
void upd(int i, int u, int x, int l, int r){
if(r-l==1){
mx[x] = u;
mn[x] = u;
return;
}
int m = (l+r)/2;
if(i<m) upd(i,u,2*x+1,l,m);
else upd(i,u,2*x+2,m,r);
mn[x] = min(mn[2*x+1],mn[2*x+2]);
mx[x] = max(mx[2*x+1],mx[2*x+2]);
}
int get(int l, int r, bool ismx){
return get(l,r,ismx,0,0,size);
}
int get(int l, int r, bool ismx, int x, int lx, int rx){
vi& arr = (ismx) ? mx : mn;
if(rx<=l||lx>=r) return (ismx) ? 0 : INT_MAX;
if(lx>=l&&rx<=r) return arr[x];
int m = (rx+lx)/2;
int o = get(l,r,ismx,2*x+1,lx,m);
int t = get(l,r,ismx,2*x+2,m,rx);
if(ismx) return max(o,t); else return min(o,t);
}
};
vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
vi res(S.size());
vi adj[N];
int inds[N];
segtree sgt(N);
//chain setup
for(int i = 0; i<X.size(); i++){
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
vi chain;
for(int i = 0; i<N; i++){
if(adj[i].size()==1){
inds[i]=0; sgt.upd(0,i);
chain.pb(i);
int e = adj[i][0];
int p = i;
while(adj[e].size()!=1){
inds[e]=chain.size(); sgt.upd(chain.size(),e);
chain.pb(e);
for(int x : adj[e]) if(x!=p){
p = e;
e = x;
break;
}
}
inds[e]=chain.size(); sgt.upd(chain.size(),e);
chain.pb(e);
break;
}
}
// binary search the intervals assuming all starting pos are smaller
auto x = [&](){
for (size_t i = 0; i < S.size(); i++)
{
if(inds[S[i]]>inds[E[i]]) continue;
if(S[i]<L[i]||E[i]>R[i]){
res[i] = 0;
continue;
}
//find farthes position that can be travelled as a human;
int l = inds[S[i]], r = inds[E[i]]+1;
while(r-l>1){
int m = (r+l)/2;
if(sgt.get(inds[S[i]],m+1,false)<L[i]) r = m;
else l = m;
}
int p = l;
l = inds[E[i]], r = inds[S[i]]-1;
while(l-r>1){
int m = (r+l)/2;
if(sgt.get(m,inds[E[i]]+1,true)>R[i]) r = m;
else l = m;
}
res[i] = p>=l;
}
};
x();
reverse(chain.begin(),chain.end());
for(int i = 0; i<N; i++){
sgt.upd(i,chain[i]);
inds[chain[i]] = i;
}
x();
return res;
}
#ifndef ONLINE_JUDGE
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
int main() {
freopen("input.in", "r", stdin);
freopen("input.out", "w", stdout);
int N = read_int();
int M = read_int();
int Q = read_int();
std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
for (int j = 0; j < M; ++j) {
X[j] = read_int();
Y[j] = read_int();
}
for (int i = 0; i < Q; ++i) {
S[i] = read_int();
E[i] = read_int();
L[i] = read_int();
R[i] = read_int();
}
std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
for (size_t i = 0; i < A.size(); ++i) {
printf("%d ", A[i]);
}
return 0;
}
#endif