oj.uz

Submission #1041504

# Submission time Handle Problem Language Result Execution time Memory
1041504 2024-08-02T04:53:24 Z 제우스 (BOJ 30318)(#11052) Brought Down the Grading Server? (CEOI23_balance) C++17
0 / 100
 53 ms 34348 KB 
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define cr(v, n) (v).clear(), (v).resize(n);
using namespace std;
using lint = long long;
using pi = array<lint, 2>;

namespace euler_path {
vector<vector<pi>> gph;
vector<int> ptr, ans, vis;
void dfs(int x) {
	while (ptr[x] < sz(gph[x])) {
		auto [idx, z] = gph[x][ptr[x]++];
		dfs(z);
		ans.push_back(idx);
	}
}
void dfs2(int x) {
	while (ptr[x] < sz(gph[x])) {
		auto [idx, z] = gph[x][ptr[x]++];
		if (vis[idx >> 1])
			continue;
		vis[idx >> 1] = 1;
		dfs2(z);
		ans.push_back(idx);
	}
}

vector<int> solve_undirected(int n, vector<pi> edges) {
	if (sz(edges) == 0)
		return {};
	cr(gph, n);
	cr(ptr, n);
	cr(ans, 0);
	cr(vis, 2 * sz(edges));
	for (int i = 0; i < sz(edges); i++) {
		auto [u, v] = edges[i];
		gph[u].push_back({2 * i, v});
		gph[v].push_back({2 * i + 1, u});
	}
	int fixed = -1;
	int oddcnt = 0;
	for (int i = 0; i < n; i++) {
		if (sz(gph[i]) % 2 == 1) {
			oddcnt++;
			fixed = i;
		}
	}
	if (oddcnt > 2)
		return {};
	if (fixed == -1) {
		for (int i = 0; i < n; i++) {
			if (sz(gph[i])) {
				fixed = i;
				break;
			}
		}
	}
	dfs2(fixed);
	reverse(all(ans));
	if (sz(ans) != sz(edges))
		ans.clear();
	return ans;
}

} // namespace euler_path

vector<vector<int>> adj;

void solve(int l, int r, int t) {
	if (r - l == 1)
		return;
	vector<pi> edges;
	vector<int> deg(t);
	vector<int> ptr(sz(adj));
	for (int i = 0; i < sz(adj); i++) {
		for (int j = l; j < r; j += 2) {
			edges.push_back({adj[i][j], adj[i][j + 1]});
			deg[adj[i][j]]++;
			deg[adj[i][j + 1]]++;
		}
	}
	int ecnt = sz(edges);
	int uplast = -1;
	int m = (l + r) / 2;
	for (int i = 0; i < t; i++) {
		if (deg[i] % 2 == 1) {
			if (uplast == -1)
				uplast = i;
			else {
				edges.push_back({uplast, i});
				uplast = -1;
			}
		}
	}
	auto ans = euler_path::solve_undirected(t, edges);
	assert(sz(ans));
	for (auto &ed : ans) {
		if (ed >= 2 * ecnt)
			continue;
		if (ed % 2 == 0) {
			auto [u, v] = edges[ed / 2];
			int rw = ed / (r - l);
			adj[rw][l + ptr[rw]] = u;
			adj[rw][m + ptr[rw]] = v;
			ptr[rw]++;
		}
		if (ed % 2 == 1) {
			auto [v, u] = edges[ed / 2];
			int rw = ed / (r - l);
			adj[rw][l + ptr[rw]] = u;
			adj[rw][m + ptr[rw]] = v;
			ptr[rw]++;
		}
	}
	assert(count(all(ptr), m - l) == sz(ptr));
	solve(l, m, t);
	solve(m, r, t);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, s, t;
	cin >> n >> s >> t;
	cr(adj, n);
	for (auto &x : adj) {
		x.resize(s);
		for (auto &y : x) {
			cin >> y;
			y--;
		}
	}
	solve(0, s, t);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < s; j++) {
			cout << adj[i][j] + 1 << " ";
		}
		cout << "\n";
	}
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 0 ms 348 KB Correct

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 0 ms 344 KB Correct
4 Correct 0 ms 344 KB Correct
5 Runtime error 0 ms 604 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #2-1
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 28096 KB Correct
2 Correct 49 ms 29220 KB Correct
3 Correct 42 ms 24636 KB Correct
4 Correct 31 ms 24520 KB Correct
5 Correct 44 ms 29124 KB Correct
6 Correct 53 ms 29332 KB Correct
7 Runtime error 35 ms 34348 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #2-2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 28096 KB Correct
2 Correct 49 ms 29220 KB Correct
3 Correct 42 ms 24636 KB Correct
4 Correct 31 ms 24520 KB Correct
5 Correct 44 ms 29124 KB Correct
6 Correct 53 ms 29332 KB Correct
7 Runtime error 35 ms 34348 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #2-3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 0 ms 344 KB Correct
4 Correct 0 ms 344 KB Correct
5 Runtime error 0 ms 604 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #3-1
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Runtime error 4 ms 2652 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3-2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Runtime error 4 ms 2652 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3-3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Runtime error 4 ms 2652 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4-1
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 28096 KB Correct
2 Correct 49 ms 29220 KB Correct
3 Correct 42 ms 24636 KB Correct
4 Correct 31 ms 24520 KB Correct
5 Correct 44 ms 29124 KB Correct
6 Correct 53 ms 29332 KB Correct
7 Runtime error 35 ms 34348 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #4-2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 28096 KB Correct
2 Correct 49 ms 29220 KB Correct
3 Correct 42 ms 24636 KB Correct
4 Correct 31 ms 24520 KB Correct
5 Correct 44 ms 29124 KB Correct
6 Correct 53 ms 29332 KB Correct
7 Runtime error 35 ms 34348 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #4-3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 0 ms 348 KB Correct
4 Correct 0 ms 348 KB Correct
5 Correct 0 ms 344 KB Correct
6 Correct 0 ms 344 KB Correct
7 Runtime error 0 ms 604 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -