oj.uz

Submission #160642

# Submission time Handle Problem Language Result Execution time Memory
160642 2019-10-29T04:57:40 Z qkxwsm Teoretičar (COCI18_teoreticar) C++14
130 / 130
 6334 ms 119416 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 61440 KB Output is correct
2 Correct 88 ms 61432 KB Output is correct
3 Correct 63 ms 61436 KB Output is correct
4 Correct 57 ms 61432 KB Output is correct
5 Correct 57 ms 61512 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 61552 KB Output is correct
2 Correct 56 ms 61432 KB Output is correct
3 Correct 56 ms 61384 KB Output is correct
4 Correct 99 ms 61440 KB Output is correct
5 Correct 56 ms 61432 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 62200 KB Output is correct
2 Correct 65 ms 62004 KB Output is correct
3 Correct 68 ms 62328 KB Output is correct
4 Correct 60 ms 61780 KB Output is correct
5 Correct 60 ms 61724 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 62072 KB Output is correct
2 Correct 85 ms 61988 KB Output is correct
3 Correct 72 ms 62328 KB Output is correct
4 Correct 66 ms 61816 KB Output is correct
5 Correct 61 ms 61688 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1142 ms 95752 KB Output is correct
2 Correct 5235 ms 114180 KB Output is correct
3 Correct 1973 ms 117624 KB Output is correct
4 Correct 969 ms 101496 KB Output is correct
5 Correct 798 ms 90596 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 939 ms 95900 KB Output is correct
2 Correct 2047 ms 111760 KB Output is correct
3 Correct 3360 ms 118576 KB Output is correct
4 Correct 905 ms 101484 KB Output is correct
5 Correct 286 ms 70384 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3629 ms 107756 KB Output is correct
2 Correct 4166 ms 113444 KB Output is correct
3 Correct 253 ms 71552 KB Output is correct
4 Correct 1347 ms 100196 KB Output is correct
5 Correct 309 ms 88528 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1788 ms 100856 KB Output is correct
2 Correct 5744 ms 114176 KB Output is correct
3 Correct 3846 ms 118224 KB Output is correct
4 Correct 1380 ms 104940 KB Output is correct
5 Correct 968 ms 101460 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1702 ms 93512 KB Output is correct
2 Correct 6334 ms 114856 KB Output is correct
3 Correct 5104 ms 119416 KB Output is correct
4 Correct 1330 ms 104856 KB Output is correct
5 Correct 1381 ms 99436 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1793 ms 92864 KB Output is correct
2 Correct 6029 ms 114688 KB Output is correct
3 Correct 3726 ms 119160 KB Output is correct
4 Correct 347 ms 71664 KB Output is correct
5 Correct 1380 ms 98792 KB Output is correct