oj.uz

Submission #76465

# Submission time Handle Problem Language Result Execution time Memory
76465 2018-09-13T14:33:11 Z born2rule Werewolf (IOI18_werewolf) C++14
15 / 100
 1110 ms 174896 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define db long double
#define ii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define FN(i, n) for (int i = 0; i < (int)(n); ++i)
#define FEN(i,n) for (int i = 1;i <= (int)(n); ++i)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repv(i,a,b) for(int i=b-1;i>=a;i--)
#define SET(A, val) memset(A, val, sizeof(A))
typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const int N=200005;
vi v[N];
bool vis[N];
void dfs(int u,int l,int r,vi &tmp,int type=0)
{
  if(type==0 && u<l) return;
  if(type==1 && u>r) return;
  vis[u]=true;
  tmp.pb(u);
  for(int v1:v[u])
    {
      if(vis[v1]) continue;
      dfs(v1,l,r,tmp,type);
    }
}
vi subtask12(int n,vi S,vi E,vi L,vi R)
{
  int q=sz(S);
  vi ans(q,0);
  rep(i,0,q)
    {
      int x=S[i],y=E[i],l=L[i],r=R[i]; x++,y++,l++,r++;
      if(x<l || y>r)
	continue;
      vi tmp1,tmp2;
      rep(j,1,n+1) vis[j]=false;
      dfs(x,l,r,tmp1);
      rep(j,1,n+1) vis[j]=false;
      dfs(y,l,r,tmp2,1);
      sort(all(tmp1)); sort(all(tmp2));
      bool ok=false;
      for(int x:tmp1)
	{
	  int ind=lower_bound(all(tmp2),x)-tmp2.begin();
	  if(ind!=sz(tmp2) && tmp2[ind]==x) ok=true;
	}
      if(ok) ans[i]=1;
    }
  return ans;
}
vector<ii> seg[4*N];
vi pre[2][4*N];
int pos[N],a[N];
#define lc (pos)+(pos)
#define rc (lc)|1
void build(int low,int high,int pos)
{
  if(low==high)
    {
      seg[pos].pb(mp(a[low],low));
      rep(i,0,2)
	pre[i][pos].pb(low);
      return;
    }
  int mid=(low+high)>>1;
  build(low,mid,lc); build(mid+1,high,rc);
  seg[pos]=seg[lc];
  for(auto x:seg[rc]) seg[pos].pb(x);
  sort(all(seg[pos]));
  rep(i,0,2)
    pre[i][pos].pb(seg[pos][0].se);
  rep(i,1,sz(seg[pos]))
    {
      pre[0][pos].pb(min(pre[0][pos].back(),seg[pos][i].se));
      pre[1][pos].pb(min(pre[1][pos].back(),seg[pos][i].se));
    }
}
int query(int low,int high,int pos,int l,int r,int k,int type=0)
{
  if(low>r || high<l) return ((type==0)?N:-1);
  if(low>=l && high<=r)
    {
      int ind=upper_bound(all(seg[pos]),mp(k,N))-seg[pos].begin()-1;
      if(ind<0 || seg[pos][ind].fi>k) return N;
      return pre[type][pos][ind];
    }
  int mid=(low+high)>>1;
  if(!type)
    return min(query(low,mid,lc,l,r,k),query(mid+1,high,rc,l,r,k));
  return max(query(low,mid,lc,l,r,k),query(mid+1,high,rc,l,r,k));
}
int query2(int low,int high,int pos,int l,int r)
{
  if(low>r || high<l) return -1;
  if(low>=l && high<=r)
    return seg[pos].back().fi;
  int mid=(low+high)>>1;
  return max(query2(low,mid,lc,l,r),query2(mid+1,high,rc,l,r));
}
vi subtask3(int n,vi S,vi E,vi L,vi R)
{
  int q=sz(S);
  vi ans(q,0);
  int ind=-1;
  rep(i,1,n+1) if(sz(v[i])==1) ind=i;
  if(ind==-1) return ans;
  a[1]=ind; pos[ind]=1;
  rep(i,2,n+1)
    {
      for(int v1:v[ind])
	{
	  if(v1==a[i-1]) continue;
	  ind=v1; break;
	}
      a[i]=ind;
      pos[ind]=i;
    }
  build(1,n,1);
  rep(i,0,q)
    {
      int x=S[i],y=E[i],l=L[i],r=R[i]; x++,y++,l++,r++;
      if(x<l || y>r)
	continue;
      int nx=pos[x],ny=pos[y];
      if(nx<ny)
	{
	  //find 1st element smaller than l in nx,ny
	  ind=query(1,n,1,nx,ny,l-1);
	  if(ind>nx && ind!=N && a[ind-1]>=l && a[ind-1]<=r)
	    {
	      //check if max element in ind,ny is <=r
	      int mx=query2(1,n,1,ind,ny);
	      if(mx<=r) ans[i]=1;
	    }
	  else if(y>=l && y<=r) ans[i]=1;
	}
      else
	{
	  //find last element smaller than l in nx,ny
	  ind=query(1,n,1,ny,nx,l-1,1);
	  if(ind<nx && ind!=-1 && a[ind+1]>=l && a[ind+1]<=r)
	    {
	      //check if max element in ny,ind is <=r
	      int mx=query2(1,n,1,ny,ind);
	      if(mx<=r) ans[i]=1;
	    }
	  else if(y>=l && y<=r) ans[i]=1;
	}
    }
  return ans;
}
vi check_validity(int n,vi X,vi Y,vi S,vi E,vi L,vi R)
{
  int q=sz(S);
  rep(i,0,sz(X))
    {
      X[i]++; Y[i]++;
      v[X[i]].pb(Y[i]);
      v[Y[i]].pb(X[i]);
    }
  if(n<=3000 && q<=3000)
    return subtask12(n,S,E,L,R);
  if(sz(X)==n-1)
    return subtask3(n,S,E,L,R);
  return S;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 61432 KB Output is correct
2 Correct 57 ms 61520 KB Output is correct
3 Correct 58 ms 61664 KB Output is correct
4 Correct 55 ms 61664 KB Output is correct
5 Correct 56 ms 61664 KB Output is correct
6 Correct 58 ms 61664 KB Output is correct
7 Correct 56 ms 61664 KB Output is correct
8 Correct 81 ms 61664 KB Output is correct
9 Correct 61 ms 61768 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 61432 KB Output is correct
2 Correct 57 ms 61520 KB Output is correct
3 Correct 58 ms 61664 KB Output is correct
4 Correct 55 ms 61664 KB Output is correct
5 Correct 56 ms 61664 KB Output is correct
6 Correct 58 ms 61664 KB Output is correct
7 Correct 56 ms 61664 KB Output is correct
8 Correct 81 ms 61664 KB Output is correct
9 Correct 61 ms 61768 KB Output is correct
10 Correct 1078 ms 62192 KB Output is correct
11 Correct 713 ms 62192 KB Output is correct
12 Correct 103 ms 62336 KB Output is correct
13 Correct 1110 ms 62336 KB Output is correct
14 Correct 803 ms 62336 KB Output is correct
15 Correct 876 ms 62348 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 962 ms 174896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 61432 KB Output is correct
2 Correct 57 ms 61520 KB Output is correct
3 Correct 58 ms 61664 KB Output is correct
4 Correct 55 ms 61664 KB Output is correct
5 Correct 56 ms 61664 KB Output is correct
6 Correct 58 ms 61664 KB Output is correct
7 Correct 56 ms 61664 KB Output is correct
8 Correct 81 ms 61664 KB Output is correct
9 Correct 61 ms 61768 KB Output is correct
10 Correct 1078 ms 62192 KB Output is correct
11 Correct 713 ms 62192 KB Output is correct
12 Correct 103 ms 62336 KB Output is correct
13 Correct 1110 ms 62336 KB Output is correct
14 Correct 803 ms 62336 KB Output is correct
15 Correct 876 ms 62348 KB Output is correct
16 Incorrect 962 ms 174896 KB Output isn't correct
17 Halted 0 ms 0 KB -