Submission #202257

#	Time	Username	Problem	Language	Result	Execution time	Memory
202257		MetB	Programming Contest (POI11_pro)	C++14	100 / 100	97 ms	3320 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 = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;
const int inf = 1e9;

int p[1000], u[1000], u_p[1000], bl[1000];
int cnt[1000], n, m, r, k, t, t_m, c, sum;
vector <int> g[1000];
vector < pair <int, int> > ans[1000];

bool kuhn (int x) {
	if (u[x] == t_m) return false;
	u[x] = t_m;

	for (int to : g[x]) {
		if (u_p[to] == t_m) continue;
		u_p[to] = t_m;
		if (p[to] == -1 || kuhn (p[to])) {
			p[to] = x;
			return true;
		}
	}

	return false;
}
 
int main () {
	ios::sync_with_stdio (false);
	cin >> n >> m >> r >> t >> k;
	memset (p, -1, m * sizeof (p[0]));
	for (int i = 0; i < k; i++) {
		int a, b;
		cin >> a >> b;
		g[a-1].push_back (b - 1);
	}

	for (int i = 0; i < min (m, t / r); i++) {
		for (int x = 0; x < n; x++) {
			if (bl[x]) continue;
			t_m++;
			bl[x] = !kuhn (x);
		}
	}

	for (int i = 0; i < m; i++) {
		if (p[i] != -1) {
			ans[p[i]].push_back ({i, cnt[p[i]] * r});
			cnt[p[i]]++;
			c++, sum += cnt[p[i]] * r;
		}
	}

	cout << c << ' ' << sum << endl;

	for (int i = 0; i < n; i++) {
		for (auto a : ans[i]) {
			cout << i + 1 << ' ' << a.first + 1 << ' ' << 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: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10