oj.uz

Submission #1068980

# Submission time Handle Problem Language Result Execution time Memory
1068980 2024-08-21T14:02:47 Z Huseyn123 Werewolf (IOI18_werewolf) C++17
100 / 100
 867 ms 138996 KB 
#include "werewolf.h"
#include <bits/stdc++.h> 
#define MAX 200001
#define pb push_back
using namespace std; 
vector<int> f(vector<int> &a,vector<int> &b){
    int i,j;
    i=j=0;
    vector<int> res;
    while(i<(int)a.size() && j<(int)b.size()){
        if(a[i]<b[j]){
            res.pb(a[i]);
            i++;
        }
        else{
            res.pb(b[j]);
            j++;
        }
    }
    while(i<(int)a.size()){
        res.pb(a[i]);
        i++;
    }
    while(j<(int)b.size()){
        res.pb(b[j]);
        j++;
    }
    return res;
}
struct segtree{
    int size;
    vector<vector<int>> tree;
    void init(int n){
        size=1;
        while(size<n){
            size*=2;
        }
        tree.resize(2*size);
    }
    void build(vector<int> &a,int x,int lx,int rx){
        if(rx-lx==1){
            if(lx<(int)a.size()){
                tree[x]={a[lx]};
            }
            return;
        }
        int m=(lx+rx)/2;
        build(a,2*x+1,lx,m);
        build(a,2*x+2,m,rx);
        tree[x]=f(tree[2*x+1],tree[2*x+2]);
    }
    void build(vector<int> &a){
        build(a,0,0,size);
    }
    bool get_res(int l,int r,int x,int lx,int rx,int l1,int r1){
        if(lx>=r || rx<=l){
            return false;
        }
        if(lx>=l && rx<=r){
            auto it=lower_bound(tree[x].begin(),tree[x].end(),l1);
            if(it==tree[x].end() || *it>r1){
              return false;
            }
            return true;
        }
        int m=(lx+rx)/2;
        bool s1,s2;
        s1=get_res(l,r,2*x+1,lx,m,l1,r1);
        s2=get_res(l,r,2*x+2,m,rx,l1,r1);
        s1|=s2;
        return s1;
    }
    bool get_res(int l,int r,int l1,int r1){
        return get_res(l,r,0,0,size,l1,r1);
    }
};
struct DSU{
  vector<int> e,mx,mn;
  void init(int n){
    e.resize(n,-1);
    mx.resize(n); 
    mn.resize(n); 
    for(int i=0;i<n;i++){
      mn[i]=i; 
      mx[i]=i; 
    }
  }
  int get(int x){
    if(e[x]<0){
      return x;
    }
    return e[x]=get(e[x]);
  }
  int get_mn(int x){
    return mn[get(x)]; 
  }
  int get_mx(int x){
    return mx[get(x)]; 
  }
  bool unite(int x,int y){
    x=get(x); 
    y=get(y); 
    if(x==y) return false; 
    if(e[x]<e[y]){
      swap(x,y);
    }
    e[y]+=e[x];
    mx[y]=max(mx[y],mx[x]);
    mn[y]=min(mn[y],mn[x]);
    e[x]=y;
    return true;
  }
};
int bl1[MAX][20],bl2[MAX][20],in1[MAX],in2[MAX],out1[MAX],out2[MAX];
int tim=-1; 
vector<vector<int>> g,g1,g2;
void dfs1(int v){
  in1[v]=++tim; 
  for(auto x:g1[v]){
    if(in1[x]!=-1){
      continue;
    }
    dfs1(x);
  }
  out1[v]=tim;
}
void dfs2(int v){
  in2[v]=++tim; 
  for(auto x:g2[v]){
    if(in2[x]!=-1){
      continue;
    }
    dfs2(x);
  }
  out2[v]=tim;
}
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 Q = S.size();
  int M = X.size();
  g.clear(); 
  g.resize(N);
  g1.clear(); 
  g1.resize(N);
  g2.clear(); 
  g2.resize(N);
  vector<int> A(Q);
  for (int i = 0; i < Q; ++i) {
    A[i] = 0;
  }
  DSU dsu1,dsu2; 
  dsu1.init(N); 
  dsu2.init(N); 
  for(int i=0;i<M;i++){
    g[X[i]].push_back(Y[i]);
    g[Y[i]].push_back(X[i]);
  }
  for(int i=0;i<N;i++){
    bl1[i][0]=bl2[i][0]=in1[i]=in2[i]=-1;
  }
  for(int i=0;i<N;i++){
    for(auto x:g[i]){
      int h=dsu1.get_mx(x);
      if(x<i && dsu1.unite(i,x)){
        g1[i].push_back(h); 
        g1[h].push_back(i);
        bl1[h][0]=i;
      }
    }
  }
  for(int i=N-1;i>=0;i--){
    for(auto x:g[i]){
      int h=dsu2.get_mn(x);
      if(x>i && dsu2.unite(i,x)){ 
        g2[i].push_back(h); 
        g2[h].push_back(i);
        bl2[h][0]=i;
      }
    }
  }
  for(int i=1;i<20;i++){
    for(int j=0;j<N;j++){
      if(bl1[j][i-1]==-1){
         bl1[j][i]=-1;
      }
      else{
        bl1[j][i]=bl1[bl1[j][i-1]][i-1];
      }
      if(bl2[j][i-1]==-1){
         bl2[j][i]=-1;
      }
      else{
        bl2[j][i]=bl2[bl2[j][i-1]][i-1];
      }
    }
  }
  tim=-1;
  for(int i=N-1;i>=0;i--){
    if(in1[i]!=-1){
      continue; 
    }
    dfs1(i); 
  }
  tim=-1;
  for(int i=0;i<N;i++){
    if(in2[i]!=-1){
      continue; 
    }
    dfs2(i); 
  }
  vector<int> a(N); 
  for(int i=0;i<N;i++){
    a[in1[i]]=in2[i];
  }
  segtree st; 
  st.init(N); 
  st.build(a); 
  for(int i=0;i<Q;i++){
    for(int j=19;j>=0;j--){
      if(bl1[E[i]][j]!=-1 && bl1[E[i]][j]<=R[i]){
        E[i]=bl1[E[i]][j];
      }
    }
    for(int j=19;j>=0;j--){
      if(bl2[S[i]][j]!=-1 && bl2[S[i]][j]>=L[i]){
        S[i]=bl2[S[i]][j];
      }
    }
    A[i]=st.get_res(in1[E[i]],out1[E[i]]+1,in2[S[i]],out2[S[i]]);
  }
  return A;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 1 ms 6620 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 6 ms 7832 KB Output is correct
