Submission #202257

# Submission time Handle Problem Language Result Execution time Memory
202257 2020-02-14T15:33:29 Z MetB Programming Contest (POI11_pro) C++14
100 / 100
97 ms 3320 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;

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';
		}
	}
}
# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 13 ms 504 KB Output is correct
2 Correct 13 ms 504 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 34 ms 888 KB Output is correct
2 Correct 33 ms 1528 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 80 ms 1016 KB Output is correct
2 Correct 25 ms 832 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 91 ms 1016 KB Output is correct
2 Correct 55 ms 1016 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 13 ms 504 KB Output is correct
2 Correct 18 ms 888 KB Output is correct
3 Correct 97 ms 1528 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 89 ms 1016 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 16 ms 504 KB Output is correct
2 Correct 68 ms 3320 KB Output is correct
3 Correct 5 ms 504 KB Output is correct