oj.uz

Submission #461227

# Submission time Handle Problem Language Result Execution time Memory
461227 2021-08-09T14:57:04 Z grt Teoretičar (COCI18_teoreticar) C++17
130 / 130
 5556 ms 194360 KB 
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 1000 * 1000 + 10;
int l, r, m;
int deg[nax][2];
pi edge[nax];
vector<pi> V[nax][2];
int I[nax][2];
bool vis[nax];
int col[nax];
int nr;

vi cycle;

void eulerCycle(int x, bool turn) {
	while(I[x][turn] < (int)V[x][turn].size()) {
		auto nbh = V[x][turn][I[x][turn]++];
		if(!vis[nbh.ND]) {
			vis[nbh.ND] = true;
			eulerCycle(nbh.ST, turn^1);
			cycle.PB(nbh.ND);
		}
	}
}

vector<pi>V2[nax][2];

void add(int a, int b) {
	nr++;
	V[a][0].PB({b, nr});
	V[b][1].PB({a, nr});
	edge[nr] = {a, b};
}
	

void rec(int a, int b, vi use_l, vi use_r) {
	if(a == b) {
		for(int i : use_l) {
			if((int)V[i][0].size() > 0) {
				col[V[i][0][0].ND] = a;
			}
		}
		return;
	}
	V[max(l,r) + 1][0].clear();
	V[max(l,r) + 1][1].clear();
	nr = m;
	for(int i : use_l) {
		I[i][0] = 0;
		if((int)V[i][0].size() % 2 == 1) {
			add(i, max(l,r) + 1);
		}
		for(auto nbh : V[i][0]) vis[nbh.ND] = false;
	}
	for(int i : use_r) {
		I[i][1] = 0;
		if((int)V[i][1].size() % 2 == 1) {
			add(max(l,r) + 1, i);
		}
	}
	I[max(l,r)+1][0] = I[max(l,r)+1][1] = 0;
	if((int)V[max(l,r) + 1][0].size() % 2 == 1) {
		add(max(l,r)+1, max(l,r)+1);
	}
	for(auto nbh : V[max(l,r) + 1][0]) vis[nbh.ND] = false;
	//for(int i : use_l) {
		//cout << i << ": ";
		//for(auto x : V[i][0]) cout << x.ST << " " << x.ND << ", ";
		//cout << "\n";
	//}
	//for(int i : {max(l,r)+1}) {
		//cout << i << ": ";
		//for(auto x : V[i][0]) cout << x.ST << " " << x.ND << ", ";
		//cout << "\n";
	//}
	cycle.clear();
	for(int i : use_l) {
		eulerCycle(i, 0);
	}
	eulerCycle(max(l,r) + 1, 0);
	vi cyc = cycle;
	//for(int c : cyc) {
		//cout << c << " ";
	//}
	//cout << "\n----\n";
	for(int i = 0; i < (int)cyc.size(); i += 2) {
		if(cyc[i] <= m) {
			V2[edge[cyc[i]].ST][0].PB({edge[cyc[i]].ND, cyc[i]});
			V2[edge[cyc[i]].ND][1].PB({edge[cyc[i]].ST, cyc[i]});
		}
	}
	vi ul = {}, ur = {};
	for(int i : use_l) {
		V[i][0].swap(V2[i][0]);
		if((int)V[i][0].size() > 0) ul.PB(i);
		V2[i][0].clear();
	}
	for(int i : use_r) {
		V[i][1].swap(V2[i][1]);
		if((int)V[i][1].size() > 0) ur.PB(i);
		V2[i][1].clear();
	}
	rec(a, (a + b) / 2, ul, ur);
	ul.clear();
	ur.clear();
	for(int i = 1; i < (int)cyc.size(); i += 2) {
		if(cyc[i] <= m) {
			V2[edge[cyc[i]].ST][0].PB({edge[cyc[i]].ND, cyc[i]});
			V2[edge[cyc[i]].ND][1].PB({edge[cyc[i]].ST, cyc[i]});
		}
	}
	for(int i : use_l) {
		V[i][0].swap(V2[i][0]);
		if((int)V[i][0].size() > 0) ul.PB(i);
		V2[i][0].clear();
	}
	for(int i : use_r) {
		V[i][1].swap(V2[i][1]);
		if((int)V[i][1].size() > 0) ur.PB(i);
		V2[i][1].clear();
	}
	rec((a + b) / 2 + 1, b, ul, ur);
}

