oj.uz

Submission #1111730

# Submission time Handle Problem Language Result Execution time Memory
1111730 2024-11-12T18:29:48 Z epicci23 Werewolf (IOI18_werewolf) C++17
100 / 100
 1562 ms 226460 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 INF = 1000000007;
const int N = 400005;
const int LOG = 20;

struct DSU{
  vector<int> par,siz,mini;
  DSU(int _n){
   par.resize(_n+5);
   iota(all(par),0);
   siz.assign(_n+5,1);
   mini.resize(_n+5);
   iota(all(mini),0);
  } 
  int find(int a){
    if(par[a]==a) return a;
    return par[a]=find(par[a]);
  }
  void merge(int a,int b){
    a=find(a),b=find(b);
    if(a==b) return;
    if(siz[a]>siz[b]) swap(a,b);
    par[a]=b;
    siz[b]+=siz[a];
  }
};

vector<int> v[N],human[N],wolf[N];
vector<int> hin(N,INF),hout(N,-INF),win(N,INF),wout(N,-INF);
int wift[N][LOG],hift[N][LOG],Tman[N],Twolf[N],hp,wp,ptr;

void hfs(int c){
  for(int i=1;i<LOG;i++) hift[c][i]=hift[hift[c][i-1]][i-1];

  if(!sz(human[c])){
    hout[c]=hin[c]=++ptr;
    return;
  }

  for(int x:human[c]){
    hift[x][0]=c;
    hfs(x);
    hin[c]=min(hin[c],hin[x]);
    hout[c]=max(hout[c],hout[x]);
  }
}

void wfs(int c){
  for(int i=1;i<LOG;i++) wift[c][i]=wift[wift[c][i-1]][i-1];
  
  if(!sz(wolf[c])){
    wout[c]=win[c]=++ptr;
    return;
  }

  for(int x:wolf[c]){
    wift[x][0]=c;
    wfs(x);
    win[c]=min(win[c],win[x]);
    wout[c]=max(wout[c],wout[x]);
  }
}

struct SegT{
  vector<vector<int>> seg;
  SegT(int _n){
    seg.resize(4*_n+5);
  }
  void add(int rt,int l,int r,int ind,int u){
    if(r<ind || l>ind) return;
    if(l==r){
      seg[rt].push_back(u);
      return;
    }
    int m=(l+r)/2;
    add(rt*2,l,m,ind,u),add(rt*2+1,m+1,r,ind,u);
    seg[rt].push_back(u);
  }
  int query(int rt,int l,int r,int gl,int gr,int bl,int br){
    if(r<gl || l>gr) return 0;
    if(l>=gl && r<=gr){
      int it = lower_bound(all(seg[rt]),bl) - seg[rt].begin();
      if(it<sz(seg[rt]) && seg[rt][it]<=br) return 1;
      return 0;
    }
    int m=(l+r)/2;
    return query(rt*2,l,m,gl,gr,bl,br) + query(rt*2+1,m+1,r,gl,gr,bl,br);
  }
};

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);
  }
  
  hp=n;
  DSU dsu(N),dsu2(N);

  for(int i=n-1;i>=0;i--){
    for(int x:v[i]){
      if(x>i){
        int A = dsu.find(i), B = dsu.find(x);
        if(A==B) continue;
        int parA = dsu.mini[A], parB = dsu.mini[B];
        dsu.merge(A,B);
        human[hp].push_back(parA);
        human[hp].push_back(parB);
        Tman[hp]=i;
        dsu.mini[dsu.find(A)]=hp++;
      }
    }
  }
 
  wp=n;
  for(int i=0;i<n;i++){
    for(int x:v[i]){
      if(x<i){
        int A = dsu2.find(i), B = dsu2.find(x);
        if(A==B) continue;
        int parA = dsu2.mini[A], parB = dsu2.mini[B];
        dsu2.merge(A,B);
        wolf[wp].push_back(parA);
        wolf[wp].push_back(parB);
        Twolf[wp]=i;
        dsu2.mini[dsu2.find(A)]=wp++;
      }
    }
  }
  
  wp--;hp--;
  for(int i=0;i<LOG;i++){
    wift[wp][i]=wp;
    hift[hp][i]=hp;
  }
  ptr=0;
  hfs(hp);
  ptr=0;
  wfs(wp);
  
  SegT T(N);

  for(int i=0;i<n;i++) T.add(1,1,n,hin[i],win[i]);
  for(int i=0;i<sz(T.seg);i++) sort(all(T.seg[i]));

  vector<int> res(q,0);
  for(int i=0;i<q;i++){
    int st = S[i], fn = E[i];
    for(int j=LOG-1;j>=0;j--){
      if(Tman[hift[st][j]] < L[i]) continue;
      st = hift[st][j];
    }
    for(int j=LOG-1;j>=0;j--){
      if(Twolf[wift[fn][j]] > R[i]) continue;
      fn = wift[fn][j];
    }
    if(T.query(1,1,n,hin[st],hout[st],win[fn],wout[fn])) res[i]=1;
    else res[i]=0;
  }


  return res;
}

