oj.uz

Submission #1111584

# Submission time Handle Problem Language Result Execution time Memory
1111584 2024-11-12T09:47:23 Z epicci23 Werewolf (IOI18_werewolf) C++17
15 / 100
 197 ms 19796 KB 
#include "bits/stdc++.h"
#include "werewolf.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 3005;
const int INF = 1e9;
vector<int> v[N];
vector<int> Hvis,Wvis,ar;

void create(int c,int p,int ind){
  ar[ind]=c;
  for(int x:v[c]){
  	if(x==p) continue;
  	create(x,c,ind+1);
  }
}

void dfs_h(int c,int l){
  if(Hvis[c]) return;
  Hvis[c]=1;
  for(int x:v[c]) if(x>=l) dfs_h(x,l);
}

void dfs_w(int c,int r){
  if(Wvis[c]) return;
  Wvis[c]=1;
  for(int x:v[c]) if(x<=r) dfs_w(x,r);
}

struct SegT{
  vector<int> mn,mx;
  SegT(int _n){
    mn.assign(4*_n+5,INF);
    mx.assign(4*_n+5,-INF);
  }

  void build(int rt,int l,int r){
  	if(l==r){
  	  mn[rt]=mx[rt]=ar[l];
  	  return;
  	}
  	int m=(l+r)/2;
  	build(rt*2,l,m),build(rt*2+1,m+1,r);
  	mn[rt]=min(mn[rt*2],mn[rt*2+1]);
  	mx[rt]=max(mx[rt*2],mx[rt*2+1]);
  }

  int get_max(int rt,int l,int r,int gl,int gr){
   if(l>=gl && r<=gr) return mx[rt];
   if(r<gl || l>gr) return -INF;
   int m=(l+r)/2;
   return max(get_max(rt*2,l,m,gl,gr),get_max(rt*2+1,m+1,r,gl,gr));
  }

  int get_min(int rt,int l,int r,int gl,int gr){
   if(l>=gl && r<=gr) return mn[rt];
   if(r<gl || l>gr) return INF;
   int m=(l+r)/2;
   return min(get_min(rt*2,l,m,gl,gr),get_min(rt*2+1,m+1,r,gl,gr));
  }
};

vector<int> check_validity(int _N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
  int n=_N,m=sz(X),q=sz(L);

  for(int i=0;i<m;i++){
 	int a=X[i],b=Y[i];
 	v[a].push_back(b);
 	v[b].push_back(a);
  }

  vector<int> res(q,0);
  
  if(n<N){


	   for(int i=0;i<q;i++){
	   int x=S[i],y=E[i],l=L[i],r=R[i];
	   Wvis.assign(n+5,0);
	   Hvis.assign(n+5,0);
	   dfs_h(x,l);
	   dfs_w(y,r);
	   bool ok=0;
	   for(int i=0;i<n;i++) if(Wvis[i] && Hvis[i]) ok=1;
	   res[i]=ok;
	  }

  }
  else{
  	ar.resize(n+5);
    for(int i=0;i<n;i++){
      if(sz(v[i])==1){
        create(i,-1,0);
        break;
      }
    }
    SegT Seg(n+5);
    Seg.build(1,0,n-1);
    for(int i=0;i<q;i++){
      int x=S[i],y=E[i],l=L[i],r=R[i];
      if(x<y){
        int ll = x , rr = n - 1;
        while(ll<rr){
          int mm = (ll+rr+1)/2;
          if(Seg.get_min(1,0,n-1,x,mm)>=l) ll=mm;
          else rr=mm-1;
        }
        int l2 = 0 , r2 = y;
        while(l2<r2){
          int m2 = (l2+r2)/2;
          if(Seg.get_max(1,0,n-1,m2,y)<=r) r2=m2;
          else l2=m2+1;
        } 
        res[i]=(l2<=ll);
      }
      else{
        int ll = 0 , rr = x;
        while(ll<rr){
          int mm = (ll+rr)/2;
          if(Seg.get_min(1,0,n-1,mm,x)>=l) rr=mm;
          else ll=mm+1;
        }

        int l2 = y , r2 = n - 1;
        while(l2<r2){
          int m2 = (l2+r2+1)/2;
          if(Seg.get_max(1,0,n-1,y,m2)<=r) l2=m2;
          else r2=m2-1;
        } 
        res[i]=(ll<=l2);
      }
    }
  }
  return res;
}

/*void _(){
 int n,m,q;
 cin >> n >> m >> q;

 for(int i=0;i<m;i++){
 	int a,b;
 	cin >> a >> b;
 	v[a].push_back(b);
 	v[b].push_back(a);
 }

 while(q--){
  int x,y,l,r;
  cin >> x >> y >> l >> r;
  Wvis.assign(n+5,0);
  Hvis.assign(n+5,0);
  dfs_h(x,l);
  dfs_w(y,r);
  bool ok=0;
  for(int i=0;i<n;i++) if(Wvis[i] && Hvis[i]) ok=1;
  cout << ok;
 }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 504 KB Output is correct
9 Correct 1 ms 336 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 504 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 170 ms 788 KB Output is correct
11 Correct 74 ms 592 KB Output is correct
12 Correct 23 ms 864 KB Output is correct
13 Correct 183 ms 592 KB Output is correct
14 Correct 85 ms 592 KB Output is correct
15 Correct 197 ms 1096 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 96 ms 19796 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 504 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 170 ms 788 KB Output is correct
11 Correct 74 ms 592 KB Output is correct
12 Correct 23 ms 864 KB Output is correct
13 Correct 183 ms 592 KB Output is correct
14 Correct 85 ms 592 KB Output is correct
15 Correct 197 ms 1096 KB Output is correct
16 Runtime error 96 ms 19796 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -