Submission #308283

#	Time	Username	Problem	Language	Result	Execution time	Memory
308283		fivefourthreeone	Programming Contest (POI11_pro)	C++17	60 / 100	1096 ms	27896 KiB

pro

#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 (stderr)

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()){
      |         ~~~~^~~~~~~~~~

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