Submission #371303

---

Source Code Expand

#include <algorithm>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <queue>
#include <cstdio>
inline int getInt(){ int s; scanf("%d", &s); return s; }

#include <set>

using namespace std;

struct Edge{
  int cap; // capacity
  int to;
  int rev; // reverse edge id

  Edge(){}
  Edge(int c, int t, int r) :
    cap(c), to(t), rev(r){}
};

struct CostEdge : public Edge{
  int cost;
  CostEdge() : Edge() {}
  CostEdge(int c, int t, int cs, int r) :
    Edge(c, t, r), cost(cs){}
};

template<class E> // Edge type
class Graph{
public:
  typedef std::vector<std::vector<E> > G;

private:
  G g;

public:
  Graph(int n) : g(G(n)) {}

  void addEdge(int from, int to, int cap){
    g[from].push_back(E(cap, to, g[to].size()));
    g[to].push_back(E(0, from, g[from].size() - 1));
  }

  void addEdge(int from, int to, int cap, int cost){
    g[from].push_back(E(cap, to, cost, g[to].size()));
    g[to].push_back(E(0, from, -cost, g[from].size() - 1));
  }

  G &getRowGraph(){
    return g;
  }
};

template<class E>
int minCostFlow(Graph<E> &graph, int s, int t, int f, bool negative = false){
  typedef pair<int, int> P;
  typename Graph<E>::G &g = graph.getRowGraph();
  int n = g.size();
  int res = 0;
  vector<int> h(n, 0);
  vector<int> prevv(n);
  vector<int> preve(n);
  const int inf = 10000000;

  if(negative){
    vector<int> dist(n, inf);
    dist[s] = 0;

    bool update = true;

    while(update){
      update = false;
      for(int v = 0; v < n; v++){
        if(dist[v] == inf) continue;
        for(int i = 0; i < (int)g[v].size(); i++){
          E &e = g[v][i];
          if(e.cap > 0 && dist[e.to] > dist[v] + e.cost){
            dist[e.to]  = dist[v] + e.cost;
            prevv[e.to] = v;
            preve[e.to] = i;
            update      = true;
          }
        }
      }
    }

    for(int i = 0; i < n; i++)
      h[i] = dist[i];
  }

  while(f > 0){
    priority_queue<P, vector<P>, greater<P> > que;
    vector<int> dist(n, inf);
    dist[s] = 0;
    que.push(P(0, s));

    while(!que.empty()){
      P p   = que.top(); que.pop();
      int v = p.second;
      if(dist[v] < p.first) continue;
      for(int i = 0; i < (int)g[v].size(); i++){
        E &e = g[v][i];

        if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]){
          dist[e.to]  = dist[v] + e.cost + h[v] - h[e.to];
          prevv[e.to] = v;
          preve[e.to] = i;
          que.push(P(dist[e.to], e.to));
        }
      }
    }
    if(dist[t] == inf){
      return -1;
    }

    for(int v = 0; v < n; v++) h[v] += dist[v];

    int d = f;
    for(int v = t; v != s; v = prevv[v]){
      d = min(d, g[prevv[v]][preve[v]].cap);
    }

    f   -= d;
    res += d * h[t];

    for(int v = t; v != s; v = prevv[v]){
      E &e = g[prevv[v]][preve[v]];
      e.cap -= d;
      g[v][e.rev].cap += d;
    }
  }
  return res;
}

template<typename T>
inline T dbl(T t){ return t * t; }

bool canReach(int x1, int y1, int x2, int y2, int t){
  return dbl(x1 - x2) + dbl(y1 - y2) <= dbl(t);
}

int main(){
  const int m = getInt();
  vector<int> rx(m);
  vector<int> ry(m);

  REP(i,m){
    rx[i] = getInt();
    ry[i] = getInt();
  }

  const int n = getInt();
  vector<int> px(n);
  vector<int> py(n);
  vector<int> s(n);
  vector<int> t(n);

  REP(i,n){
    px[i] = getInt();
    py[i] = getInt();
    s[i] = getInt();
    t[i] = getInt();
  }

  Graph<CostEdge> g(2 + m + n);
  const int start = n + m;
  const int goal = n + m + 1;

  REP(i,m)
    g.addEdge(start, n + i, 1, 0);

  REP(i,m) REP(j,n){
    if(canReach(rx[i], ry[i], px[j], py[j], s[j]))
      g.addEdge(n + i, j, 1, -1);
  }

  REP(i,n) REP(j,n){
    if(s[i] >= t[j]){
      if(canReach(px[j], py[j], px[i], py[i], s[i] - t[j]))
        g.addEdge(j, i, 1, -1);
    }
  }

  REP(i,n) g.addEdge(i, goal, 1, 0);

  const int cost = minCostFlow(g, start, goal, m, true);
  puts(-cost == n ? "YES" : "NO");
  // printf("%s\n", -cost == m ? );

  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int getInt()’:
./Main.cpp:6:44: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 inline int getInt(){ int s; scanf("%d", &s); return s; }
                                            ^

Judge Result