#include <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define MAXN 600013
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef pair<pii, pii> ppp;
int L, N, M, K, E;
pii edges[MAXN];
int deg[MAXN];
int ans[MAXN];
vi edge[MAXN];
vi nodes;
vi wtf[MAXN];
bitset<MAXN> vis, color;
void dfs(int u, bool b = true)
{
while(!edge[u].empty())
{
int eid = edge[u].back(); edge[u].pop_back();
if (vis[eid]) continue;
vis[eid] = true;
color[eid] = b; b ^= 1;
int v = edges[eid].fi ^ edges[eid].se ^ u;
// cerr << u << " -> " << v << ' ' << (b ^ 1) << endl;
dfs(v, b);
}
}
void solve(vi vec, int lvl)
{
// cerr << "SOLVE " << lvl << endl;
// for (int x : vec)
// {
// cerr << x << ' ';
// }
// cerr << endl;
if (lvl <= 0 || vec.empty()) return;
nodes.clear();
nodes.PB(0); nodes.PB(N - 1);
for (int idx : vec)
{
nodes.PB(edges[idx].fi); nodes.PB(edges[idx].se);
vis[idx] = false;
}
sort(ALL(nodes));
nodes.erase(unique(ALL(nodes)), nodes.end());
for (int u : nodes)
{
edge[u].clear();
deg[u] = 0;
}
for (int idx : vec)
{
edge[edges[idx].fi].PB(idx);
edge[edges[idx].se].PB(idx);
deg[edges[idx].fi]++; deg[edges[idx].se]++;
}
E = M;
for (int u : nodes)
{
if (!(deg[u] & 1)) continue;
if (u < L)
{
deg[u]++; deg[N - 1]++;
edge[u].PB(E);
edge[N - 1].PB(E);
edges[E] = {u, N - 1};
}
else
{
deg[u]++; deg[0]++;
edge[u].PB(E);
edge[0].PB(E);
edges[E] = {0, u};
}
E++;
}
if (deg[0] & 1)
{
deg[0]++; deg[N - 1]++;
edge[0].PB(E);
edge[N - 1].PB(E);
edges[E] = {0, N - 1};
}
for (int u : nodes)
{
dfs(u);
}
vi ch[2];
for (int x : vec)
{
ch[color[x]].PB(x);
// cerr << "AT level " << lvl << ' ' << x << " colored " << color[x] << endl;
}
solve(ch[0], lvl - 1);
solve(ch[1], lvl - 1);
for (int x : vec) ans[x] <<= 1;
for (int x : ch[1])
{
ans[x]++;
// cerr << "BIT " << lvl << " OF " << x << endl;
}
//find all the things rhr that should go on the left.
}
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cout << fixed << setprecision(10);
cerr << fixed << setprecision(4);
cin >> L >> N >> M; L++; N += L; N++;
FOR(i, 0, M)
{
int u, v;
cin >> u >> v; v--;
edges[i] = {u, v + L};
deg[u]++; deg[v + L]++;
}
FOR(i, 0, N)
{
ckmax(K, deg[i]);
deg[i] = 0;
}
K = (32 - __builtin_clz(K - 1));
// cerr << K << endl;
FOR(i, 0, M) nodes.PB(i);
solve(nodes, K);
nodes.clear();
FOR(i, 0, M) nodes.PB(ans[i]);
sort(ALL(nodes));
nodes.erase(unique(ALL(nodes)), nodes.end());
cout << SZ(nodes) << '\n';
FOR(i, 0, M)
{
ans[i] = LB(ALL(nodes), ans[i]) - nodes.begin();
cout << ans[i] + 1 << '\n';
wtf[edges[i].fi].PB(ans[i]);
wtf[edges[i].se].PB(ans[i]);
}
// FOR(i, 0, N)
// {
// for (int x : wtf[i])
// {
// cerr << x << ' ';
// }
// cerr << endl;
// }
//split edges into two colors.
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
28540 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
28536 KB |
Output is correct |
| 2 |
Correct |
27 ms |
28536 KB |
Output is correct |
| 3 |
Correct |
27 ms |
28536 KB |
Output is correct |
| 4 |
Correct |
27 ms |
28508 KB |
Output is correct |
| 5 |
Correct |
29 ms |
28664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
29432 KB |
Output is correct |
| 2 |
Correct |
35 ms |
29224 KB |
Output is correct |
| 3 |
Incorrect |
38 ms |
29544 KB |
not colored properly |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
29176 KB |
Output is correct |
| 2 |
Incorrect |
36 ms |
29148 KB |
not colored properly |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
944 ms |
68164 KB |
Output is correct |
| 2 |
Runtime error |
1004 ms |
175192 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1008 ms |
68140 KB |
Output is correct |
| 2 |
Runtime error |
1069 ms |
172380 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3234 ms |
82372 KB |
Output is correct |
| 2 |
Runtime error |
3265 ms |
175032 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1794 ms |
75868 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1689 ms |
66128 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1585 ms |
66216 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
