420C - Bug in Code - CodeForces Solution


data structures graphs implementation two pointers *1900

Please click on ads to support us..

C++ Code:

#include<iostream>
#include  <algorithm>
struct programmer
{
	long long y;
	long long x;
};
programmer p[300000];
long long vote[300000];
long long rp[300000];
long long py[300000];
long long result;
long long n;
long long m;
long long j;
bool predicate(programmer a, programmer b)
{
	if (a.x != b.x)
	{
		return a.x < b.x;
	}
	else
	{
		return a.y < b.y;
	}
}
int main()
{
	std::cin >> n >> m;
for (long long i = 1; i <= n; i++)
{
	std::cin >> p[i].x >> p[i].y;
	vote[p[i].x]++;
	vote[p[i].y]++;
	rp[p[i].x]++;
	rp[p[i].y]++;
	if (p[i].x > p[i].y)
		std::swap(p[i].y, p[i].x);
}
		std::sort(p + 1, p + 1 + n, predicate);
std::sort(rp + 1, rp + 1 + n);
long long start = 1;
for (long long i = 1; i <= n; i++)
{
	long long t = 0;
	long long vertex = 0;
	
	for (j = start; j <= n; j++)
    {
if (p[j].x != i)
{
	if (t != 0)
	{
		if (vote[i] + vote[vertex] - t < m && vote[i] + vote[vertex] >= m)
		{
			result -= 2;
		}
	}
	break;
}
if (j == start)
{
	vertex = p[j].y;
	t++;
}
else
{
	if (p[j].y == vertex)
	{
		t++;
	}
	else
	{
		if (vote[i] + vote[vertex] - t < m && vote[i] + vote[vertex] >= m)
		{
			result -= 2;
		}
		t = 1;
		vertex = p[j].y;
	}
}
    }
	if (j == n + 1)
{
	if (t != 0)
	{
		if (vote[i] + vote[vertex] - t < m && vote[i] + vote[vertex] >= m)
		{
			result -= 2;
		}
	}
}
start = j;
long long left=1;
long long right=n;
long long check =m - vote[i];
if (vote[i] * 2 >= m)
{
	result--;
}

while (left < right)
{
	long long mid = (left + right) / 2;
	if (rp[mid] < check)
	{
		left = mid + 1;
	}
	else
	{
		right = mid;
	}
}
if (rp[right] < check)
	right++;
result += n - right + 1;

}
std::cout << result / 2 << '\n';
    return 0;
}/*1698160193.2336645*/


Comments

Submit
0 Comments
More Questions

265A - Colorful Stones (Simplified Edition)
296A - Yaroslav and Permutations
967B - Watering System
152A - Marks
1398A - Bad Triangle
137A - Postcards and photos
1674D - A-B-C Sort
334A - Candy Bags
855A - Tom Riddle's Diary
1417A - Copy-paste
1038A - Equality
1061A - Coins
1676E - Eating Queries
1447A - Add Candies
1721D - Maximum AND
363C - Fixing Typos
1401A - Distance and Axis
658A - Bear and Reverse Radewoosh
1721E - Prefix Function Queries
977E - Cyclic Components
1140D - Minimum Triangulation
75C - Modified GCD
1722A - Spell Check
1722B - Colourblindness
1722D - Line
1722C - Word Game
1722G - Even-Odd XOR
552E - Vanya and Brackets
933A - A Twisty Movement
1722F - L-shapes