int main() {
	cin >> l >> r >> m;
	for(int a, b, i = 1; i <= m; ++i) {
		cin >> a >> b;
		edge[i] = {a, b};
		deg[a][0]++;
		deg[b][1]++;
		V[a][0].PB({b, i});
		V[b][1].PB({a, i});
	}
	int mx = 0;
	for(int i = 1; i <= l; ++i) {
		mx = max(mx, deg[i][0]);	
	}
	for(int i = 1; i <= r; ++i) {
		mx = max(mx, deg[i][1]);	
	}
	int pt = 1;
	while(pt < mx) pt *= 2;
	vi a(l), b(r);
	for(int i = 0; i < l; ++i) a[i] = i + 1;
	for(int i = 0; i < r; ++i) b[i] = i + 1;
	rec(1, pt, a, b);
	cout << pt << "\n";
	for(int i = 1; i <= m; ++i) {
		cout << col[i] << "\n";
	}
	
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 94148 KB Output is correct
2 Correct 52 ms 94152 KB Output is correct
3 Correct 50 ms 94276 KB Output is correct
4 Correct 52 ms 94212 KB Output is correct
5 Correct 52 ms 94284 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 94252 KB Output is correct
2 Correct 51 ms 94276 KB Output is correct
3 Correct 50 ms 94180 KB Output is correct
4 Correct 52 ms 94148 KB Output is correct
5 Correct 52 ms 94152 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 95512 KB Output is correct
2 Correct 60 ms 95236 KB Output is correct
3 Correct 61 ms 95812 KB Output is correct
4 Correct 54 ms 94900 KB Output is correct
5 Correct 55 ms 94852 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 95300 KB Output is correct
2 Correct 59 ms 95184 KB Output is correct
3 Correct 62 ms 95940 KB Output is correct
4 Correct 55 ms 94896 KB Output is correct
5 Correct 54 ms 94676 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 929 ms 159156 KB Output is correct
2 Correct 4962 ms 191492 KB Output is correct
3 Correct 1713 ms 190076 KB Output is correct
4 Correct 897 ms 162464 KB Output is correct
5 Correct 688 ms 141916 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 936 ms 159224 KB Output is correct
2 Correct 1690 ms 187532 KB Output is correct
3 Correct 2823 ms 190024 KB Output is correct
4 Correct 896 ms 156824 KB Output is correct
5 Correct 200 ms 108888 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2996 ms 179132 KB Output is correct
2 Correct 3909 ms 194008 KB Output is correct
3 Correct 241 ms 111676 KB Output is correct
4 Correct 994 ms 157036 KB Output is correct
5 Correct 373 ms 133808 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1194 ms 166392 KB Output is correct
2 Correct 5067 ms 191804 KB Output is correct
3 Correct 3336 ms 192528 KB Output is correct
4 Correct 1199 ms 165560 KB Output is correct
5 Correct 936 ms 162316 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1168 ms 150656 KB Output is correct
2 Correct 5556 ms 194008 KB Output is correct
3 Correct 4477 ms 194360 KB Output is correct
4 Correct 1224 ms 165764 KB Output is correct
5 Correct 987 ms 155704 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1139 ms 150716 KB Output is correct
2 Correct 5404 ms 193576 KB Output is correct
3 Correct 3403 ms 194208 KB Output is correct
4 Correct 234 ms 110984 KB Output is correct
5 Correct 911 ms 155044 KB Output is correct