Submission #292111

#	Time	Username	Problem	Language	Result	Execution time	Memory
292111		Fasho	Werewolf (IOI18_werewolf)	C++14	15 / 100	4046 ms	30076 KiB

werewolf

#include <cstdio>
#include <cstdlib>
#include <vector>
#define NN 200005
#define ll long long int  
#define MP make_pair
#define pb push_back
#define ppb pop_back
#define sp " "
#define endl "\n"
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll>
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define fast2 freopen ("badhair.gir","r",stdin);freopen ("badhair.cik","w",stdout);
#define mod 1000000007
#define fs(x,y) for(ll i=1;i<=y;i++) cin>>x[i]
#define fo(i,x,y) for(ll i=x;i<=y;i++)
#define INF 1000000000005
#define ull unsigned long long int

using namespace std;

ll ans=0,m,n,q,mark1[NN],mark2[NN];

vector<int> v[NN];
void f1(int ind,int mn)
{
  if(mark1[ind])
    return;
  if(ind<mn)
    return;
  // printf("%d ", ind);
  mark1[ind]=1;
  for(int i=0;i<v[ind].size();i++)
  {
    ll x=v[ind][i];
    if(!mark1[x] && x>=mn)
      f1(x,mn);
  }
}
void f2(int ind,int mk)
{
  if(mark2[ind])
    return;
  if(ind>mk)
    return;
  if(mark1[ind])
    ans=1;
  // printf("%d ", ind);
  mark2[ind]=1;
  for(int i=0;i<v[ind].size();i++)
  {
    ll x=v[ind][i];
    if(!mark2[x] && x<=mk)
      f2(x,mk);
  }
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
  n=NN;
  m=X.size();
  q=S.size();

  fo(i,0,m-1)
  {
    int a=X[i];
    int b=Y[i];
    v[a].pb(b);
    v[b].pb(a);
  }
    
  std::vector<int> A(q);
  for (int i = 0; i < q; ++i) {
    fo(j,0,n-1)
      mark1[j]=0,mark2[j]=0;
    ans=0;
    // printf("[d1] %d\n", i);
    f1(S[i],L[i]);
    printf("\n");
    // printf("[d2] %d\n", i);
    f2(E[i],R[i]);
    // printf("\n\n");
    A[i]=ans;
  }
  return A;
}

// namespace {

// int read_int() {
//   int x;
//   if (scanf("%d", &x) != 1) {
//     fprintf(stderr, "Error while reading input\n");
//     exit(1);
//   }
//   return x;
// }

// }  // namespace

// int main() {
//   int N = read_int();
//   int M = read_int();
//   int Q = read_int();
//   std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
//   for (int j = 0; j < M; ++j) {
//     X[j] = read_int();
//     Y[j] = read_int();
//   }
//   for (int i = 0; i < Q; ++i) {
//     S[i] = read_int();
//     E[i] = read_int();
//     L[i] = read_int();
//     R[i] = read_int();
//   }

//   std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
//   for (size_t i = 0; i < A.size(); ++i) {
//     printf("%d\n", A[i]);
//   }
//   return 0;
// }

Compilation message (stderr)

werewolf.cpp: In function 'void f1(int, int)':
werewolf.cpp:36:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(int i=0;i<v[ind].size();i++)
      |               ~^~~~~~~~~~~~~~
werewolf.cpp: In function 'void f2(int, int)':
werewolf.cpp:53:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int i=0;i<v[ind].size();i++)
      |               ~^~~~~~~~~~~~~~

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