oj.uz

Submission #487702

# Submission time Handle Problem Language Result Execution time Memory
487702 2021-11-16T12:20:31 Z MathMate Teoretičar (COCI18_teoreticar) C++17
52 / 130
 12000 ms 99832 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 2e5 + 5;
const int MAX_ILOSC_KRAWEDZI = 5e5 + 5;
const int INF = 1e9 + 5;

struct Krawedz
{
	int sasiad, numer_krawedzi;
};

struct Cala_Krawedz
{
	int a, b, numer_krawedzi;

	bool operator < (const Cala_Krawedz& inny) const
	{
		return numer_krawedzi < inny.numer_krawedzi;
	}
};

vector <Krawedz> graf[MAX_N];

vector <Cala_Krawedz> zachowane_krawedzie(MAX_ILOSC_KRAWEDZI);

vector <int> ilosc_sasiadow(MAX_N);

vector <int> wierzcholki;

vector <bool> visited_krawedzie(MAX_ILOSC_KRAWEDZI);

vector <int> obecny_numer_krawedzi(MAX_N);

vector <int> numery_krawedzi_w_cyklu_Eulera;

void wyczysc()
{
	for(int i = 1; i < MAX_N; i++)
	{
		graf[i].clear();

		ilosc_sasiadow[i] = 0;

		obecny_numer_krawedzi[i] = 0;
	}

	for(int i = 0; i < MAX_ILOSC_KRAWEDZI; i++)
	{
		zachowane_krawedzie[i] = {0, 0, INF};

		visited_krawedzie[i] = false;
	}

	numery_krawedzi_w_cyklu_Eulera.clear();

	wierzcholki.clear();
}

void dodaj_krawedz(Cala_Krawedz& krawedz, int& numer_krawedzi)
{
	int a = krawedz.a;
	int b = krawedz.b;

	if(graf[a].empty())
	{
		wierzcholki.push_back(a);
	}

	if(graf[b].empty())
	{
		wierzcholki.push_back(b);
	}

	ilosc_sasiadow[a]++;
	ilosc_sasiadow[b]++;

	graf[a].push_back({b, numer_krawedzi});
	graf[b].push_back({a, numer_krawedzi});

	zachowane_krawedzie[numer_krawedzi] = krawedz;

	numer_krawedzi++;
}

void DFS(int v, int numer_poprzedniej_krawedzi)
{
	while(obecny_numer_krawedzi[v] < (int) graf[v].size())
	{
		const Krawedz krawedz = graf[v][obecny_numer_krawedzi[v]];

		int numer_krawedzi = krawedz.numer_krawedzi;
		int sasiad = krawedz.sasiad;

		obecny_numer_krawedzi[v]++;

		if(!visited_krawedzie[numer_krawedzi])
		{
			visited_krawedzie[numer_krawedzi] = true;

			DFS(sasiad, numer_krawedzi);
		}
	}

	if(numer_poprzedniej_krawedzi != INF)
	{
		numery_krawedzi_w_cyklu_Eulera.push_back(numer_poprzedniej_krawedzi);
	}
}

void policz_cykl_Eulera(int n_L, int n_R, int& numer_krawedzi, vector <Cala_Krawedz>& cykl_Eulera)
{
	for(auto& v : wierzcholki)
	{
		if(ilosc_sasiadow[v] % 2 != 0)
		{
			// jesli v jest jednym z dodanych wierzcholkow, to kontynuujemy
			if(v == 0 || v == n_L + n_R + 1)
			{
				continue;
			}

			if(v <= n_L)
			{
				Cala_Krawedz krawedz = {0, v, INF};

				dodaj_krawedz(krawedz, numer_krawedzi);
			}

			else
			{
				Cala_Krawedz krawedz = {v, n_L + n_R + 1, INF};

				dodaj_krawedz(krawedz, numer_krawedzi);
			}
		}
	}

	if(ilosc_sasiadow[0] % 2 != 0)
	{
		Cala_Krawedz krawedz = {0, n_L + n_R + 1, INF};

		dodaj_krawedz(krawedz, numer_krawedzi);
	}

	for(auto& v : wierzcholki)
	{
		// jesli nie odwiedzilem wszystkich sasiadow to puszczam
		if(obecny_numer_krawedzi[v] < (int) graf[v].size())
		{
			DFS(v, INF);
		}
	}

	for(auto& indeks_krawedzi : numery_krawedzi_w_cyklu_Eulera)
	{
		Cala_Krawedz krawedz = zachowane_krawedzie[indeks_krawedzi];

		cykl_Eulera.push_back(krawedz);
	}
}

