Submission #202249

#	Time	Username	Problem	Language	Result	Execution time	Memory
202249		MetB	Programming Contest (POI11_pro)	C++14	50 / 100	1099 ms	40444 KiB

pro

#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 = 1e9, MOD = 1e9 + 7, MOD2 = 1e6 + 3;
const int inf = 1e9;

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

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

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

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

int find_path () {
	fill (d, d + T + 1, INF);
	fill (u, u + T + 1, 0);
	d[S] = 0;
	for (int st = 0; st <= T; st++) {
		int x = -1;
		for (int 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 (int i = 0; i <= T; i++){
 		p[i] += d[i];
 		p[i] = min (p[i], (int) INF);
 	}

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

 	int x = T;
 	int 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;
}

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

	return s;
}

void add (int x, int to, int 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 () {
	ios::sync_with_stdio (false);
	cin >> n >> m >> r >> t >> k;

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

	T = n + m + 1;

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

	for (int i = 0; i < k; i++) {
		int 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';
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10