oj.uz

Submission #871579

# Submission time Handle Problem Language Result Execution time Memory
871579 2023-11-11T06:52:46 Z KaleemRazaSyed ICC (CEOI16_icc) C++17
18 / 100
 225 ms 856 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 7 ms 604 KB Ok! 201 queries used.
2 Correct 7 ms 604 KB Ok! 199 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 604 KB Ok! 1799 queries used.
2 Correct 71 ms 604 KB Ok! 1707 queries used.
3 Correct 71 ms 616 KB Ok! 1727 queries used.

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 225 ms 616 KB Number of queries more than 4500 out of 2250
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 205 ms 616 KB Number of queries more than 4000 out of 2000
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 179 ms 620 KB Number of queries more than 3550 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 166 ms 856 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -