Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "vector"
- #include "iostream"
- using namespace std;
- struct five {
- int minute, x0, y0, x1, y1;
- };
- inline bool check(five f1, five f2) {
- int t1 = f1.minute +
- abs(f1.x0 - f1.x1) +
- abs(f1.y0 - f1.y1);
- int dt = abs(f1.x1 - f2.x0) +
- abs(f1.y1 - f2.y0);
- return t1 + dt < f2.minute;
- }
- vector<vector<int>> g;
- vector<int> pairs;
- vector<char> used;
- int cnt = 0;
- bool dfs_kuhn(int v) {
- if (used[v])
- return false;
- used[v] = true;
- for (int to : g[v]) {
- if(pairs[to] == -1)
- cnt++;
- if (pairs[to] == -1 || dfs_kuhn(pairs[to])) {
- pairs[to] = v;
- return true;
- }
- }
- return false;
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- int M;
- vector<five> ords;
- cin >> M;
- g.resize(M);
- for (int i = 0; i < M; ++i) {
- int h, m, x0, y0, x1, y1;
- char c;
- cin >> h >> c >> m >> x0 >> y0 >> x1 >> y1;
- five f = {h * 60 + m, x0, y0, x1, y1};
- for (int i = 0; i < ords.size(); ++i) {
- if (check(ords[i], f)){
- g[i].push_back(ords.size());
- }
- }
- ords.push_back(f);
- }
- pairs.assign(M, -1);
- for(int v = 0; v < M; ++v) {
- used.assign(M, false);
- dfs_kuhn(v);
- }
- cout << M - cnt << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement