Submission #197918

#	Time	Username	Problem	Language	Result	Execution time	Memory
197918		nafis_shifat	Werewolf (IOI18_werewolf)	C++14	0 / 100	386 ms	26312 KiB

werewolf

#include<bits/stdc++.h>
#include "werewolf.h"
#define  pii pair<int,int>
#define f first
#define s second
using namespace std;
const int mxn=2e5+5;

struct edge
{
  int u,v;
  edge(int _,int __):u(_),v(__){};
};

vector<edge> g;
bool cmp1(edge a,edge b)
{
  return max(a.u,a.v)<max(b.u,b.v);
}

bool cmp2(edge a,edge b)
{
  return min(a.u,a.v)>min(b.u,b.v);
}

bool cmp3(pii a,pii b)
{
  return a>b;
}

int parent[mxn];

int findRep(int u)
{
  if(parent[u]==u)return u;
  return parent[u]=findRep(parent[u]);
}


void _union(int u,int v)
{
  u=findRep(u);
  v=findRep(v);
  parent[min(u,v)]=max(u,v);
}


vector<int> check_validity(int N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R)
{
  for(int i=0;i<=N;i++)parent[i]=i;
  pair<bool,bool> res[mxn];
  for(int i=0;i<X.size();i++)
  {
    g.push_back(edge(X[i],Y[i]));
  }


  vector<pii> tr;
  vector<pii> tl;
  for(int i=0;i<R.size();i++)
  {
    tr.push_back({R[i],i});
    tl.push_back({L[i],i});
  }

  sort(g.begin(),g.end(),cmp1);
  sort(tr.begin(),tr.end());

  int k=0;

  for(int i=0;i<tr.size();i++)
  {
    while(k<g.size() && max(g[k].u,g[k].v)<=tr[i].f)
    {
      _union(g[k].u,g[k].v);
      k++;
    }

    int q=tr[i].s;

    int p=findRep(E[q]);
    

    if(p>=L[q] && p<=R[q])
    {
      res[q]={true,false};
    }
    else
    {
      res[q]={false,false};
    }
    E[q]=p;




  }

   for(int i=0;i<=N;i++)parent[i]=i;

    sort(g.begin(),g.end(),cmp2);
    sort(tl.begin(),tl.end(),cmp3);


     k=0;
    for(int i=0;i<tr.size();i++)
    {
      while(k<g.size() && tl[i].f<=min(g[k].u,g[k].v))
      {
        _union(g[k].u,g[k].v);
        k++;
      }

      int q=tl[i].s;
      
   
      if(findRep(S[q])==findRep(E[q]))
      {
    
        res[q].s=true;
      }
    }
    vector<int> rs;

    for(int i=0;i<S.size();i++)
    {
      if(res[i].f && res[i].s)rs.push_back(1);
      else rs.push_back(0);

    }


    return rs;



}

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:52:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<X.size();i++)
               ~^~~~~~~~~
werewolf.cpp:60:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<R.size();i++)
               ~^~~~~~~~~
werewolf.cpp:71:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<tr.size();i++)
               ~^~~~~~~~~~
werewolf.cpp:73:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(k<g.size() && max(g[k].u,g[k].v)<=tr[i].f)
           ~^~~~~~~~~
werewolf.cpp:106:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tr.size();i++)
                 ~^~~~~~~~~~
werewolf.cpp:108:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while(k<g.size() && tl[i].f<=min(g[k].u,g[k].v))
             ~^~~~~~~~~
werewolf.cpp:125:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<S.size();i++)
                 ~^~~~~~~~~

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