Submission #972693

#	Time	Username	Problem	Language	Result	Execution time	Memory
972693		NemanjaSo2005	Werewolf (IOI18_werewolf)	C++17	100 / 100	515 ms	79996 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn=2e5+5;
int N,M,Q,rod[maxn],vel[maxn],in[maxn],out[maxn],vrem,rod2[maxn],vred[maxn];
vector<int> koji[maxn],graf[maxn];
vector<pair<int,int>> stablo[maxn];
set<int> SS[maxn];
struct grana{
   int a,b,w,id;
} grane[2*maxn];
bool cmp(grana a,grana b){
   return a.w<b.w;
}
int getp(int x){
   if(rod[x]==x)
      return x;
   return getp(rod[x]);
}
void spoj(int a,int b,int w){
   //cout<<a<<" "<<b<<endl;
   a=getp(a);
   b=getp(b);
   if(a==b)
      return;
   if(vel[b]>vel[a])
      swap(a,b);
   rod[b]=a;
   vred[b]=w;
   stablo[b].push_back({a,w});
   stablo[a].push_back({b,w});
   vel[a]=max(vel[a],vel[b]+1);
   //cout<<b<<" "<<a<<" "<<w<<endl;
   return;
}
void dfs(int gde,int pret){
   in[gde]=++vrem;
   for(auto x:stablo[gde])
      if(x.f!=pret)
         dfs(x.f,gde);
   out[gde]=vrem;
}
int getp2(int x){
   if(rod2[x]==x)
      return x;
   rod2[x]=getp2(rod2[x]);
   return rod2[x];
}
void spoj2(int a,int b){
   a=getp2(a);
   b=getp2(b);
   if(a==b)
      return;

   if(SS[a].size()<SS[b].size())
      swap(a,b);
   //cout<<"SPOJ 2  "<<a<<" "<<b<<endl;
   for(auto it=SS[b].begin();it!=SS[b].end();it++)
      SS[a].insert(*it);
   SS[b].clear();
   rod2[b]=a;
   return;
}
vector<int> check_validity(int NN, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R) {
   vector<int> ans(R.size(),0);
   N=NN;
   M=X.size();
   for(int i=0;i<S.size();i++){
      S[i]++;
      E[i]++;
      L[i]++;
      R[i]++;
   }
   for(int i=0;i<X.size();i++){
      X[i]++;
      Y[i]++;
   }
   for(int i=1;i<=N;i++){
      rod[i]=i;
      rod2[i]=i;
   }
   for(int i=0;i<M;i++){
      grane[i].a=X[i];
      grane[i].b=Y[i];
      grane[i].w=max(grane[i].a,grane[i].b);
      grane[i].id=i;
      graf[grane[i].a].push_back(grane[i].b);
      graf[grane[i].b].push_back(grane[i].a);
   }
   sort(grane,grane+M,cmp);
   for(int i=0;i<M;i++)
      spoj(grane[i].a,grane[i].b,grane[i].w);
/*
   for(int i=1;i<=N;i++){
      cout<<i<<": ";
      for(auto p:stablo[i])
         cout<<p.f<<" "<<p.s<<"   ";
      cout<<endl;
   }*/

   dfs(getp(1),getp(1));
   //for(int i=1;i<=N;i++)
    //  cout<<i<<": "<<in[i]<<" "<<out[i]<<endl;
   vred[getp(1)]=1e9;
 //  for(int i=1;i<=N;i++)
  //    cout<<i<<": "<<rod[i]<<endl;
   for(int i=1;i<=N;i++)
      SS[i].insert(in[i]);
   for(int i=0;i<L.size();i++){
      koji[L[i]].push_back(i);
   }
   for(int i=N;i>=1;i--){
      for(int x:graf[i])
         if(x>=i)
            spoj2(x,i);

      for(int q:koji[i]){
         int kraj=E[q];
         int poc=S[q];
         int r=R[q];
        // cout<<"R JE "<<r<<endl;
         while(vred[kraj]<=r){
         //   cout<<kraj<<" "<<vred[kraj]<<endl;
            kraj=rod[kraj];
         }
        // cout<<kraj<<" "<<vred[kraj]<<endl;
         int il=in[kraj];
         int ir=in[kraj];

        // cout<<kraj<<endl;

         if(stablo[kraj].size()){
            int dg=0,gg=stablo[kraj].size()-1,sred,ret=-1;
            while(dg<=gg){
               sred=(dg+gg)/2;
               if(stablo[kraj][sred].s<=r){
                  dg=sred+1;
                  ret=sred;
               }
               else
                  gg=sred-1;
            }
            if(ret!=-1)
               ir=out[stablo[kraj][ret].f];
         }

  //       cout<<il<<" "<<ir<<endl;

        /* cout<<"DODAO DO "<<i<<endl;
         cout<<poc<<" "<<getp2(poc)<<endl;
         for(auto it=SS[getp2(poc)].begin();it!=SS[getp2(poc)].end();it++)
            cout<<(*it)-1<<" ";
         cout<<endl;
*/
         auto it=SS[getp2(poc)].upper_bound(il-1);
         if(it!=SS[getp2(poc)].end())
            if((*it)<=ir)
               ans[q]=1;
      }
   }
   return ans;
}

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:71:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |    for(int i=0;i<S.size();i++){
      |                ~^~~~~~~~~
werewolf.cpp:77:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |    for(int i=0;i<X.size();i++){
      |                ~^~~~~~~~~
werewolf.cpp:112:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |    for(int i=0;i<L.size();i++){
      |                ~^~~~~~~~~

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