oj.uz

Submission #585925

# Submission time Handle Problem Language Result Execution time Memory
585925 2022-06-29T14:47:03 Z Koosha_mv Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 120384 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=4e5+99;

int n,m,Time,par[N],pos[N],A[N],B[N],mark[N],st[2][N],ft[2][N],L[2][N],R[2][N];
pair<int,int> seg[N<<1];
vector<int> ans,ad[N],dl[N],adj[N],g[2][N];
vector<pair<int,int>> vec[2][N];

int getpar(int u){
  if(par[u]<0) return u;
  return par[u]=getpar(par[u]);
}
void merge(int u,int v,int s){
  u=getpar(u),v=getpar(v);
  if(u==v) return ;
  if(s^(u<v)) swap(u,v);
  par[u]+=par[v];
  par[v]=u;
}
void dfs(int u,int s){
  st[s][u]=Time++;
  for(auto v : g[s][u]){
    dfs(v,s);
  }
  ft[s][u]=Time;
}
void upd(int x,pair<int,int> val){
  seg[x+m]=val;
  for(x+=m;x>1;x>>=1){
    seg[x>>1]=max(seg[x],seg[x^1]);
  }
}
pair<int,int> get(int l,int r){
  pair<int,int> ans=mp(-1,0);
  for(l+=m,r+=m;l<r;l>>=1,r>>=1){
    if(l&1){
      maxm(ans,seg[l++]);
    }
    if(r&1){
      maxm(ans,seg[--r]);
    }
  }
  return ans;
}
vector<int> check_validity(int _n,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> C,vector<int> D){
  f(i,0,N<<1) seg[i].F=-1;
  n=_n,m=S.size();
  f(i,0,X.size()) adj[X[i]].pb(Y[i]),adj[Y[i]].pb(X[i]);
  fill(par,par+N,-1);
  f(i,0,m){
    ans.pb(0);
    swap(S[i],E[i]);
    L[0][i]=R[0][i]=L[1][i]=R[1][i]=n;
    vec[0][D[i]].pb({S[i],i});
    vec[1][C[i]].pb({E[i],i});
  }
  f(u,0,n){
    for(auto v : adj[u]){
      v=getpar(v);
      if(v<u){
        //cout<<u<<" -> "<<v<<endl;
        merge(u,v,0);
        g[0][u].pb(v);
      }
    }
    for(auto p : vec[0][u]){
      A[p.S]=getpar(p.F);
    }
  }
  fill(par,par+N,-1);
  f_(u,n-1,0){
    for(auto v : adj[u]){
      v=getpar(v);
      if(v>u){
        merge(u,v,1);
        g[1][u].pb(v);
      }
    }
    for(auto p : vec[1][u]){
      B[p.S]=getpar(p.F);
    }
  }
  dfs(n-1,0);
  Time=0,dfs(0,1);
  f(i,0,m){
    L[0][i]=st[0][A[i]];
    R[0][i]=ft[0][A[i]];
    L[1][i]=st[1][B[i]];
    R[1][i]=ft[1][B[i]];
  }
  f(i,0,n) A[st[0][i]]=i,B[st[1][i]]=i;
  /*dbga(A,0,n);
  dbga(B,0,n);
  f(i,0,t){
    cout<<L[0][i]<<" "<<R[0][i]<<endl;
    cout<<L[1][i]<<" "<<R[1][i]<<endl;
    cout<<endl;
  }*/
  vector<int> p(m);
  iota(all(p),0);
  sort(all(p),[&](int u,int v){ return L[1][u]<L[1][v]; });
  f(i,0,m) pos[p[i]]=i;
  f(i,0,m){
    ad[L[0][i]].pb(i);
    dl[R[0][i]].pb(i);
  }
  f(i,0,n){
    for(auto id : ad[i]) upd(pos[id],mp(R[1][id],id));
    for(auto id : dl[i]) upd(pos[id],mp(-1,id));
    int x=st[1][A[i]];
    //cout<<A[i]<<" -> "<<st[1][A[i]]<<endl;
    int l=-1,r=m,mid;
    while(l+1<r){
      int mid=(l+r)>>1;
      if(L[1][p[mid]]<=x) l=mid;
      else r=mid;
    }
    /*
    for(pair<int,int> P=get(0,r);P.F>x;P=get(0,r)){
      //erorp(P);
      ans[P.S]=1;
      upd(pos[P.S],mp(-1,P.S));
    }*/
    f(j,0,m){
      if(L[1][p[j]]>=x) break ;
      if(seg[j+m].F>x){
        ans[p[j]]=1;
        upd(j,mp(-1,-1));
      }
    }
    f(j,0,m){
      if(L[0][j]<=i && i<R[0][j] && L[1][j]<=x && x<R[1][j]){
        ans[j]=1;
      }
    }
  }
  return ans;
}
/*
6 6 3
3 0
3 1
3 4
1 2
2 5
5 1
4 2 1 2
4 2 2 2
5 4 3 4
*/

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   70 |   f(i,0,X.size()) adj[X[i]].pb(Y[i]),adj[Y[i]].pb(X[i]);
      |     ~~~~~~~~~~~~               
werewolf.cpp:70:3: note: in expansion of macro 'f'
   70 |   f(i,0,X.size()) adj[X[i]].pb(Y[i]),adj[Y[i]].pb(X[i]);
      |   ^
werewolf.cpp:134:18: warning: unused variable 'mid' [-Wunused-variable]
  134 |     int l=-1,r=m,mid;
      |                  ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 73932 KB Output is correct
2 Correct 35 ms 73904 KB Output is correct
3 Correct 34 ms 73980 KB Output is correct
4 Correct 35 ms 73976 KB Output is correct
5 Correct 37 ms 73892 KB Output is correct
6 Correct 35 ms 73956 KB Output is correct
7 Correct 34 ms 73880 KB Output is correct
8 Correct 37 ms 73940 KB Output is correct
9 Correct 34 ms 73932 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 73932 KB Output is correct
2 Correct 35 ms 73904 KB Output is correct
3 Correct 34 ms 73980 KB Output is correct
4 Correct 35 ms 73976 KB Output is correct
5 Correct 37 ms 73892 KB Output is correct
6 Correct 35 ms 73956 KB Output is correct
7 Correct 34 ms 73880 KB Output is correct
8 Correct 37 ms 73940 KB Output is correct
9 Correct 34 ms 73932 KB Output is correct
10 Correct 96 ms 74700 KB Output is correct
11 Correct 84 ms 74600 KB Output is correct
12 Correct 62 ms 74656 KB Output is correct
13 Correct 84 ms 74816 KB Output is correct
14 Correct 76 ms 74700 KB Output is correct
15 Correct 71 ms 74712 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4066 ms 120384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 73932 KB Output is correct
2 Correct 35 ms 73904 KB Output is correct
3 Correct 34 ms 73980 KB Output is correct
4 Correct 35 ms 73976 KB Output is correct
5 Correct 37 ms 73892 KB Output is correct
6 Correct 35 ms 73956 KB Output is correct
7 Correct 34 ms 73880 KB Output is correct
8 Correct 37 ms 73940 KB Output is correct
9 Correct 34 ms 73932 KB Output is correct
10 Correct 96 ms 74700 KB Output is correct
11 Correct 84 ms 74600 KB Output is correct
12 Correct 62 ms 74656 KB Output is correct
13 Correct 84 ms 74816 KB Output is correct
14 Correct 76 ms 74700 KB Output is correct
15 Correct 71 ms 74712 KB Output is correct
16 Execution timed out 4066 ms 120384 KB Time limit exceeded
17 Halted 0 ms 0 KB -