oj.uz

Submission #461040

# Submission time Handle Problem Language Result Execution time Memory
461040 2021-08-09T11:57:41 Z grt Teoretičar (COCI18_teoreticar) C++17
52 / 130
 2053 ms 262144 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 rec(int a, int b) {
	if(a == b) {
		for(int i = 1; i <= l; ++i) {
			col[V[i][0][0].ND] = a;
		}
		return;
	}
	//for(int i = 1; i <= l; ++i) {
		//cout << i << " " << 0 << ": ";
		//for(auto x : V[i][0]) cout << x.ST << " ";
		//cout << "\n";
	//}
	//for(int i = 1; i <= r; ++i) {
		//cout << i << " " << 1 << ": ";
		//for(auto x : V[i][1]) cout << x.ST << " ";
		//cout << "\n";
	//}
	//cout << "---\n";
	for(int i = 1; i <= l; ++i) {
		I[i][0] = 0;
		for(auto nbh : V[i][0]) {
			vis[nbh.ND] = false;
		}
	}
	for(int i = 1; i <= r; ++i) {
		I[i][1] = 0;
	}
	cycle.clear();
	for(int i = 1; i <= l; ++i) {
		eulerCycle(i, 0);
	}
	vi cyc = cycle;
	for(int i = 0; i < (int)cyc.size(); i += 2) {
		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 = 1; i <= l; ++i) {
		V[i][0].swap(V2[i][0]);
		V2[i][0].clear();
	}
	for(int i = 1; i <= r; ++i) {
		V[i][1].swap(V2[i][1]);
		V2[i][1].clear();
	}
	rec(a, (a + b)/2);
	for(int i = 1; i < (int)cyc.size(); i += 2) {
		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 = 1; i <= l; ++i) {
		V[i][0].swap(V2[i][0]);
		V2[i][0].clear();
	}
	for(int i = 1; i <= r; ++i) {
		V[i][1].swap(V2[i][1]);
		V2[i][1].clear();
	}
	rec((a+b)/2 + 1, b);
}

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});
		//cout << i << ": " << a << " " << b << "\n";
	}
	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;
	//cout << pt << "\n";
	int ptr = 1;
	nr = m;
	for(int i = 1; i <= l; ++i) {
		while(deg[i][0] != pt) {
			while(deg[ptr][1] == pt) ptr++;
			deg[ptr][1]++;
			deg[i][0]++;
			nr++;
			V[i][0].PB({ptr, nr});
			V[ptr][1].PB({i, nr});
			edge[nr] = {i, ptr};
			//cout << nr << ": " << i << " " << ptr << "\n";
		}
	}
	r = max(r, ptr);
	ptr = 1;
	for(int i = 1; i <= r; ++i) {
		while(deg[i][1] != pt) {
			while(deg[ptr][0] == pt) ptr++;
			deg[ptr][0]++;
			deg[i][1]++;
			nr++;
			V[i][1].PB({ptr, nr});
			V[ptr][0].PB({i, nr});
			edge[nr] = {ptr, i};
			//cout << nr << ": " << ptr << " " << i << "\n";
		}
	}
	l = max(l, ptr);
	for(int i = 1; i <= l; ++i) {
		assert(V[i][0].size() == pt);
	}
	for(int i = 1; i <= r; ++i) {
		assert(V[i][1].size() == pt);
	}
	rec(1, pt);
	cout << pt << "\n";
	for(int i = 1; i <= m; ++i) {
		assert(col[i] != 0);
		cout << col[i] << "\n";
	}
	
	
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from teoreticar.cpp:1:
teoreticar.cpp: In function 'int main()':
teoreticar.cpp:150:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  150 |   assert(V[i][0].size() == pt);
      |          ~~~~~~~~~~~~~~~^~~~~
teoreticar.cpp:153:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  153 |   assert(V[i][1].size() == pt);
      |          ~~~~~~~~~~~~~~~^~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 94152 KB Output is correct
2 Correct 52 ms 94264 KB Output is correct
3 Correct 51 ms 94332 KB Output is correct
4 Correct 52 ms 94212 KB Output is correct
5 Correct 54 ms 94184 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 94524 KB Output is correct
2 Correct 52 ms 94532 KB Output is correct
3 Correct 53 ms 94328 KB Output is correct
4 Correct 51 ms 94276 KB Output is correct
5 Correct 50 ms 94252 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 95676 KB Output is correct
2 Correct 61 ms 95844 KB Output is correct
3 Correct 99 ms 101688 KB Output is correct
4 Correct 54 ms 94788 KB Output is correct
5 Correct 57 ms 94808 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 741 ms 164244 KB Output is correct
2 Correct 60 ms 95836 KB Output is correct
3 Correct 104 ms 101580 KB Output is correct
4 Correct 56 ms 94976 KB Output is correct
5 Correct 54 ms 94660 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1014 ms 152448 KB Output is correct
2 Runtime error 785 ms 262144 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1040 ms 152592 KB Output is correct
2 Correct 2053 ms 194324 KB Output is correct
3 Runtime error 693 ms 262144 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 602 ms 262144 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1292 ms 173792 KB Output is correct
2 Runtime error 763 ms 262144 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 453 ms 262144 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 471 ms 262144 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -