답안 #202246

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
202246 2020-02-14T14:00:57 Z MetB Programming Contest (POI11_pro) C++14
40 / 100
1000 ms 56432 KB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
 
using namespace std;
 
typedef long long ll;

const int N = 1e6 + 1;
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;
const int inf = 1e9;

ll n, m, r, k, t, p[2000], d[2000], u[2000], S, T;

vector < pair <int, int> > ans[2000];

struct edge {
	ll x, to, cap, cost;
	int twin;
};

edge* pr[N];
vector <edge> g[N];

ll find_path () {
	fill (d, d + T + 1, INF);
	fill (u, u + T + 1, 0);
	d[S] = 0;
	for (ll st = 0; st <= T; st++) {
		ll x = -1;
		for (ll i = 0; i <= T; i++) {
			if (!u[i] && (x == -1 || d[x] > d[i])) x = i;
		}

		u[x] = 1;
		if (d[x] == INF) continue;
		for (auto& e : g[x])
			if (e.cap && d[e.to] > d[e.x] - p[e.to] + p[e.x] + e.cost) {
				d[e.to] = d[e.x] - p[e.to] + p[e.x] + e.cost;
				pr[e.to] = &e;
			}
 	}

 	for (ll i = 0; i <= T; i++){
 		p[i] += d[i];
 	}

 	if (!u[T] || d[T] == INF) return -INF;

 	ll x = T;
 	ll mn = INF, cost = 0;

 	while (x != S) {
 		mn = min (mn, pr[x] -> cap);
 		x = pr[x] -> x;
 	}

 	x = T;

 	while (x != S) {
 		pr[x] -> cap -= mn;
 		g[pr[x] -> to][pr[x] -> twin].cap += mn;
 		cost = pr[x] -> cost * mn;
 		x = pr[x] -> x;
 	}

 	return cost;
}

ll mcmf () {
	ll a = 0, s = 0;
	while ((a = find_path ()) != -INF) {
		s += a;
	}

	return s;
}

void add (ll x, ll to, ll cost) {
	edge u, v;
	u = {x, to, 1, cost, 0};
	v = {to, x, 0, -cost, 0};
	g[x].push_back (u);
	g[to].push_back (v);
	g[x][g[x].size () - 1].twin = g[to].size () - 1;
	g[to][g[to].size () - 1].twin = g[x].size () - 1;
}
 
int main () {
	cin >> n >> m >> r >> t >> k;

	for (ll i = 1; i <= n; i++) {
		for (ll j = 0; j < min (m, t / r); j++)
			add (0, i, j + 1);
	}

	T = n + m + 1;

	for (ll i = n + 1; i <= n + m; i++) {
		add (i, T, 0);
	}

	for (ll i = 0; i < k; i++) {
		ll a, b;
		cin >> a >> b;
		add (a, n + b, 0);
	}

	int s = 0, f = mcmf () * r;

	for (int i = 1; i <= n; i++) {
		int t = 0;
		for (edge e : g[i]) {
			if (!e.cap && e.to) {
				ans[i].push_back ({e.to - n, t});
				s++;
				t += r;
			}
		}
	}

	cout << s << ' ' << f << endl;

	for (int i = 1; i <= n; i++) {
		for (auto a : ans[i])
			cout << i << ' ' << a.first << ' ' << a.second << '\n';
	}
}
# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 24056 KB Output is correct
2 Correct 23 ms 24056 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 24056 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 24184 KB Output is correct
2 Correct 20 ms 23928 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 26232 KB Output is correct
2 Correct 115 ms 26328 KB Output is correct
3 Correct 34 ms 23928 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1071 ms 34396 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1086 ms 34912 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1088 ms 34552 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 923 ms 26360 KB Output is correct
2 Runtime error 78 ms 35192 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1089 ms 56432 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1094 ms 27256 KB Time limit exceeded
2 Halted 0 ms 0 KB -