Submission #1064837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064837		NemanjaSo2005	Friend (IOI14_friend)	C++17	0 / 100	5 ms	924 KiB

friend

#include "friend.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1005;
int N,niz[maxn],par[maxn];
int prosli[maxn],pvred,boja[maxn];
bool uparen[maxn];
vector<int> koji[2];
ll res=0;
mt19937_64 rng;
bool postoji[maxn][maxn];
void grana(int a,int b){
   postoji[a][b]=true;
   postoji[b][a]=true;
}
void dfs(int gde,int bb){
   //cout<<"NA "<<gde<<endl;
   koji[bb].push_back(gde);
   boja[gde]=bb;
   bb^=1;
   prosli[gde]=pvred;
   for(int x=1;x<=N;x++){
    //  cout<<x<<" "<<postoji[gde][x]<<endl;
      if(prosli[x]!=pvred and postoji[gde][x])
         dfs(x,bb);
   }
   return;
}
bool upari(int x){
   if(prosli[x]==pvred)
      return false;
   prosli[x]=pvred;
   for(int i=1;i<=N;i++){
      if(!postoji[i][x])
         continue;
      if(par[i]==0){
         par[i]=x;
         return true;
      }
      if(upari(par[i])){
         par[i]=x;
         return true;
      }
   }
   return false;
}
int calcmatching(){
   pvred++;
   dfs(1,1);
   //if(koji[0]>koji[1])
   //   swap(koji[0],koji[1]);
   //for(int i=1;i<koji[0].size();i++)
    //  swap(koji[0][i],koji[0][rng()%(i+1)]);
/*   for(int x:koji[0]){
      for(int i=1;i<=N;i++){
         if(!postoji[x][i])
            continue;
         if(par[i]!=0)
            continue;
         par[i]=x;
         uparen[x]=true;
         break;
      }
   }*/
   //cout<<koji[0].size()<<" sz "<<koji[1].size()<<endl;
   for(int x:koji[0]){
     // cout<<"POKUSAJ "<<x<<endl;
      if(uparen[x])
         continue;
      pvred++;
      uparen[x]=upari(x);
   }
   int br=0;
   for(int x:koji[0])
      if(uparen[x])
         br++;
   return br;
}
int findSample(int n,int confidence[],int host[],int protocol[]){
	N=n;
	rng.seed(52366);
	for(int i=1;i<=N;i++)
      niz[i]=confidence[i-1];
   for(int i=1;i<N;i++){
      int x=host[i]+1;
      int p=protocol[i];
      if(p==1 or p==2){
         for(int aa=1;aa<=i;aa++)
            if(postoji[x][aa])
               grana(aa,i+1);
      }
      if(p==0 or p==2)
         grana(x,i+1);
   }

	return N-calcmatching();
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31