제출 #972647

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
972647		NemanjaSo2005	늑대인간 (IOI18_werewolf)	C++17	15 / 100	4075 ms	267108 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,siz[maxn],rod1[maxn],vel1[maxn],rod[maxn][20],maks[maxn][20],in[maxn],out[maxn],vrem,dub[maxn];
int cpar[maxn];
bool blok[maxn];
vector<int> koji[maxn],graf[maxn];
struct grana{
   int a,b,w,id;
} grane[2*maxn];
bool cmp(grana a,grana b){
   return a.w>b.w;
}
int getpar1(int x){
   if(rod1[x]==x)
      return x;
   rod1[x]=getpar1(rod1[x]);
   return rod1[x];
}
bool spoj1(int a,int b){
   a=getpar1(a);
   b=getpar1(b);
   if(a==b)
      return false;
   if(vel1[a]>vel1[b])
      rod1[b]=a;
   else{
      rod1[a]=b;
      vel1[b]=max(vel1[a]+1,vel1[b]);
   }
   return true;
}
vector<pair<int,int>> stablo[maxn];
void dfs(int gde,int pret){
   dub[gde]=dub[pret]+1;
   in[gde]=++vrem;
   rod[gde][0]=pret;
   for(auto p:stablo[gde])
      if(p.f!=pret){
        // cout<<"MAKS OD "<<p.f<<" JE "<<p.s<<endl;
         maks[p.f][0]=p.s;
         dfs(p.f,gde);
      }
   out[gde]=vrem;
   return;
}
bool isparent(int a,int b){
   return in[a]<=in[b] and out[a]>=out[b];
}
int LCA(int a,int b){
   if(isparent(a,b))
      return a;
   if(isparent(b,a))
      return b;
   for(int i=17;i>=0;i--)
      if(!isparent(rod[a][i],b))
         a=rod[a][i];
   return rod[a][0];
}
int liftmax(int x,int d){
   int r=1e9;
   //cout<<"LIFT "<<x<<" "<<d<<" ";
   for(int i=17;i>=0;i--)
      if(d&(1<<i)){
         d-=(1<<i);
         r=min(r,maks[x][i]);
         x=rod[x][i];
      }
   //cout<<r<<endl;
   return r;
}
int getmax(int a,int b){
   int lc=LCA(a,b);
   //cout<<a<<" "<<b<<" "<<lc<<endl;
   int v1=liftmax(a,dub[a]-dub[lc]);
   int v2=liftmax(b,dub[b]-dub[lc]);
   return min(v1,v2);
}
int cdfs(int gde,int pret){
   siz[gde]=1;
   for(auto p:stablo[gde])
      if(p.f!=pret and !blok[p.f])
         siz[gde]+=cdfs(p.f,gde);
   return siz[gde];
}
int findcent(int gde,int pret,int vel){
   for(auto p:stablo[gde]){
      if(p.f==pret)
         continue;
      if(blok[p.f])
         continue;
      if(siz[p.f]>=vel)
         return findcent(p.f,gde,vel);
   }
   return gde;
}
void decompose(int gde,int pret){
   //cout<<"DECOMP "<<gde<<" "<<pret<<endl;
   cdfs(gde,gde);
   gde=findcent(gde,gde,siz[gde]/2+1);
   //cout<<"CENTROID JE "<<gde<<endl;
   cpar[gde]=pret;
   blok[gde]=true;
   for(auto p:stablo[gde])
      if(!blok[p.f])
         decompose(p.f,gde);
}
int dsrod[maxn];
map<int,int> mapa[maxn];
int getpar(int x){
   if(dsrod[x]==x)
      return x;
   dsrod[x]=getpar(dsrod[x]);
   return dsrod[x];
}
void spoj(int a,int b){
   a=getpar(a);
   b=getpar(b);
   if(a==b)
      return;
   if(mapa[b].size()>mapa[a].size())
      swap(a,b);
   dsrod[b]=a;
   for(auto it=mapa[b].begin();it!=mapa[b].end();it++)
      mapa[a][it->first]=max(mapa[a][it->first],it->second);
   mapa[b].clear();
   return;
}
int nadjimaks(map<int,int> &m,int kraj){
   int res=0;
   int c=kraj;
   while(c!=0){
      res=max(res,min(m[c],getmax(kraj,c)));
      c=cpar[c];
   }
   return res;
}
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++){
      rod1[i]=i;
      vel1[i]=1;
      dsrod[i]=i;
   }
   for(int i=0;i<M;i++){
      grane[i].a=X[i];
      grane[i].b=Y[i];
      grane[i].w=min(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++){
      if(!spoj1(grane[i].a,grane[i].b))
         continue;
      stablo[grane[i].a].push_back({grane[i].b,grane[i].w});
      stablo[grane[i].b].push_back({grane[i].a,grane[i].w});
   //   cout<<grane[i].a<<" "<<grane[i].b<<" "<<grane[i].w<<endl;
   }


   dub[1]=-1;
   dfs(1,1);
   maks[1][0]=1e9;
   for(int j=1;j<=17;j++)
      for(int i=1;i<=N;i++){
         rod[i][j]=rod[rod[i][j-1]][j-1];
         maks[i][j]=min(maks[i][j-1],maks[rod[i][j-1]][j-1]);
      }

  /* for(int i=1;i<=N;i++){
      for(int j=1;j<=N;j++)
         cout<<getmax(i,j)<<" ";
      cout<<endl;
   }*/

   decompose(1,0);

//   for(int i=1;i<=N;i++)
//      cout<<i<<": "<<cpar[i]<<endl;

   for(int i=1;i<=N;i++){
      int x=i;
      while(x){
         mapa[i][x]=getmax(i,x);
         x=cpar[x];
      }
   }

   for(int i=0;i<R.size();i++)
      koji[R[i]].push_back(i);
   for(int i=1;i<=N;i++){
      for(int x:graf[i])
         if(x<=i)
            spoj(x,i);

      for(int q:koji[i])
         ans[q]=nadjimaks(mapa[getpar(E[q])],S[q])>=L[q];
   }
   return ans;
}

컴파일 시 표준 에러 (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:146:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |    for(int i=0;i<S.size();i++){
      |                ~^~~~~~~~~
werewolf.cpp:152:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |    for(int i=0;i<X.size();i++){
      |                ~^~~~~~~~~
werewolf.cpp:208:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  208 |    for(int i=0;i<R.size();i++)
      |                ~^~~~~~~~~

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