Submission #871579

#	Time	Username	Problem	Language	Result	Execution time	Memory
871579		KaleemRazaSyed	ICC (CEOI16_icc)	C++17	18 / 100	225 ms	856 KiB

icc

#include "icc.h"
#include<bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 105;
int dsu[MAXN];
vector<int> S[MAXN];
/*bool G[MAXN][MAXN], done[MAXN][MAXN];
int q;
int query(int size_a, int size_b, int a[], int b[])
{
  q++;
  for(int i = 0; i < size_a; i++)
    for(int j = 0; j < size_b; j++)
      if(G[a[i]][b[j]]) return 1;
  return 0;
}
 
void setRoad(int a, int b)
{
  if(done[a][b])
    {
      cout << "Found edge " << a << ' ' << b << " more than once\n";
      return;
    }
  if(G[a][b])
    {
      done[a][b] = done[b][a] = 1;
      cout << "Correctly Found edge " << a << ' ' << b << endl;
      return;
    }
  cout << "Wrong edge is Found " << a << ' ' << b << endl;
  }*/
 
 
 
void merge(int a,int b)
{
  int ra = dsu[a], rb = dsu[b];
  if(ra == rb) return;
  if(S[ra].size() > S[rb].size()) swap(ra, rb);
  for(int i : S[ra])
    {
      S[rb].push_back(i);
      dsu[i] = rb;
    }
  S[ra].resize(0);
}
 
pair<int,int> BS(vector<int> &v, int l, int r)
{
  if(r - l <= 1) return {-1, -1}; // Not enough nodes to form a pair
  int m = (r + l) / 2;
  pair<int,int> p = BS(v, l, m);
  if(p.first != -1)
    return p;
  
  p = BS(v, m, r);
  if(p.first != -1) 
      return p;
 
  vector<int> first_half, second_half;
  for(int i = l; i < m; i ++)
    for(int j : S[v[i]])
      first_half.push_back(j);
  
  int size_f = first_half.size();
  int F[size_f];
  for(int i = 0; i < size_f; i++)
    F[i] = first_half[i];
  
  // from the first half is there any edge to second half
  for(int i = m; i < r; i ++)
    for(int j : S[v[i]])
      second_half.push_back(j);
  
  int Sec[second_half.size()];
  
  for(int i = 0; i < second_half.size(); i++)
    Sec[i] = second_half[i];
 
  if(!query(size_f, second_half.size(), F, Sec))
    return p;
  
  int s = m, e = r;
  
  while(e - s > 1)
    {
      int mid = (e + s) / 2;
      int size_s = 0;
 
      for(int i = m; i < mid; i++) size_s += S[v[i]].size();
      if(query(size_f, size_s, F, Sec))
	e = mid;
      else
	s = mid;
    }
  
  int vertex = v[s];
  int size_s = S[v[s]].size();
  for(int i = 0; i < size_s; i++)
    Sec[i] = S[v[s]][i];
 
  s = l, e = m; // I know one of them have an edge to vertex[0];
        
  while(e - s > 1)
    {
      int mid = (e + s) / 2;
      int fsize = 0;
 
      for(int i = l; i < mid; i++)
	fsize += S[v[i]].size();
      
      if(query(size_s, fsize, Sec, F))
	e = mid;
      else
	s = mid;
    }
  p = {v[s], vertex};
  return p; // the roots are founded
}
 
void run(int n)
{
  for(int i = 1; i <= n; i++)
    dsu[i] = i, S[i].push_back(i);
 
  for(int i = 1; i < n; i ++)
    {
      vector<int> roots;
      for(int v = 1; v <= n; v++)
	if(dsu[v] == v)
	  roots.push_back(v);
 
      // which two commponents has now merged
      pair<int,int> p = BS(roots, 0, roots.size()); // returns a pair of roots that are merged
      int F[S[p.first].size()], Sec[S[p.second].size()];
      int sz1 = S[p.first].size(), sz2 = S[p.second].size();
      for(int i = 0; i < sz1; i ++)
	F[i] = S[p.first][i];
      for(int i = 0; i < sz2; i ++)
	Sec[i] = S[p.second][i];
 
      int l = 0, r = sz2;
      while(r - l > 1)
	{
	  int m = (l +  r) / 2;
	  if(query(sz1, m, F, Sec))
	    r = m;
	  else
	    l = m;
	}
      int a[] = {Sec[l]};
      l = 0, r = sz1;
      while(r - l > 1)
	{
	  int m = (l + r) / 2;
	  if(query(m, 1, F, a))
	    r = m;
	  else
	    l = m;
	}
      setRoad(a[0], F[l]);
      merge(a[0], F[l]);
    }
}
 
 
/*int main()
{
  int n;
  cin >> n;
  run(n);
  return 0;
  }*/

Compilation message (stderr)

icc.cpp: In function 'std::pair<int, int> BS(std::vector<int>&, int, int)':
icc.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for(int i = 0; i < second_half.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10