Submission #202249

# Submission time Handle Problem Language Result Execution time Memory
202249 2020-02-14T14:25:37 Z MetB Programming Contest (POI11_pro) C++14
50 / 100
1000 ms 40444 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 = 1e9, MOD = 1e9 + 7, MOD2 = 1e6 + 3;
const int inf = 1e9;

int n, m, r, k, t, p[2000], d[2000], u[2000], S, T;

vector < pair <int, int> > ans[2000];

struct edge {
int x, to, cap, cost;
int twin;
};

edge* pr[N];
vector <edge> g[N];

int find_path () {
fill (d, d + T + 1, INF);
fill (u, u + T + 1, 0);
d[S] = 0;
for (int st = 0; st <= T; st++) {
int x = -1;
for (int i = 0; i <= T; i++) {
if (!u[i] && (x == -1 || d[x] > d[i])) x = i;
}

u[x] = 1;
if (d[x] == INF) continue;
for (auto& e : g[x])
if (e.cap && d[e.to] > d[e.x] - p[e.to] + p[e.x] + e.cost) {
d[e.to] = d[e.x] - p[e.to] + p[e.x] + e.cost;
pr[e.to] = &e;
}
}

for (int i = 0; i <= T; i++){
p[i] += d[i];
p[i] = min (p[i], (int) INF);
}

if (!u[T] || d[T] == INF) return -INF;

int x = T;
int mn = INF, cost = 0;

while (x != S) {
mn = min (mn, pr[x] -> cap);
x = pr[x] -> x;
}

x = T;

while (x != S) {
pr[x] -> cap -= mn;
g[pr[x] -> to][pr[x] -> twin].cap += mn;
cost = pr[x] -> cost * mn;
x = pr[x] -> x;
}

return cost;
}

int mcmf () {
int a = 0, s = 0;
while ((a = find_path ()) != -INF) {
s += a;
}

return s;
}

void add (int x, int to, int cost) {
edge u, v;
u = {x, to, 1, cost, 0};
v = {to, x, 0, -cost, 0};
g[x].push_back (u);
g[to].push_back (v);
g[x][g[x].size () - 1].twin = g[to].size () - 1;
g[to][g[to].size () - 1].twin = g[x].size () - 1;
}

int main () {
ios::sync_with_stdio (false);
cin >> n >> m >> r >> t >> k;

for (int i = 1; i <= n; i++) {
for (int j = 0; j < min (m, t / r); j++)
add (0, i, j + 1);
}

T = n + m + 1;

for (int i = n + 1; i <= n + m; i++) {
}

for (int i = 0; i < k; i++) {
int a, b;
cin >> a >> b;
add (a, n + b, 0);
}

int s = 0, f = mcmf () * r;

for (int i = 1; i <= n; i++) {
int t = 0;
for (edge e : g[i]) {
if (!e.cap && e.to) {
ans[i].push_back ({e.to - n, t});
s++;
t += r;
}
}
}

cout << s << ' ' << f << endl;

for (int i = 1; i <= n; i++) {
for (auto a : ans[i])
cout << i << ' ' << a.first << ' ' << a.second << '\n';
}
}```

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 24 ms 23928 KB Output is correct

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23928 KB Output is correct

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24184 KB Output is correct
2 Correct 20 ms 23928 KB Output is correct

# Verdict Execution time Memory Grader output
1 Correct 113 ms 25208 KB Output is correct
2 Correct 112 ms 25080 KB Output is correct
3 Correct 34 ms 23928 KB Output is correct

# Verdict Execution time Memory Grader output
1 Correct 884 ms 29304 KB Output is correct
2 Correct 867 ms 29956 KB Output is correct
3 Correct 75 ms 24184 KB Output is correct

# Verdict Execution time Memory Grader output
1 Execution timed out 1097 ms 29432 KB Time limit exceeded
2 Halted 0 ms 0 KB -

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 29304 KB Time limit exceeded
2 Halted 0 ms 0 KB -

# Verdict Execution time Memory Grader output
1 Correct 977 ms 25208 KB Output is correct
2 Correct 41 ms 29304 KB Output is correct
3 Execution timed out 1076 ms 39800 KB Time limit exceeded