Submission #115338

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
115338	2019-06-06T17:25:37 Z	model_code	Hotel (CEOI11_hot)	C++17	Compilation error	0 ms	0 KB

/* Slow solution for task HOT
 * Author: Miroslaw Michalski
 * Time complexity : O(n^3)
 * 03MAY11
 * Min Cost Max Flow
 */

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <cassert>

using namespace std;
#define VAR(a,b) typeof(b) a=(b)
#define REP(i,n) for(int _n=n, i=0;i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
#define FOREACH(it,c) for(VAR(it,(c).begin());it!=(c).end();++it)
#define ALL(f,w) ({ bool _ok=true; f _ok=_ok && (w); _ok; })
#define EXISTS(f,w) (!ALL(f,!(w)))
typedef long long LL;
const int INF = 1100000000;
typedef vector<int> VI; 
#define MP make_pair
#define PB push_back
#define ST first
#define ND second
#define SIZE(x) (int)x.size()

const int N=500100;
struct Edge{
  int v,rev,c,koszt;
  Edge(int vv,int rrev,int cc,int kkoszt) : v(vv), rev(rrev), c(cc), koszt(kkoszt) {}
  Edge(){}
};
vector<Edge> kraw[N];
int parent[N],parent_kraw[N];
int used[N],dist[N],pot[N];
void AddEdge(int a,int b,int c,int koszt){
  kraw[a].PB(Edge(b,SIZE(kraw[b])+(a==b),c,koszt));
  kraw[b].PB(Edge(a,SIZE(kraw[a])-1,0,-koszt));
}

LL MinCostMaxFlow(int beg,int end,int n){
  int res=0;
  LL koszt=0, totalResult = 0;
  REP(i,n) pot[i]=0; //poczatkowy potencjal, zakladam, ze poczatkowo
                     //wszystkie wagi sa nieujemne, jesli moba byc ujemne,
                     //to trzeba obliczyc poczatkowe potencjaly Bellmanem-Fordem
  while (1){
    REP(i,n) dist[i]=INF,used[i]=0; 
    dist[beg]=0;
    //algorytm Dijkstry, mozna zmienic na wersje z kopcem dla grafu rzadkiego
    REP(k,n){
      int best=-1;
      REP(i,n) if (!used[i] && (best==-1 || dist[i]<dist[best])) best=i;
      used[best]=1;
      if (dist[best]==INF) break;
      FOREACH(it,kraw[best]) if (it->c>0){
        int x=it->koszt-pot[it->v]+pot[best];
        if (dist[it->v]>dist[best]+x){
          dist[it->v]=dist[best]+x;
          parent[it->v]=best;
          parent_kraw[it->v]=it-kraw[best].begin();
        }
      }
    }

    if (dist[end]==INF) break; //brak sciezki powiekszajacej
    REP(i,n) dist[i]+=pot[i],pot[i]=dist[i]; //uaktualnienie potencjalu

    int cap=INF; //minimalna przepustowosc na sciezce
    int x=end;
    do{
      cap=min(cap,kraw[parent[x]][parent_kraw[x]].c);
      x=parent[x];
    } while (x!=beg);
    res+=cap;

    x=end;
    do{
      koszt+=kraw[parent[x]][parent_kraw[x]].koszt*(LL)cap;
      kraw[parent[x]][parent_kraw[x]].c-=cap;
      kraw[x][kraw[parent[x]][parent_kraw[x]].rev].c+=cap;
      x=parent[x];
    } while (x!=beg);
    totalResult = max(totalResult, static_cast<long long>(INF) * res - koszt);
  }
  return totalResult;
}


int main(){
  int graphSize, n, m, o, ci, pi;
  vector<pair<int, int> > room, need;
  scanf("%d%d%d", &n, &m, &o);
  graphSize = 3 + n + m + 1;
  REP(i, graphSize) {
    kraw[i].clear();
  }

  AddEdge(0, 1, o, 0);
  REP(i, n) {
    scanf("%d%d", &ci, &pi);
    room.push_back(make_pair(ci, pi));
  }
  REP(i, m) {
    scanf("%d%d", &ci, &pi);
    need.push_back(make_pair(ci, pi));
  }

  REP(i, n) {
    AddEdge(1, 2 + i, 1, 0);
  }
  REP(i, m) {
    AddEdge(2 + n + i, graphSize - 1, 1, 0);
  }

  REP(i, n) {
    REP(j, m) {
      if (room[i].first < need[j].first && room[i].second >= need[j].second) {
        AddEdge(2 + i, 2 + n + j, 1, INF - (need[j].first - room[i].first));
      }
    }
  }
  LL p = MinCostMaxFlow(0, graphSize - 1, graphSize);
  printf("%lld\n", p);
  return 0;
}

Compilation message

hot.cpp: In function 'LL MinCostMaxFlow(int, int, int)':
hot.cpp:24:18: error: 'typeof' was not declared in this scope
 #define VAR(a,b) typeof(b) a=(b)
                  ^
hot.cpp:28:27: note: in expansion of macro 'VAR'
 #define FOREACH(it,c) for(VAR(it,(c).begin());it!=(c).end();++it)
                           ^~~
hot.cpp:69:7: note: in expansion of macro 'FOREACH'
       FOREACH(it,kraw[best]) if (it->c>0){
       ^~~~~~~
hot.cpp:24:18: note: suggested alternative: 'feof'
 #define VAR(a,b) typeof(b) a=(b)
                  ^
hot.cpp:28:27: note: in expansion of macro 'VAR'
 #define FOREACH(it,c) for(VAR(it,(c).begin());it!=(c).end();++it)
                           ^~~
hot.cpp:69:7: note: in expansion of macro 'FOREACH'
       FOREACH(it,kraw[best]) if (it->c>0){
       ^~~~~~~
hot.cpp:69:15: error: 'it' was not declared in this scope
       FOREACH(it,kraw[best]) if (it->c>0){
               ^
hot.cpp:28:47: note: in definition of macro 'FOREACH'
 #define FOREACH(it,c) for(VAR(it,(c).begin());it!=(c).end();++it)
                                               ^~
hot.cpp:69:15: note: suggested alternative: 'int'
       FOREACH(it,kraw[best]) if (it->c>0){
               ^
hot.cpp:28:47: note: in definition of macro 'FOREACH'
 #define FOREACH(it,c) for(VAR(it,(c).begin());it!=(c).end();++it)
                                               ^~
hot.cpp: In function 'int main()':
hot.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &n, &m, &o);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
hot.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &ci, &pi);
     ~~~~~^~~~~~~~~~~~~~~~~~
hot.cpp:118:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &ci, &pi);
     ~~~~~^~~~~~~~~~~~~~~~~~