Submission #160642

#	Time	Username	Problem	Language	Result	Execution time	Memory
160642		qkxwsm	Teoretičar (COCI18_teoreticar)	C++14	130 / 130	6334 ms	119416 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 1300013

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;
bool col;
int need[MAXN];

void dfs(int u)
{
	while(!edge[u].empty())
	{
		int eid = edge[u].back(); edge[u].pop_back();
		if (vis[eid]) continue;
		vis[eid] = true;
		int v = edges[eid].fi ^ edges[eid].se ^ u;
		//see what color u or v needs
		color[eid] = col; col ^= 1;
		// net[u] += (2 * col - 1);
		// net[v] += (2 * col - 1);
		// cerr << u << ',' << col << endl << v << ',' << col << endl;
		// need[u] = (need[u] == -1 ? col ^ 1 : -1);
		// need[v] = (need[v] == -1 ? col ^ 1 : -1);
		// cerr << u << " -> " << v << ' ' << (b ^ 1) << endl;
		dfs(v);
	}
}

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};
		}
		vis[E] = false;
		E++;
	}
	if (deg[0] & 1)
	{
		deg[0]++; deg[N - 1]++;
		edge[0].PB(E);
		edge[N - 1].PB(E);
		edges[E] = {0, N - 1};
		vis[E] = false;
		E++;
	}
	for (int u : nodes) need[u] = -1;
	for (int u : nodes)
	{
		dfs(u);
		// assert((deg[u] & 1) == 0);
	}
	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};
		// cerr << u << " -> " << v + L << endl;
		deg[u]++; deg[v + L]++;
	}
	// cerr << L << ' ' << N << endl;
	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.
}

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