Submission #160636

#	Time	Username	Problem	Language	Result	Execution time	Memory
160636		qkxwsm	Teoretičar (COCI18_teoreticar)	C++14	13 / 130	2794 ms	66856 KiB

teoreticar

#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> 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();
	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();
	}
	for (int idx : vec)
	{
		edge[edges[idx].fi].PB(idx);
		edge[edges[idx].se].PB(idx);
	}
	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; 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.
}

• Subtask 1: 0 / 13
• Subtask 2: 13 / 13
• Subtask 3: 0 / 13
• Subtask 4: 0 / 13
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13
• Subtask 9: 0 / 13
• Subtask 10: 0 / 13