oj.uz

Submission #585922

# Submission time Handle Problem Language Result Execution time Memory
585922 2022-06-29T14:45:37 Z Koosha_mv Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 120568 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,t){
      if(L[1][p[j]]>=x) break ;
      if(seg[j+t].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 33 ms 73940 KB Output is correct
2 Correct 35 ms 73976 KB Output is correct
3 Correct 36 ms 73916 KB Output is correct
4 Correct 33 ms 73952 KB Output is correct
5 Correct 36 ms 74004 KB Output is correct
6 Correct 34 ms 73940 KB Output is correct
7 Correct 42 ms 73932 KB Output is correct
8 Correct 36 ms 73984 KB Output is correct
9 Correct 38 ms 73976 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 73940 KB Output is correct
2 Correct 35 ms 73976 KB Output is correct
3 Correct 36 ms 73916 KB Output is correct
4 Correct 33 ms 73952 KB Output is correct
5 Correct 36 ms 74004 KB Output is correct
6 Correct 34 ms 73940 KB Output is correct
7 Correct 42 ms 73932 KB Output is correct
8 Correct 36 ms 73984 KB Output is correct
9 Correct 38 ms 73976 KB Output is correct
10 Correct 82 ms 74700 KB Output is correct
11 Correct 82 ms 74700 KB Output is correct
12 Correct 59 ms 74660 KB Output is correct
13 Correct 80 ms 74816 KB Output is correct
14 Correct 76 ms 74828 KB Output is correct
15 Correct 73 ms 74736 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 73940 KB Output is correct
2 Correct 35 ms 73976 KB Output is correct
3 Correct 36 ms 73916 KB Output is correct
4 Correct 33 ms 73952 KB Output is correct
5 Correct 36 ms 74004 KB Output is correct
6 Correct 34 ms 73940 KB Output is correct
7 Correct 42 ms 73932 KB Output is correct
8 Correct 36 ms 73984 KB Output is correct
9 Correct 38 ms 73976 KB Output is correct
10 Correct 82 ms 74700 KB Output is correct
11 Correct 82 ms 74700 KB Output is correct
12 Correct 59 ms 74660 KB Output is correct
13 Correct 80 ms 74816 KB Output is correct
14 Correct 76 ms 74828 KB Output is correct
15 Correct 73 ms 74736 KB Output is correct
16 Execution timed out 4014 ms 120568 KB Time limit exceeded
17 Halted 0 ms 0 KB -