oj.uz

Submission #585896

# Submission time Handle Problem Language Result Execution time Memory
585896 2022-06-29T14:08:08 Z Koosha_mv Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 89608 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,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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 48852 KB Output is correct
2 Correct 23 ms 48828 KB Output is correct
3 Correct 23 ms 48840 KB Output is correct
4 Correct 22 ms 48852 KB Output is correct
5 Correct 23 ms 48824 KB Output is correct
6 Correct 25 ms 48936 KB Output is correct
7 Correct 24 ms 48852 KB Output is correct
8 Correct 25 ms 48852 KB Output is correct
9 Correct 25 ms 48920 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 48852 KB Output is correct
2 Correct 23 ms 48828 KB Output is correct
3 Correct 23 ms 48840 KB Output is correct
4 Correct 22 ms 48852 KB Output is correct
5 Correct 23 ms 48824 KB Output is correct
6 Correct 25 ms 48936 KB Output is correct
7 Correct 24 ms 48852 KB Output is correct
8 Correct 25 ms 48852 KB Output is correct
9 Correct 25 ms 48920 KB Output is correct
10 Correct 48 ms 49600 KB Output is correct
11 Correct 47 ms 49592 KB Output is correct
12 Correct 28 ms 49632 KB Output is correct
13 Correct 52 ms 49824 KB Output is correct
14 Correct 53 ms 49740 KB Output is correct
15 Correct 41 ms 49728 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 48852 KB Output is correct
2 Correct 23 ms 48828 KB Output is correct
3 Correct 23 ms 48840 KB Output is correct
4 Correct 22 ms 48852 KB Output is correct
5 Correct 23 ms 48824 KB Output is correct
6 Correct 25 ms 48936 KB Output is correct
7 Correct 24 ms 48852 KB Output is correct
8 Correct 25 ms 48852 KB Output is correct
9 Correct 25 ms 48920 KB Output is correct
10 Correct 48 ms 49600 KB Output is correct
11 Correct 47 ms 49592 KB Output is correct
12 Correct 28 ms 49632 KB Output is correct
13 Correct 52 ms 49824 KB Output is correct
14 Correct 53 ms 49740 KB Output is correct
15 Correct 41 ms 49728 KB Output is correct
16 Execution timed out 4035 ms 89608 KB Time limit exceeded
17 Halted 0 ms 0 KB -