oj.uz

답안 #168402

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
168402 2019-12-13T00:22:03 Z Thuleanx Programming Contest (POI11_pro) C++14
0 / 100
 38 ms 1528 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB It was possible to solve 100 problems and you solved only 56.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB It was possible to solve 95 problems and you solved only 82.

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 504 KB It was possible to solve 80 problems and you solved only 14.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 608 KB It was possible to solve 200 problems and you solved only 87.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 38 ms 1504 KB It was possible to solve 494 problems and you solved only 12.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 1528 KB It was possible to solve 500 problems and you solved only 43.
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 1492 KB It was possible to solve 500 problems and you solved only 27.
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 632 KB It was possible to solve 390 problems and you solved only 113.
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 1500 KB It was possible to get penalty of 500 points and you received 19671.
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 832 KB It was possible to solve 452 problems and you solved only 168.
2 Halted 0 ms 0 KB -