oj.uz

Submission #1111586

# Submission time Handle Problem Language Result Execution time Memory
1111586 2024-11-12T09:48:29 Z epicci23 Werewolf (IOI18_werewolf) C++17
15 / 100
 1239 ms 35184 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 = 200005;
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<3005){
	   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 2 ms 4944 KB Output is correct
2 Correct 2 ms 5116 KB Output is correct
3 Correct 2 ms 4944 KB Output is correct
4 Correct 2 ms 4944 KB Output is correct
5 Correct 2 ms 4944 KB Output is correct
6 Correct 2 ms 4944 KB Output is correct
7 Correct 2 ms 4944 KB Output is correct
8 Correct 2 ms 4944 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 5116 KB Output is correct
3 Correct 2 ms 4944 KB Output is correct
4 Correct 2 ms 4944 KB Output is correct
5 Correct 2 ms 4944 KB Output is correct
6 Correct 2 ms 4944 KB Output is correct
7 Correct 2 ms 4944 KB Output is correct
8 Correct 2 ms 4944 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 181 ms 5200 KB Output is correct
11 Correct 74 ms 5200 KB Output is correct
12 Correct 22 ms 5624 KB Output is correct
13 Correct 186 ms 5424 KB Output is correct
14 Correct 86 ms 5200 KB Output is correct
15 Correct 199 ms 5456 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 5116 KB Output is correct
3 Correct 2 ms 4944 KB Output is correct
4 Correct 2 ms 4944 KB Output is correct
5 Correct 2 ms 4944 KB Output is correct
6 Correct 2 ms 4944 KB Output is correct
7 Correct 2 ms 4944 KB Output is correct
8 Correct 2 ms 4944 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 181 ms 5200 KB Output is correct
11 Correct 74 ms 5200 KB Output is correct
12 Correct 22 ms 5624 KB Output is correct
13 Correct 186 ms 5424 KB Output is correct
14 Correct 86 ms 5200 KB Output is correct
15 Correct 199 ms 5456 KB Output is correct
16 Incorrect 1239 ms 35184 KB Output isn't correct
17 Halted 0 ms 0 KB -