#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
It was possible to solve 100 problems and you solved only 20. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
It was possible to solve 95 problems and you solved only 50. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
248 KB |
Your program calculated penalty of 12657708 points but it was possible to get no less than 72329760. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
632 KB |
It was possible to get penalty of 5478600 points and you received 11176344. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
1404 KB |
It was possible to solve 494 problems and you solved only 252. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
1528 KB |
Your program calculated penalty of 27179746 points but it was possible to get no less than 219191500. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
1488 KB |
Your program calculated penalty of 14066038 points but it was possible to get no less than 215009438. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
632 KB |
Your program assigned 500 problems but it was possible to solve only 390. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
1656 KB |
It was possible to get penalty of 500 points and you received 19671. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
760 KB |
Your program assigned 500 problems but it was possible to solve only 452. |
| 2 |
Halted |
0 ms |
0 KB |
- |
