oj.uz

Submission #88087

# Submission time Handle Problem Language Result Execution time Memory
88087 2018-12-03T18:52:59 Z MAMBA Teoretičar (COCI18_teoreticar) C++17
130 / 130
 10855 ms 167348 KB 
#ifdef _MSC_VER
#define __builtin_popcount (int)__popcnt
#define __builtin_popcountll (int)__popcnt64
#define __builtin_clz (int)__lzcnt
#define $ system("pause")
#else
#define $
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> point;

#define MOD ll(1e9 + 7)
#define MAXN int(5e5 + 20)
#define lg 17
#define inf int(2e9 + 100)

#define rep(i, j, k) for (int i = j; i < k; i++)
#define for_all(x) x.begin(), x.end()
#define lid id << 1
#define rid id << 1 | 1
#define lch l, mid, lid
#define rch mid, r, rid
#define pb push_back
#define X first
#define Y second
#define re real()
#define im imag()

template <typename S, typename T>
inline ostream &operator<<(ostream &out, const pair<S, T> &p)
{
	return out << "( " << p.X << " , " << p.Y << " )";
}
template <typename S>
inline ostream &operator<<(ostream &out, const vector<S> &p)
{
	for (auto &e : p) out << e << ' '; return out;
}
template <typename T, typename S> inline T
smin(T &a, const S &b) { return a > b ? a = b : a; }
template <typename T, typename S> inline T
smax(T &a, const S &b) { return a < b ? a = b : a; }
inline double dot(const point l, const point r) { return l.re * r.re + l.im * r.im; }
inline double cross(const point l, const point r) { return l.re * r.im - l.im * r.re; }
ll po(ll v, ll u) { return u ? (po(v * v % MOD, u >> 1) * (u & 1 ? v : 1) % MOD) : 1; }
inline void add(ll &l, const ll &r) { l = (l + r) % MOD; }
ll gcd(ll v, ll u) { return u ? gcd(u, v % u) : v; }

int L, R, m, yal[MAXN], color[MAXN], supervec;
pii sar[MAXN * 2];
vector<int> adj[MAXN];
bool mark[MAXN * 2];
void tour(int v, int level) {
	while (!adj[v].empty()) {
		int e = adj[v].back();
		adj[v].pop_back();
		if (mark[e]) continue;
		mark[e] = true;
		if (v >= L && e < m) color[e] ^= (1 << level);
		tour(sar[e].X + sar[e].Y - v, level);
	}
	return;
}

void solve(int l , int r, int level = 0) {
	rep(i, l, r) {
		adj[sar[yal[i]].Y].pb(yal[i]);
		adj[sar[yal[i]].X].pb(yal[i]);
	}
	int Z = m;
	int mx = 0;
	rep(i, l, r) {
		int v = sar[yal[i]].X;
		int u = sar[yal[i]].Y;
		smax(mx, adj[v].size());
		smax(mx, adj[u].size());
		if ((int)adj[v].size() & 1) {
			adj[v].pb(Z);
			adj[supervec].pb(Z);
			sar[Z++] = { v , supervec };
		}
		if ((int)adj[u].size() & 1) {
			adj[u].pb(Z);
			adj[supervec].pb(Z);
			sar[Z++] = { u , supervec };
		}
	}
	if (mx < 2) {
		rep(i, l, r) {
			adj[sar[yal[i]].Y].clear();
			adj[sar[yal[i]].X].clear();
		}
		adj[supervec].clear();
		return;
	}
	rep(i, l, r)
		if (!adj[sar[yal[i]].X].empty())
			tour(sar[yal[i]].X, level);
	//
	rep(i, l, r) mark[yal[i]] = false;
	rep(i, m, Z) mark[i] = false;
	int lptr = l, rptr = r - 1;
	while (lptr != rptr) {
		if (color[yal[lptr]] & (1 << level))
			swap(yal[lptr], yal[rptr]), rptr--;
		else lptr++;
	}
	if (color[yal[lptr]] & (1 << level)) lptr--;
	lptr++;
	solve(l, lptr, level + 1);
	solve(lptr, r, level + 1);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> L >> R >> m;
	supervec = L + R;
	rep(i, 0, m) {
		int u, v;
		cin >> u >> v; u--; v--;
		v += L;
		sar[i] = { u , v };
		yal[i] = i;
	}
	solve(0, m);
	cout << *max_element(color, color + m) + 1 << '\n';
	rep(i, 0, m)
		cout << color[i] + 1 << '\n';
	$;
	return (0);
}

Compilation message

teoreticar.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<_Tp>&)':
teoreticar.cpp:47:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (auto &e : p) out << e << ' '; return out;
  ^~~
teoreticar.cpp:47:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (auto &e : p) out << e << ' '; return out;
                                     ^~~~~~
teoreticar.cpp: In instantiation of 'T smax(T&, const S&) [with T = int; S = long unsigned int]':
teoreticar.cpp:85:25:   required from here
teoreticar.cpp:52:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 smax(T &a, const S &b) { return a < b ? a = b : a; }
                                 ~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12280 KB Output is correct
2 Correct 15 ms 12280 KB Output is correct
3 Correct 14 ms 12336 KB Output is correct
4 Correct 14 ms 12448 KB Output is correct
5 Correct 14 ms 12448 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12448 KB Output is correct
2 Correct 14 ms 12496 KB Output is correct
3 Correct 14 ms 12516 KB Output is correct
4 Correct 14 ms 12516 KB Output is correct
5 Correct 14 ms 12636 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 13028 KB Output is correct
2 Correct 21 ms 13028 KB Output is correct
3 Correct 22 ms 13148 KB Output is correct
4 Correct 18 ms 13148 KB Output is correct
5 Correct 18 ms 13148 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 13148 KB Output is correct
2 Correct 20 ms 13148 KB Output is correct
3 Correct 23 ms 13496 KB Output is correct
4 Correct 19 ms 13496 KB Output is correct
5 Correct 18 ms 13496 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1004 ms 38072 KB Output is correct
2 Correct 6110 ms 54504 KB Output is correct
3 Correct 2090 ms 58368 KB Output is correct
4 Correct 1043 ms 58368 KB Output is correct
5 Correct 469 ms 58368 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 895 ms 61724 KB Output is correct
2 Correct 1919 ms 76404 KB Output is correct
3 Correct 2952 ms 82160 KB Output is correct
4 Correct 996 ms 82160 KB Output is correct
5 Correct 145 ms 82160 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2787 ms 88668 KB Output is correct
2 Correct 5223 ms 97908 KB Output is correct
3 Correct 131 ms 97908 KB Output is correct
4 Correct 830 ms 97908 KB Output is correct
5 Correct 270 ms 97908 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1268 ms 101600 KB Output is correct
2 Correct 8325 ms 115324 KB Output is correct
3 Correct 4347 ms 119184 KB Output is correct
4 Correct 1529 ms 119184 KB Output is correct
5 Correct 1083 ms 120908 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 878 ms 120908 KB Output is correct
2 Correct 10855 ms 139188 KB Output is correct
3 Correct 5108 ms 144168 KB Output is correct
4 Correct 1505 ms 144168 KB Output is correct
5 Correct 894 ms 144168 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 925 ms 144168 KB Output is correct
2 Correct 10256 ms 162800 KB Output is correct
3 Correct 4029 ms 167348 KB Output is correct
4 Correct 165 ms 167348 KB Output is correct
5 Correct 850 ms 167348 KB Output is correct