Submission #314597

#TimeUsernameProblemLanguageResultExecution timeMemory
314597tengiz05Werewolf (IOI18_werewolf)C++17
49 / 100
788 ms37192 KiB
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; const int N = 2e5+5, inf = 1e9; int n, sz, m, timer=0; int depth[N]; int a[N]; vector<int> edges[N]; void dfs(int u, int p, int d = 0){ a[u]=timer,timer++; depth[u] = d; for(auto v : edges[u]){ if(v == p)continue; dfs(v, u, d+1); } } struct segtree { struct Node{ int mn, mx; }; vector<Node> t; Node neutral = {inf, 0}; void build(){ sz=1; while(sz<n)sz<<=1; t.assign(sz*2, neutral); for(int i=0;i<n;i++){ t[a[i]+sz] = {i, i}; }for(int i=sz-1;i>0;i--){ t[i] = {min(t[i*2].mn, t[i*2+1].mn), max(t[i*2].mx, t[i*2+1].mx)}; } } int f_less(int l, int r, int L, int R, int node, int x){ if(L >= r || R <= l)return inf; if(R-L == 1){ if(L >= l && t[node].mn < x)return L; else return inf; }int mid = (L+R)/2; if(L >= l && R <= r){ if(t[node*2].mn < x)return f_less(l, r, L, mid, node*2, x); else return f_less(l, r, mid, R, node*2+1, x); }return min(f_less(l, r, L, mid, node*2, x), f_less(l, r, mid, R, node*2+1, x)); }int f_less(int l, int x){return f_less(l, sz, 0, sz, 1, x);} int f_great(int l, int r, int L, int R, int node, int x){ if(L >= r || R <= l)return inf; if(R-L == 1){ if(L >= l && t[node].mx > x)return L; else return inf; }int mid = (L+R)/2; if(L >= l && R <= r){ if(t[node*2].mx > x)return f_great(l, r, L, mid, node*2, x); else return f_great(l, r, mid, R, node*2+1, x); }return min(f_great(l, r, L, mid, node*2, x), f_great(l, r, mid, R, node*2+1, x)); }int f_great(int l, int x){return f_great(l, sz, 0, sz, 1, x);} //903475834u1ify98pw75ruehruiae7893yu524hfuiayw78ryhweajkrasfasfasdfsddasf4589i7889he6ghwerg int l_less(int l, int r, int L, int R, int node, int x){ if(L >= r || R <= l)return -1; if(R-L == 1){ if(R <= r && t[node].mn < x)return L; else return -1; }int mid = (L+R)/2; if(L >= l && R <= r){ if(t[node*2+1].mn < x)return l_less(l, r, mid, R, node*2+1, x); else return l_less(l, r, L, mid, node*2, x); }return max(l_less(l, r, L, mid, node*2, x), l_less(l, r, mid, R, node*2+1, x)); }int l_less(int r, int x){return l_less(0, r, 0, sz, 1, x);} int l_great(int l, int r, int L, int R, int node, int x){ if(L >= r || R <= l)return -1; if(R-L == 1){ if(R <= r && t[node].mx > x)return L; else return -1; }int mid = (L+R)/2; if(L >= l && R <= r){ if(t[node*2+1].mx > x)return l_great(l, r, mid, R, node*2+1, x); else return l_great(l, r, L, mid, node*2, x); }return max(l_great(l, r, L, mid, node*2, x), l_great(l, r, mid, R, node*2+1, x)); }int l_great(int r, int x){return l_great(0, r, 0, sz, 1, x);} }seg; // ================================================================= vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) { n = N; m = X.size(); for(int i=0;i<m;i++){ edges[X[i]].push_back(Y[i]); edges[Y[i]].push_back(X[i]); } int Q = S.size(); if(n <= 3000 && m <= 6000 && Q <= 3000){ vector<int> ans; for(int i=0;i<Q;i++){ vector<int> g1(n); vector<int> g2(n); vector<bool> used1(n); vector<bool> used2(n); int ans1=0; int l=L[i], r=R[i]; queue<int> q; q.push(S[i]);used1[S[i]]=true; while(!q.empty()){ int u = q.front();q.pop(); for(auto v : edges[u]){ if(!used1[v]&&v >= l){ q.push(v); used1[v]=true; } } } q.push(E[i]);used2[E[i]]=true; while(!q.empty()){ int u = q.front();q.pop(); for(auto v : edges[u]){ if(!used2[v]&&v <= r){ q.push(v); used2[v]=true; } } }for(int u=0;u<n;u++){ ans1 |= (used1[u]&&used2[u]); }ans.push_back(ans1); }return ans; } dfs(0, 0); int mxdep = 0, inddep = 0; for(int i=0;i<n;i++){ if(depth[i] > mxdep)mxdep=depth[i], inddep = i; }timer=0; dfs(inddep, inddep); seg.build(); vector<int> ans; for(int i=0;i<Q;i++){ int start = a[S[i]], end = a[E[i]]; int l = L[i], r = R[i]; int ans1 = 1; if(start <= end){ int ff = seg.f_less(start, l)-1; int ss = seg.l_great(end, r)+1; if(ff < ss)ans1 = 0; }else { int ff = seg.l_less(start, l)+1; int ss = seg.f_great(end, r)-1; if(ff > ss)ans1 = 0; } ans.push_back(ans1); }return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...