#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/extc++.h>
#define owo(i,a, b) for(auto i=(a);i<(b); ++i)
#define uwu(i,a, b) for(auto i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<ttgl, null_type,less<ttgl>, rb_tree_tag,tree_order_statistics_node_update>*/
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 62;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const double PI = acos(-1);
const double eps = 1e-10;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
template<typename T, typename C>
struct MCMF{
static constexpr T eps = (T) 1e-9;
struct edge{
int from, to;
T c, f;
C cost;
};
vector<vector<int> > g;
vector<edge> edges;
vector<C> d;
vector<bool> in_queue;
vector<int> q, pe;
int n, source, sink;
T flow;
C cost;
MCMF(int n, int source, int sink): n(n), source(source), sink(sink), g(n), d(n), in_queue(n), pe(n){
assert(0 <= source && source < n && 0 <= sink && sink < n && source != sink);
flow = cost = 0;
}
void clear_flow(){
for(const edge &e: edges) e.f = 0;
flow = 0;
}
void add(int from, int to, T forward_cap, C cost, T backward_cap = 0){
assert(0 <= from && from < n && 0 <= to && to < n);
g[from].push_back((int) edges.size());
edges.push_back({from, to, forward_cap, 0, cost});
g[to].push_back((int) edges.size());
edges.push_back({to, from, backward_cap, 0, -cost});
}
bool expath(){
fill(d.begin(), d.end(), numeric_limits<C>::max());
q.clear();
q.push_back(source);
d[source] = 0;
in_queue[source] = true;
int beg = 0;
bool found = false;
while(beg < q.size()){
int i = q[beg ++];
if(i == sink) found = true;
in_queue[i] = false;
for(int id : g[i]){
const edge &e = edges[id];
if(e.c - e.f > eps && d[i] + e.cost < d[e.to]){
d[e.to] = d[i] + e.cost;
pe[e.to] = id;
if(!in_queue[e.to]){
q.push_back(e.to);
in_queue[e.to] = true;
}
}
}
}
if(found){
T push = numeric_limits<T>::max();
int v = sink;
while(v != source){
const edge &e = edges[pe[v]];
push = min(push, e.c - e.f);
v = e.from;
}
v = sink;
while(v != source){
edge &e = edges[pe[v]];
e.f += push;
edge &back = edges[pe[v] ^ 1];
back.f -= push;
v = e.from;
}
flow += push;
cost += push * d[sink];
}
return found;
}
pair<T, C> Flow(){
while(expath()){ }
return {flow, cost};
}
};
//easy flow?
const int mxN = 501;
int n, m, r, t, k;
int cnt[mxN];
int main() {
//freopen("file.in", "r", stdin);
//freopen("file.out", "w", stdout);
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
cin.tie(0)->sync_with_stdio(0);
cin>>n>>m>>r>>t>>k;
int most = min(t/r, m);
int a, b;
int src = n + m;
int dest = n + m + 1;
MCMF<int, ll> G(2 + n + m, src, dest);
owo(i, 0, n) {
owo(j, 0, most) {
G.add(src, i, 1, (j+1)*r);
}
}
owo(i, 0, k) {
cin>>a>>b;
a--; b--;
G.add(a, b + n, 1, 0);
}
owo(i, 0, m) {
G.add(i + n, dest, 1, 0);
}
pair<int, ll> ans = G.Flow();
cout<<ans.first<<" "<<ans.second<<"\n";
memset(cnt, 0, sizeof(cnt));
owo(i, 0, n) {
for(auto e: G.g[i]) {
if(G.edges[e].to >= n && G.edges[e].to < n + m && G.edges[e].f > 0) {
cout<<(i + 1)<<" "<<(G.edges[e].to - n + 1)<<" "<<(cnt[i]++)*r<<"\n";
}
}
}
return 0;
}
Compilation message
pro.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
2 | #pragma GCC optimization ("O3")
|
pro.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
3 | #pragma GCC optimization ("unroll-loops")
|
pro.cpp: In instantiation of 'MCMF<T, C>::MCMF(int, int, int) [with T = int; C = long long int]':
pro.cpp:123:41: required from here
pro.cpp:41:17: warning: 'MCMF<int, long long int>::sink' will be initialized after [-Wreorder]
41 | int n, source, sink;
| ^~~~
pro.cpp:36:23: warning: 'std::vector<std::vector<int> > MCMF<int, long long int>::g' [-Wreorder]
36 | vector<vector<int> > g;
| ^
pro.cpp:44:2: warning: when initialized here [-Wreorder]
44 | MCMF(int n, int source, int sink): n(n), source(source), sink(sink), g(n), d(n), in_queue(n), pe(n){
| ^~~~
pro.cpp: In instantiation of 'bool MCMF<T, C>::expath() [with T = int; C = long long int]':
pro.cpp:105:9: required from 'std::pair<_T1, _T2> MCMF<T, C>::Flow() [with T = int; C = long long int]'
pro.cpp:137:32: required from here
pro.cpp:67:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | while(beg < q.size()){
| ~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| 2 |
Correct |
2 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
640 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
2192 KB |
Output is correct |
| 2 |
Correct |
37 ms |
2192 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
506 ms |
8072 KB |
Output is correct |
| 2 |
Correct |
504 ms |
8084 KB |
Output is correct |
| 3 |
Correct |
3 ms |
740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
418 ms |
8088 KB |
Output is correct |
| 2 |
Execution timed out |
1096 ms |
14352 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
565 ms |
8448 KB |
Output is correct |
| 2 |
Correct |
460 ms |
7440 KB |
Output is correct |
| 3 |
Correct |
7 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
2328 KB |
Output is correct |
| 2 |
Correct |
20 ms |
8084 KB |
Output is correct |
| 3 |
Execution timed out |
1092 ms |
27896 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1066 ms |
27532 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
134 ms |
2332 KB |
Output is correct |
| 2 |
Execution timed out |
1066 ms |
16144 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
