oj.uz

Submission #1111606

# Submission time Handle Problem Language Result Execution time Memory
1111606 2024-11-12T09:58:41 Z epicci23 Werewolf (IOI18_werewolf) C++17
15 / 100
 1224 ms 35192 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 = 1000000007;
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.assign(n+5,0);
    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);
    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,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,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,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,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 4944 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 4944 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 172 ms 5424 KB Output is correct
11 Correct 86 ms 5368 KB Output is correct
12 Correct 22 ms 5476 KB Output is correct
13 Correct 185 ms 5424 KB Output is correct
14 Correct 86 ms 5368 KB Output is correct
15 Correct 204 ms 5676 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 1224 ms 35192 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 4944 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 172 ms 5424 KB Output is correct
11 Correct 86 ms 5368 KB Output is correct
12 Correct 22 ms 5476 KB Output is correct
13 Correct 185 ms 5424 KB Output is correct
14 Correct 86 ms 5368 KB Output is correct
15 Correct 204 ms 5676 KB Output is correct
16 Incorrect 1224 ms 35192 KB Output isn't correct
17 Halted 0 ms 0 KB -