이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 500013
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;
pii edges[MAXN];
int deg[MAXN];
int ans[MAXN];
vi edge[MAXN];
vi nodes;
bitset<MAXN> alive, 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)
{
if (lvl <= 0 || vec.empty()) return;
// cerr << "SOLVE " << lvl << endl;
// for (int x : vec)
// {
// cerr << x << ' ';
// }
// cerr << endl;
nodes.clear();
for (int idx : vec)
{
nodes.PB(edges[idx].fi); nodes.PB(edges[idx].se);
alive[idx] = true;
}
sort(ALL(nodes));
nodes.erase(unique(ALL(nodes)), nodes.end());
for (int u : nodes)
{
edge[u].clear();
}
for (int idx : vec)
{
edge[edges[idx].fi].PB(idx);
edge[edges[idx].se].PB(idx);
vis[idx] = false;
}
for (int u : nodes)
{
if (!vis[u]) 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; N += L;
FOR(i, 0, M)
{
int u, v;
cin >> u >> v; u--; v--;
edges[i] = {u, v + L};
deg[u]++; deg[v + L]++;
}
FOR(i, 0, N)
{
ckmax(K, deg[i]);
}
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';
}
//split edges into two colors.
}
# | 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... |