11 Correct 6 ms 7808 KB Output is correct
12 Correct 6 ms 7772 KB Output is correct
13 Correct 7 ms 8044 KB Output is correct
14 Correct 7 ms 8028 KB Output is correct
15 Correct 7 ms 8024 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 120240 KB Output is correct
2 Correct 711 ms 132332 KB Output is correct
3 Correct 693 ms 130024 KB Output is correct
4 Correct 571 ms 128936 KB Output is correct
5 Correct 565 ms 128820 KB Output is correct
6 Correct 604 ms 128684 KB Output is correct
7 Correct 510 ms 128816 KB Output is correct
8 Correct 633 ms 132260 KB Output is correct
9 Correct 536 ms 129968 KB Output is correct
10 Correct 415 ms 128940 KB Output is correct
11 Correct 431 ms 128812 KB Output is correct
12 Correct 495 ms 128940 KB Output is correct
13 Correct 611 ms 133544 KB Output is correct
14 Correct 754 ms 133356 KB Output is correct
15 Correct 581 ms 133552 KB Output is correct
16 Correct 597 ms 133608 KB Output is correct
17 Correct 464 ms 128748 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 1 ms 6620 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 6 ms 7832 KB Output is correct
11 Correct 6 ms 7808 KB Output is correct
12 Correct 6 ms 7772 KB Output is correct
13 Correct 7 ms 8044 KB Output is correct
14 Correct 7 ms 8028 KB Output is correct
15 Correct 7 ms 8024 KB Output is correct
16 Correct 514 ms 120240 KB Output is correct
17 Correct 711 ms 132332 KB Output is correct
18 Correct 693 ms 130024 KB Output is correct
19 Correct 571 ms 128936 KB Output is correct
20 Correct 565 ms 128820 KB Output is correct
21 Correct 604 ms 128684 KB Output is correct
22 Correct 510 ms 128816 KB Output is correct
23 Correct 633 ms 132260 KB Output is correct
24 Correct 536 ms 129968 KB Output is correct
25 Correct 415 ms 128940 KB Output is correct
26 Correct 431 ms 128812 KB Output is correct
27 Correct 495 ms 128940 KB Output is correct
28 Correct 611 ms 133544 KB Output is correct
29 Correct 754 ms 133356 KB Output is correct
30 Correct 581 ms 133552 KB Output is correct
31 Correct 597 ms 133608 KB Output is correct
32 Correct 464 ms 128748 KB Output is correct
33 Correct 597 ms 130028 KB Output is correct
34 Correct 251 ms 38124 KB Output is correct
35 Correct 840 ms 132588 KB Output is correct
36 Correct 623 ms 129624 KB Output is correct
37 Correct 867 ms 131732 KB Output is correct
38 Correct 670 ms 130032 KB Output is correct
39 Correct 836 ms 138680 KB Output is correct
40 Correct 660 ms 138216 KB Output is correct
41 Correct 616 ms 131160 KB Output is correct
42 Correct 416 ms 129488 KB Output is correct
43 Correct 833 ms 136424 KB Output is correct
44 Correct 672 ms 131696 KB Output is correct
45 Correct 559 ms 138996 KB Output is correct
46 Correct 632 ms 138728 KB Output is correct
47 Correct 567 ms 133612 KB Output is correct
48 Correct 564 ms 133552 KB Output is correct
49 Correct 601 ms 133608 KB Output is correct
50 Correct 589 ms 133536 KB Output is correct
51 Correct 523 ms 138732 KB Output is correct
52 Correct 540 ms 138732 KB Output is correct