Submission #199647

#	Time	Username	Problem	Language	Result	Execution time	Memory
199647		ZwariowanyMarcin	Teoretičar (COCI18_teoreticar)	C++14	13 / 130	1397 ms	221184 KiB

teoreticar

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define LL long long
#define LD long double
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, j, n) for(int i = j; i <= n; ++i)
#define boost cin.tie(0), ios_base::sync_with_stdio(0);


using namespace std;			

const int nax = 2e5 + 111;

int L, R, m;
int a, b;

struct gao {
	int a, b, id;
};

vector <gao> x;
vector <gao> tyt;

int n;

int color = 1;

vector <pair<int, int>> v[nax];
int deg[nax];
int ans[nax];

bool odw[nax];
int wsk[nax];

void dfs(int u, int par = 0, int p = -1, int id = -1) {
	while (wsk[u] < ss(v[u])) {
		pair<int, int> it = v[u][wsk[u]];
		wsk[u]++;
		if (odw[it.se]) continue;
		odw[it.se] = 1;
		dfs(it.fi, (par + 1) % 2, u, it.se);
	}
	if (u > n || p > n || id == -1) return;
	tyt.pb({min(u, p), max(u, p), id});
}
	

void solve(vector <gao> y) {
	vector <gao> Left, Right;
	
	for (auto &it : y) 
		if (it.a > it.b) swap(it.a, it.b); 
	
	for (auto it : y) {
		deg[it.a]++;
		deg[it.b]++;
	}
	
	int MAX = 0;
	for (auto it : y) {
		MAX = max(MAX, deg[it.a]);
		MAX = max(MAX, deg[it.b]);
	}
	
	if (MAX == 1) {
		for (auto it : y) {
			ans[it.id] = color;
			deg[it.a] = 0;
			deg[it.b] = 0;
		}
		color++;
		return;
	}
	
	int nowe = m + 1;
	
	for (auto it : y) {
		v[it.a].pb({it.b, it.id});
		v[it.b].pb({it.a, it.id});
	}
	
	for (auto it : y) {
		if (ss(v[it.a]) % 2 == 1) {
			v[it.a].pb({n + 1, nowe});
			v[n + 1].pb({it.a, nowe++});
		}
		if (ss(v[it.b]) % 2 == 1) {
			v[it.b].pb({n + 2, nowe});
			v[n + 2].pb({it.b, nowe++});
		}
	}
	
	if (ss(v[n + 1]) % 2 == 1) {
		v[n + 1].pb({n + 2, nowe});
		v[n + 2].pb({n + 1, nowe++});
	}
	
	assert(ss(v[n + 1]) % 2 == 0);
	assert(ss(v[n + 2]) % 2 == 0);
	
	Left.clear();
	Right.clear();
	tyt.clear();
	
	for (auto it : y) {
		dfs(it.a);
		dfs(it.b);
	}
	dfs(n + 1);
	dfs(n + 2);
	
	for (int i = 0; i < ss(tyt); ++i) {
		if (tyt[i].b > n) continue;
		if (i & 1) Left.pb(tyt[i]);
		else Right.pb(tyt[i]);
	}
	
	/*cat(ss(y));
	for (auto it : y) {
		cat(it.a);
		cat(it.b);
		cat(it.id);
		printf ("\n");
	}
	printf ("\n");
	cat("L");
	for (auto it : Left)
		printf ("%d %d\n", it.a, it.b);
	cat("R");
	for (auto it : Right)
		printf ("%d %d\n", it.a, it.b);
	printf ("\n\n");
	*/	
	
	assert(ss(Left) > 0);
	assert(ss(Right) > 0);
			
	for (auto it : y) {
		v[it.a].clear();
		v[it.b].clear();
		wsk[it.a] = 0;
		wsk[it.b] = 0;
		deg[it.a] = 0;
		deg[it.b] = 0;
		odw[it.id] = 0;
	}
	
	v[n + 1].clear();
	v[n + 2].clear();
	wsk[n + 1] = 0;
	wsk[n + 2] = 0;
	for (int i = m + 1; i <= nowe; ++i)
		odw[i] = 0;
	
	solve(Left);
	solve(Right);
}
	

int main() {	
	scanf ("%d %d %d", &L, &R, &m);
	n = L + R;
	for (int i = 1; i <= m; ++i) {
		scanf ("%d%d", &a, &b);
		b += L;
		x.pb({a, b, i});
	}
	
	solve(x);
	
	printf ("%d\n", color - 1);
	for (int i = 1; i <= m; ++i)
		printf ("%d\n", ans[i]);
		
	
	return 0;
}

Compilation message (stderr)

teoreticar.cpp: In function 'int main()':
teoreticar.cpp:165:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %d %d", &L, &R, &m);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
teoreticar.cpp:168:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &a, &b);
   ~~~~~~^~~~~~~~~~~~~~~~

• 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