# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
92780 | Kastanda | Teoretičar (COCI18_teoreticar) | C++11 | 2487 ms | 52732 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int VR = 100005, N = VR * 7;
int n1, n2, m, ts, parity;
int A[N], B[N], C[N], P[N], M[N];
vector < int > Adj[VR * 2];
void DFS(int v)
{
while (Adj[v].size())
{
int id = Adj[v].back();
Adj[v].pop_back();
if (M[id]) continue;
M[id] = parity;
parity = - parity;
DFS(A[id] ^ B[id] ^ v);
}
}
void Solve(int l, int r)
{
int Mxd = 0;
if (r < l) return ;
for (int i = l; i <= r; i++)
{
Adj[A[P[i]]].pb(P[i]);
Adj[B[P[i]]].pb(P[i]);
Mxd = max({Mxd, (int)Adj[A[P[i]]].size(), (int)Adj[B[P[i]]].size()});
}
if (Mxd <= 1)
{
++ ts;
for (int i = l; i <= r; i++)
C[P[i]] = ts;
return ;
}
int _m = m; parity = 1;
int dum1 = n1 + n2 + 1, dum2 = dum1 + 1;
vector < int > V;
for (int i = l; i <= r; i++)
{
int v = A[P[i]], u = B[P[i]];
V.pb(v); V.pb(u);
if (Adj[v].size() & 1)
{
++ _m;
A[_m] = v;
B[_m] = dum2;
Adj[v].pb(_m);
Adj[dum2].pb(_m);
}
if (Adj[u].size() & 1)
{
++ _m;
A[_m] = dum1;
B[_m] = u;
Adj[dum1].pb(_m);
Adj[u].pb(_m);
}
}
V.pb(dum1); V.pb(dum2);
if (Adj[dum1].size() & 1)
{
++ _m;
A[_m] = dum1;
B[_m] = dum2;
Adj[dum1].pb(_m);
Adj[dum2].pb(_m);
}
for (int &v : V)
if (Adj[v].size())
DFS(v);
int nw = l;
for (int i = l; i <= r; i++)
if (M[P[i]] == 1)
swap(P[i], P[nw]), nw ++;
for (int i = l; i <= r; i++)
M[P[i]] = 0;
for (int i = m + 1; i <= _m; i++)
M[i] = 0;
Solve(l, nw - 1);
Solve(nw, r);
}
int main()
{
scanf("%d%d%d", &n1, &n2, &m);
for (int i = 1; i <= m; i++)
scanf("%d%d", &A[i], &B[i]),
B[i] += n1, P[i] = i;
Solve(1, m);
printf("%d\n", ts);
for (int i = 1; i <= m; i++)
printf("%d\n", C[i]);
return (0);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |