oj.uz

Submission #972647

# Submission time Handle Problem Language Result Execution time Memory
972647 2024-04-30T19:27:41 Z NemanjaSo2005 Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 267108 KB 
#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;
}

Compilation message

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 35420 KB Output is correct
2 Correct 8 ms 35420 KB Output is correct
3 Correct 7 ms 35420 KB Output is correct
4 Correct 9 ms 35496 KB Output is correct
5 Correct 7 ms 35420 KB Output is correct
6 Correct 10 ms 35420 KB Output is correct
7 Correct 7 ms 35416 KB Output is correct
8 Correct 8 ms 35408 KB Output is correct
9 Correct 8 ms 35504 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 35420 KB Output is correct
2 Correct 8 ms 35420 KB Output is correct
3 Correct 7 ms 35420 KB Output is correct
4 Correct 9 ms 35496 KB Output is correct
5 Correct 7 ms 35420 KB Output is correct
6 Correct 10 ms 35420 KB Output is correct
7 Correct 7 ms 35416 KB Output is correct
8 Correct 8 ms 35408 KB Output is correct
9 Correct 8 ms 35504 KB Output is correct
10 Correct 22 ms 36956 KB Output is correct
11 Correct 21 ms 36964 KB Output is correct
12 Correct 30 ms 37468 KB Output is correct
13 Correct 20 ms 36956 KB Output is correct
14 Correct 18 ms 36956 KB Output is correct
15 Correct 23 ms 37240 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4075 ms 267108 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 35420 KB Output is correct
2 Correct 8 ms 35420 KB Output is correct
3 Correct 7 ms 35420 KB Output is correct
4 Correct 9 ms 35496 KB Output is correct
5 Correct 7 ms 35420 KB Output is correct
6 Correct 10 ms 35420 KB Output is correct
7 Correct 7 ms 35416 KB Output is correct
8 Correct 8 ms 35408 KB Output is correct
9 Correct 8 ms 35504 KB Output is correct
10 Correct 22 ms 36956 KB Output is correct
11 Correct 21 ms 36964 KB Output is correct
12 Correct 30 ms 37468 KB Output is correct
13 Correct 20 ms 36956 KB Output is correct
14 Correct 18 ms 36956 KB Output is correct
15 Correct 23 ms 37240 KB Output is correct
16 Execution timed out 4075 ms 267108 KB Time limit exceeded
17 Halted 0 ms 0 KB -