Submission #380853

#	Time	Username	Problem	Language	Result	Execution time	Memory
380853		sad	Werewolf (IOI18_werewolf)	C++14	15 / 100	3809 ms	184232 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
int n;const int N=3090;
int vis[N],wolf[N][N],human[N][N];
vector<int>v[N];
priority_queue<pair<int,int>>q;
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {

  n=N;
  for(int i=0;i<X.size();i++)
  {
      v[X[i]].pb(Y[i]);
      v[Y[i]].pb(X[i]);
  }
  for(int i=0;i<n;i++)
  {
      for(int j=0;j<n;j++)
      {
          wolf[i][j]=1e9;
          human[i][j]=-1;
      }
  }
  for(int i=0;i<n;i++)
  {
     memset(vis,0,sizeof vis);
      q.push({-i,i});
      while(!q.empty())
      {
          pair<int,int>x=q.top();
          q.pop();
          if(vis[x.se])continue;
          wolf[i][x.se]=-x.fi;
          wolf[x.se][i]=-x.fi;
          vis[x.se]=1;
          for(auto it:v[x.se])
          {
              if(vis[it])continue;
              if(min(x.fi,-it)<(-wolf[i][it]))continue;
              q.push({min(x.fi,-it),it});
              wolf[i][it]=min(x.fi,-it);
          }
      }
  }
  for(int i=0;i<n;i++)
  {
      memset(vis,0,sizeof vis);
      q.push({i,i});
      while(!q.empty())
      {
          pair<int,int>x=q.top();
          q.pop();
          if(vis[x.se])continue;
          human[i][x.se]=x.fi;
          human[x.se][i]=x.fi;
          vis[x.se]=1;
          for(auto it:v[x.se])
          {
              if(vis[it])continue;
              if(min(x.fi,it)<human[i][it])continue;
              q.push({min(x.fi,it),it});
              human[i][it]=min(x.fi,it);
          }
      }
  }
  for(int i=0;i<n;i++)
  {
      wolf[i][i]=i;
      human[i][i]=i;
  }
  vector<int>ans;
  int q=S.size();
  for(int i=0;i<q;i++)
  {
      int re=0;
      int s=S[i],e=E[i],l=L[i],r=R[i];
      if(s<l||e>r){ans.pb(0);continue;}
      for(int j=l;j<=r;j++)
      {
          if(human[s][j]<l||wolf[j][e]>r)continue;
          re=1;
      }
      if(re)
      {
          ans.pb(1);continue;
      }
      ans.pb(0);
  }
  return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
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:16:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   for(int i=0;i<X.size();i++)
      |               ~^~~~~~~~~

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