test/aoj_2429.cpp

• View this file on GitHub
• Last update: 2024-05-10 22:05:31+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/2429

Depends on

• mincostflow_nega(最小費用流) (graph/mincostflow_nega.cpp)
• 2D-Array( $2$ 次元配列) (structure/2d_array.cpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2429

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

#include "graph/mincostflow_nega.cpp"
#include "structure/2d_array.cpp"

int main() {
	int N;
	cin >> N;
	v2d<int> W(N, N), E(N, N);
	v2d<char> mp(N, N);
	W.in();
	E.in();
	mp.in();
	mincostflow mcf(N + N + 2);
	int s = N + N, t = s + 1, ans = 0;

	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++) {
			if(mp[i][j] == 'o') {
				ans += E[i][j];
				mcf.add(i, N + j, 1, -E[i][j]);
			}
			else {
				mcf.add(i, N + j, 1, W[i][j]);
			}
		}
	for(int i = 0; i < N; i++) {
		mcf.add(s, i, 1, 0);
		mcf.add(N + i, t, 1, 0);
	}

	cout << ans + mcf.solve(s, t, N) << endl;

	auto stat = mcf.stat();
	queue<pair<int, int>> wr, er;
	for(int i = 0; i < stat.size(); i++) {
		if(stat[i].from == s || stat[i].to == t) continue;
		int from = stat[i].from, to = stat[i].to - N;
		if(stat[i].used_cap == 1) {
			if(mp[from][to] == '.') wr.push({from + 1, to + 1});
		}
		else {
			if(mp[from][to] == 'o') er.push({from + 1, to + 1});
		}
	}

	cout << wr.size() + er.size() << endl;
	while(!er.empty()) {
		int from = er.front().first, to = er.front().second;
		er.pop();
		cout << from << " " << to << " erase" << endl;
	}
	while(!wr.empty()) {
		int from = wr.front().first, to = wr.front().second;
		wr.pop();
		cout << from << " " << to << " write" << endl;
	}
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj_resolve/resolver.py", line 181, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 252, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 422, in update
    raise BundleErrorAt(
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: test/aoj_2429.cpp: line 9: found codes out of include guard

Test cases

Env	Name	Status	Elapsed	Memory
g++	testcase_00	AC	6 ms	3 MB
g++	testcase_01	AC	10 ms	4 MB
g++	testcase_02	AC	10 ms	4 MB
g++	testcase_03	AC	18 ms	4 MB
g++	testcase_04	AC	12 ms	4 MB
g++	testcase_05	AC	19 ms	4 MB
g++	testcase_06	AC	5 ms	4 MB
g++	testcase_07	AC	5 ms	3 MB
g++	testcase_08	AC	5 ms	3 MB
g++	testcase_09	AC	7 ms	4 MB
g++	testcase_10	AC	21 ms	5 MB
g++	testcase_11	AC	6 ms	4 MB
g++	testcase_12	AC	7 ms	4 MB
g++	testcase_13	AC	17 ms	4 MB
g++	testcase_14	AC	7 ms	4 MB
g++	testcase_15	AC	7 ms	4 MB
g++	testcase_16	AC	11 ms	4 MB
g++	testcase_17	AC	7 ms	4 MB
g++	testcase_18	AC	5 ms	3 MB
g++	testcase_19	AC	9 ms	4 MB
g++	testcase_20	AC	5 ms	3 MB
g++	testcase_21	AC	5 ms	3 MB
g++	testcase_22	AC	5 ms	3 MB
g++	testcase_23	AC	22 ms	5 MB
g++	testcase_24	AC	5 ms	3 MB
g++	testcase_25	AC	5 ms	3 MB
clang++	testcase_00	AC	6 ms	3 MB
clang++	testcase_01	AC	9 ms	4 MB
clang++	testcase_02	AC	10 ms	4 MB
clang++	testcase_03	AC	17 ms	4 MB
clang++	testcase_04	AC	11 ms	4 MB
clang++	testcase_05	AC	17 ms	5 MB
clang++	testcase_06	AC	5 ms	4 MB
clang++	testcase_07	AC	5 ms	3 MB
clang++	testcase_08	AC	5 ms	3 MB
clang++	testcase_09	AC	6 ms	4 MB
clang++	testcase_10	AC	19 ms	5 MB
clang++	testcase_11	AC	6 ms	4 MB
clang++	testcase_12	AC	7 ms	4 MB
clang++	testcase_13	AC	16 ms	4 MB
clang++	testcase_14	AC	7 ms	4 MB
clang++	testcase_15	AC	6 ms	4 MB
clang++	testcase_16	AC	10 ms	4 MB
clang++	testcase_17	AC	6 ms	3 MB
clang++	testcase_18	AC	5 ms	3 MB
clang++	testcase_19	AC	8 ms	4 MB
clang++	testcase_20	AC	5 ms	3 MB
clang++	testcase_21	AC	5 ms	3 MB
clang++	testcase_22	AC	5 ms	3 MB
clang++	testcase_23	AC	19 ms	5 MB
clang++	testcase_24	AC	5 ms	3 MB
clang++	testcase_25	AC	5 ms	3 MB

Back to top page