oj.uz

Submission #199651

# Submission time Handle Problem Language Result Execution time Memory
199651 2020-02-02T12:37:04 Z ZwariowanyMarcin Teoretičar (COCI18_teoreticar) C++17
130 / 130
 5530 ms 136940 KB 
#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 = 7e5 + 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 (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

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
13.0 / 13.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16888 KB Output is correct
2 Correct 15 ms 16760 KB Output is correct
3 Correct 14 ms 16760 KB Output is correct
4 Correct 14 ms 16760 KB Output is correct
5 Correct 16 ms 16888 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18168 KB Output is correct
2 Correct 23 ms 18040 KB Output is correct
3 Correct 22 ms 18384 KB Output is correct
4 Correct 17 ms 17528 KB Output is correct
5 Correct 19 ms 17528 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 18040 KB Output is correct
2 Correct 22 ms 17916 KB Output is correct
3 Correct 23 ms 18536 KB Output is correct
4 Correct 19 ms 17784 KB Output is correct
5 Correct 18 ms 17528 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 791 ms 91096 KB Output is correct
2 Correct 5180 ms 131148 KB Output is correct
3 Correct 1675 ms 133308 KB Output is correct
4 Correct 804 ms 94804 KB Output is correct
5 Correct 586 ms 82652 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 836 ms 91296 KB Output is correct
2 Correct 1697 ms 128204 KB Output is correct
3 Correct 2854 ms 134604 KB Output is correct
4 Correct 784 ms 98252 KB Output is correct
5 Correct 134 ms 36844 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2783 ms 121420 KB Output is correct
2 Correct 4019 ms 136940 KB Output is correct
3 Correct 174 ms 34028 KB Output is correct
4 Correct 732 ms 105188 KB Output is correct
5 Correct 205 ms 58204 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 960 ms 113208 KB Output is correct
2 Correct 5285 ms 136784 KB Output is correct
3 Correct 3241 ms 135116 KB Output is correct
4 Correct 1063 ms 112936 KB Output is correct
5 Correct 750 ms 100044 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 846 ms 93624 KB Output is correct
2 Correct 5362 ms 136732 KB Output is correct
3 Correct 4504 ms 136416 KB Output is correct
4 Correct 1004 ms 112916 KB Output is correct
5 Correct 689 ms 103784 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 874 ms 93924 KB Output is correct
2 Correct 5530 ms 135940 KB Output is correct
3 Correct 3554 ms 136780 KB Output is correct
4 Correct 161 ms 40548 KB Output is correct
5 Correct 678 ms 102784 KB Output is correct