제출 #308283

#제출 시각아이디문제언어결과실행 시간메모리
308283fivefourthreeone새로운 문제 (POI11_pro)C++17
60 / 100
1096 ms27896 KiB
#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; }

컴파일 시 표준 에러 (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()){
      |         ~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...