#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_ILOSC_KRAWEDZI);
vector <int> numery_krawedzi_w_cyklu_Eulera;
void wyczysc()
{
for(int i = 1; i < MAX_N; i++)
{
graf[i].clear();
ilosc_sasiadow[i] = 0;
}
for(int i = 0; i < MAX_ILOSC_KRAWEDZI; i++)
{
zachowane_krawedzie[i] = {0, 0, 0};
visited_krawedzie[i] = false;
obecny_numer_krawedzi[i] = 0;
}
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
13644 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
114 ms |
13764 KB |
too many colors |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
16328 KB |
too many colors |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1492 ms |
19148 KB |
too many colors |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2535 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2568 ms |
259324 KB |
too many colors |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
169 ms |
73708 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
128 ms |
70696 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4626 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
12024 ms |
154412 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
