Submission #202245

# Submission time Handle Problem Language Result Execution time Memory
202245 2020-02-14T13:59:59 Z MetB Programming Contest (POI11_pro) C++14
0 / 100
1000 ms 65540 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[N], d[N], u[N], S, T;

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

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';
	}
}
# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 47480 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 47352 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 47612 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 124 ms 49656 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1055 ms 58488 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 58872 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 59000 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 987 ms 49912 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 63 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 50808 KB Time limit exceeded
2 Halted 0 ms 0 KB -