Submission #168401

#	Time	Username	Problem	Language	Result	Execution time	Memory
168401		Thuleanx	Programming Contest (POI11_pro)	C++14	0 / 100	38 ms	1656 KiB

pro

#include <bits/stdc++.h>
using namespace std;

// try for O(N^3) and pray it works
const int N = 507;
int n, m, r, t, k;
int p[N], assign[N], pr[N];
bool vis[N];
set<int> nxt[N];
vector<int> adj[2*N];

int dfs(int v, int src) {
	vis[v] = 1;	
	if (nxt[v].size() + 1 < nxt[src].size())
		return v;
	for (int w : nxt[v]) {
		for (int u : adj[w+N]) {
			if (u != v && !vis[u]) {
				pr[u] = w;
				int ans = dfs(u,src);
				if (ans>=0)
					return ans;
			}
		}
	}
	return -1;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin>>n>>m>>r>>t>>k;
	memset(assign, -1, sizeof(assign));
	for (int i = 0; i < k; i++) {
		int a, b; cin>>a>>b;
		adj[--a].push_back(--b+N);
		adj[N+b].push_back(a);
		if (assign[b] == -1) {
			assign[b] = a;
			nxt[a].insert(b);
		}
	}
	for (int i = 0; i < n; i++)
		p[i] = i;
	while (1) {
		sort(p, p+n, [](int i, int j) {
			return adj[i].size() > adj[j].size();
		});
		memset(vis, 0, sizeof(vis));
		memset(pr, -1, sizeof(pr));
		bool found = 0;
		for (int v : p) {
			int w = dfs(v, v);
			if (w != -1) {
				while (w != v) {
					// flip edges from w to assign[pr[w]]
					int task = pr[w];
					nxt[w].insert(task);
					nxt[assign[pr[w]]].erase(task);
					swap(assign[pr[w]], w);
				}
				found = 1;
				break;
			}
		}
		if (!found)
			break;
	}
	stringstream ss;
	long long ans = 0;
	int actual_cnt = 0;
	for (int i = 0; i < n; i++) {
		int cnt = 0;
		for (int x : nxt[i]) {
			if (++cnt*r <= t) {
				ss << i+1 << " " << x+1 << " " << (cnt-1)*r << endl;
				ans += cnt*r;
			}
		}
		actual_cnt++;
	}
	cout << actual_cnt << " " << ans << endl;
	cout << ss.str();

	return 0;
}

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