void Divide_And_Conquer(vector <Cala_Krawedz>& krawedzie, vector <int>& odpowiedzi, int n_L, int n_R, int& kolor)
{
	wyczysc();

	int indeks_krawedzi = 0;

	for(auto& krawedz : krawedzie)
	{
		dodaj_krawedz(krawedz, indeks_krawedzi);
	}

	int max_ilosc_sasiadow = 0;

	for(int i = 1; i <= n_L + n_R; i++)
	{
		int rozmiar = (int) graf[i].size();

		max_ilosc_sasiadow = max(max_ilosc_sasiadow, rozmiar);
	}

	if(max_ilosc_sasiadow == 1)
	{
		kolor++;

		for(auto& krawedz : krawedzie)
		{
			int numer_krawedzi = krawedz.numer_krawedzi;

			odpowiedzi[numer_krawedzi] = kolor;
		}

		return;
	}

	vector <Cala_Krawedz> cykl_Eulera;

	policz_cykl_Eulera(n_L, n_R, indeks_krawedzi, cykl_Eulera);

	vector <Cala_Krawedz> krawedzie_L, krawedzie_R;

	for(int i = 0; i < (int) cykl_Eulera.size(); i++)
	{
		Cala_Krawedz krawedz = cykl_Eulera[i];

		int numer_krawedzi = krawedz.numer_krawedzi;

		if(numer_krawedzi == INF)
		{
			continue;
		}

		if(i % 2 == 0)
		{
			krawedzie_L.push_back(krawedz);
		}

		else
		{
			krawedzie_R.push_back(krawedz);
		}
	}

	Divide_And_Conquer(krawedzie_L, odpowiedzi, n_L, n_R, kolor);
	Divide_And_Conquer(krawedzie_R, odpowiedzi, n_L, n_R, kolor);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n_L, n_R, m;
	cin >> n_L >> n_R >> m;

	vector <Cala_Krawedz> krawedzie(m);

	for(int i = 0; i < m; i++)
	{
		int a, b, waga = i;
		cin >> a >> b;

		b += n_L;

		krawedzie[i] = {a, b, waga};
	}

	int kolor = 0;

	vector <int> odpowiedzi(m);

	Divide_And_Conquer(krawedzie, odpowiedzi, n_L, n_R, kolor);

	cout << kolor << "\n";

	for(auto& odp : odpowiedzi)
	{
		cout << odp << "\n";
	}

	return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 12492 KB Output is correct
2 Correct 60 ms 12532 KB Output is correct
3 Correct 33 ms 12552 KB Output is correct
4 Correct 18 ms 12524 KB Output is correct
5 Correct 33 ms 12492 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 12540 KB Output is correct
2 Correct 112 ms 12496 KB Output is correct
3 Correct 34 ms 12556 KB Output is correct
4 Correct 11 ms 12496 KB Output is correct
5 Correct 13 ms 12496 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 13864 KB Output is correct
2 Correct 66 ms 13792 KB Output is correct
3 Correct 82 ms 14104 KB Output is correct
4 Correct 22 ms 13132 KB Output is correct
5 Correct 22 ms 13148 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 951 ms 13908 KB Output is correct
2 Correct 67 ms 13768 KB Output is correct
3 Correct 72 ms 14332 KB Output is correct
4 Correct 38 ms 13316 KB Output is correct
5 Correct 75 ms 13136 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 77748 KB Output is correct
2 Runtime error 275 ms 78572 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 624 ms 78968 KB Output is correct
2 Runtime error 340 ms 77484 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 150 ms 67368 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 116 ms 64348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

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

Subtask #10
0 / 13.0

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