Submission #585896

#	Time	Username	Problem	Language	Result	Execution time	Memory
585896		Koosha_mv	Werewolf (IOI18_werewolf)	C++14	15 / 100	4035 ms	89608 KiB

werewolf

#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,t,Time,par[N],A[N],B[N],mark[N],st[2][N],ft[2][N],L[2][N],R[2][N];
vector<int> ans,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;
}
vector<int> check_validity(int _n,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> C,vector<int> D) {
  n=_n,t=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,t){
    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,t){
    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;
  }*/
  f(i,0,t){
    fill(mark,mark+n,0);
    f(j,L[0][i],R[0][i]){
      mark[A[j]]=1;
    }
    f(j,L[1][i],R[1][i]){
      if(mark[B[j]]){
        ans[i]=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 (stderr)

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++)
......
   50 |   f(i,0,X.size()) adj[X[i]].pb(Y[i]),adj[Y[i]].pb(X[i]);
      |     ~~~~~~~~~~~~               
werewolf.cpp:50:3: note: in expansion of macro 'f'
   50 |   f(i,0,X.size()) adj[X[i]].pb(Y[i]),adj[Y[i]].pb(X[i]);
      |   ^

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51