/*void _(){
  int n,m,q;
  cin >> n >> m >> q;
 
 vector<int> U,W,_S,_E,_L,_R;

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

 while(q--){
  int x,y,l,r;
  cin >> x >> y >> l >> r;
  _S.push_back(x),_E.push_back(y);
  _L.push_back(l),_R.push_back(r);
 }

 vector<int> Ans=check_validity(n,U,W,_S,_E,_L,_R);
 
 for(int x:Ans) cout << x;
  cout << '\n';
}

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 61 ms 81736 KB Output is correct
2 Correct 62 ms 81736 KB Output is correct
3 Correct 47 ms 85876 KB Output is correct
4 Correct 63 ms 81748 KB Output is correct
5 Correct 65 ms 81736 KB Output is correct
6 Correct 50 ms 81744 KB Output is correct
7 Correct 50 ms 81876 KB Output is correct
8 Correct 43 ms 85928 KB Output is correct
9 Correct 46 ms 81736 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 81736 KB Output is correct
2 Correct 62 ms 81736 KB Output is correct
3 Correct 47 ms 85876 KB Output is correct
4 Correct 63 ms 81748 KB Output is correct
5 Correct 65 ms 81736 KB Output is correct
6 Correct 50 ms 81744 KB Output is correct
7 Correct 50 ms 81876 KB Output is correct
8 Correct 43 ms 85928 KB Output is correct
9 Correct 46 ms 81736 KB Output is correct
10 Correct 76 ms 83704 KB Output is correct
11 Correct 79 ms 83544 KB Output is correct
12 Correct 70 ms 83588 KB Output is correct
13 Correct 68 ms 83648 KB Output is correct
14 Correct 68 ms 83784 KB Output is correct
15 Correct 67 ms 83640 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1163 ms 201780 KB Output is correct
2 Correct 1126 ms 217868 KB Output is correct
3 Correct 1089 ms 212408 KB Output is correct
4 Correct 1025 ms 210692 KB Output is correct
5 Correct 1014 ms 210108 KB Output is correct
6 Correct 1055 ms 210228 KB Output is correct
7 Correct 1040 ms 210228 KB Output is correct
8 Correct 1173 ms 217776 KB Output is correct
9 Correct 795 ms 211096 KB Output is correct
10 Correct 779 ms 212032 KB Output is correct
11 Correct 741 ms 211888 KB Output is correct
12 Correct 780 ms 209964 KB Output is correct
13 Correct 949 ms 217652 KB Output is correct
14 Correct 1016 ms 219280 KB Output is correct
15 Correct 978 ms 217364 KB Output is correct
16 Correct 999 ms 219468 KB Output is correct
17 Correct 1056 ms 210484 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 81736 KB Output is correct
2 Correct 62 ms 81736 KB Output is correct
3 Correct 47 ms 85876 KB Output is correct
4 Correct 63 ms 81748 KB Output is correct
5 Correct 65 ms 81736 KB Output is correct
6 Correct 50 ms 81744 KB Output is correct
7 Correct 50 ms 81876 KB Output is correct
8 Correct 43 ms 85928 KB Output is correct
9 Correct 46 ms 81736 KB Output is correct
10 Correct 76 ms 83704 KB Output is correct
11 Correct 79 ms 83544 KB Output is correct
12 Correct 70 ms 83588 KB Output is correct
13 Correct 68 ms 83648 KB Output is correct
14 Correct 68 ms 83784 KB Output is correct
15 Correct 67 ms 83640 KB Output is correct
16 Correct 1163 ms 201780 KB Output is correct
17 Correct 1126 ms 217868 KB Output is correct
18 Correct 1089 ms 212408 KB Output is correct
19 Correct 1025 ms 210692 KB Output is correct
20 Correct 1014 ms 210108 KB Output is correct
21 Correct 1055 ms 210228 KB Output is correct
22 Correct 1040 ms 210228 KB Output is correct
23 Correct 1173 ms 217776 KB Output is correct
24 Correct 795 ms 211096 KB Output is correct
25 Correct 779 ms 212032 KB Output is correct
26 Correct 741 ms 211888 KB Output is correct
27 Correct 780 ms 209964 KB Output is correct
28 Correct 949 ms 217652 KB Output is correct
29 Correct 1016 ms 219280 KB Output is correct
30 Correct 978 ms 217364 KB Output is correct
31 Correct 999 ms 219468 KB Output is correct
32 Correct 1056 ms 210484 KB Output is correct
33 Correct 1359 ms 211128 KB Output is correct
34 Correct 320 ms 115440 KB Output is correct
35 Correct 1562 ms 217264 KB Output is correct
36 Correct 1308 ms 212792 KB Output is correct
37 Correct 1412 ms 214612 KB Output is correct
38 Correct 1330 ms 212160 KB Output is correct
39 Correct 1020 ms 226188 KB Output is correct
40 Correct 1169 ms 221624 KB Output is correct
41 Correct 1181 ms 215228 KB Output is correct
42 Correct 906 ms 212664 KB Output is correct
43 Correct 1471 ms 219564 KB Output is correct
44 Correct 1403 ms 216096 KB Output is correct
45 Correct 1166 ms 226460 KB Output is correct
46 Correct 1341 ms 226188 KB Output is correct
47 Correct 1057 ms 218228 KB Output is correct
48 Correct 974 ms 219460 KB Output is correct
49 Correct 1044 ms 219436 KB Output is correct
50 Correct 1099 ms 219460 KB Output is correct
51 Correct 1080 ms 222476 KB Output is correct
52 Correct 997 ms 223660 KB Output is correct