QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#610428#9412. Stop the CastleUESTC_OldEastWestWA 1ms3824kbC++177.2kb2024-10-04 15:55:032024-10-04 15:55:04

Judging History

This is the latest submission verdict.

  • [2024-10-04 15:55:04]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3824kb
  • [2024-10-04 15:55:03]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;

namespace Dinic {
	int n, s, t, tot;
	std::vector<int> to, nxt, cap, head;
	std::vector<int> cur, dep;

	void AddEdge(int u, int v, int c) {
		to[tot] = v, nxt[tot] = head[u], cap[tot] = c, head[u] = tot++;
	}

	void Init(int _n, int _s, int _t, std::vector<std::array<int, 3> > &edge) {
		n = _n, s = _s, t = _t, tot = 0;
		int m = edge.size();
		to = nxt = cap = std::vector<int>(m << 1);
		head = cur = dep = std::vector<int>(n, -1);
		for (auto [u, v, c] : edge) {
			AddEdge(u, v, c);
			AddEdge(v, u, 0);
		}
	}

	bool BFS() {
		dep = std::vector<int>(n, -1);
		std::vector<int> que(1, s);
		dep[s] = 0;
		for (int h = 0, u; h < que.size(); ++h) {
			u = que[h];
			for (int i = head[u], v, c; ~i; i = nxt[i]) {
				v = to[i], c = cap[i];
				if (dep[v] == -1 && c) dep[v] = dep[u] + 1, que.emplace_back(v);
			}
		}
		return dep[t] != -1;
	}

	int DFS (int u, int in) {
		if (u == t || !in) return in;
		int out = 0;
		for (int i = cur[u], v, c; ~i; i = nxt[i]) {
			cur[u] = nxt[i];
			v = to[i], c = cap[i];
			if (c && dep[v] == dep[u] + 1) {
				int ret = DFS(v, std::min(in, c));
				in -= ret, out += ret;
				cap[i] -= ret, cap[i ^ 1] += ret;
			}
		}
		return out;
	}

	int getMaxFlow() {
		int ans = 0;
		while (BFS()) {
			cur = head;
			ans += DFS(s, INT_MAX);
		}
		return ans;
	}
}


void charming() {
  int n; std::cin >> n;
  std::vector<std::pair<int, int> > castle;
  for (int i = 0, r, c; i < n; ++i) {
    std::cin >> r >> c;
    castle.emplace_back(std::make_pair(r, c));
  }

  int m; std::cin >> m;
  std::vector<std::pair<int, int> > obstacle;
  for (int i = 0, r, c; i < m; ++i) {
    std::cin >> r >> c;
    obstacle.emplace_back(std::make_pair(r, c));
  }

  std::function<bool(int, int, int)> Check = [&](int x, int y, int z) {
    if (x > y) std::swap(x, y);
    if (z > x && z < y) return true;
    else return false;
  };

  std::function<bool(int, int, int, int)> hinder = [&](int idx0, int idx1, int idx2, int type) {
    bool r_same = castle[idx0].first == castle[idx1].first;
    if (type == 0) {
      if (r_same) {
      	if (castle[idx2].first != castle[idx0].first) return false;
        int c0 = castle[idx0].second, c1 = castle[idx1].second, c2 = castle[idx2].second;
        return Check(c0, c1, c2);
      }
      else {
      	if (castle[idx2].second != castle[idx0].second) return false;
        int r0 = castle[idx0].first, r1 = castle[idx1].first, r2 = castle[idx2].first;
        return Check(r0, r1, r2);
      }
    }
    else {
      if (r_same) {
      	if (obstacle[idx2].first != castle[idx0].first) return false;
        int c0 = castle[idx0].second, c1 = castle[idx1].second, c2 = obstacle[idx2].second;
        return Check(c0, c1, c2);
      }
      else {
      	if (obstacle[idx2].second != castle[idx0].second) return false;
        int r0 = castle[idx0].first, r1 = castle[idx1].first, r2 = obstacle[idx2].first;
        return Check(r0, r1, r2);
      }
    }
  };

  std::function<bool(int, int)> fight = [&](int idx0, int idx1) {
    if (castle[idx0].first == castle[idx1].first || 
    castle[idx0].second == castle[idx1].second) {
      for (int i = 0; i < n; ++i) if (i != idx0 && i != idx1) {
        if (hinder(idx0, idx1, i, 0)) return false;
      }
      for (int i = 0; i < m; ++i) {
        if (hinder(idx0, idx1, i, 1)) return false;
      }
      return true;
    }
    else return false;
  };

	bool near = false;
  std::vector<std::pair<int, int> > conf_row, conf_col;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
    	if (abs(castle[i].first - castle[j].first) + 
			abs(castle[i].second - castle[j].second) <= 1) {
    		near = true; break;
    	}
      
			if (castle[i].first == castle[j].first) {
        if (fight(i, j)) conf_row.emplace_back(std::make_pair(i, j));
      }
      else {
        if (fight(i, j)) conf_col.emplace_back(std::make_pair(i, j));
      }
    }
    if (near) break;
  }
  
  if (near) {std::cout << -1 << '\n'; return;}

  int s = 0, t = 1, tot = 2;
  std::map<int, int> mp0, mp1, rev_mp0, rev_mp1;
  std::vector<std::array<int, 3> > edge;
  int conf_row_cnt = conf_row.size(), conf_col_cnt = conf_col.size();
  for (int i = 0; i < conf_row_cnt; ++i) {
    mp0[i] = tot, rev_mp0[tot++] = i;
    edge.emplace_back((std::array<int, 3>) {s, mp0[i], 1});
  }
  for (int i = 0; i < conf_col_cnt; ++i) {
    mp1[i] = tot, rev_mp1[tot++] = i;
    edge.emplace_back((std::array<int, 3>) {mp1[i], t, 1});
  }

  std::function<bool(int, int)> is_inter = [&](int idx0, int idx1) {
    int r0 = conf_row[idx0].first, r1 = conf_row[idx0].second;
    int c0 = conf_col[idx1].first, c1 = conf_col[idx1].second;
    int r = castle[r1].first, c = castle[c1].second;
    if (r <= std::min(castle[c0].first, castle[c1].first)) return false;
    if (r >= std::max(castle[c0].first, castle[c1].first)) return false;
    if (c <= std::min(castle[r0].second, castle[r1].second)) return false;
    if (c >= std::max(castle[r0].second, castle[r1].second)) return false;
    return true;
  };

  std::function<std::pair<int, int>(int, int)> get_inter = [&](int idx0, int idx1) {
    int r = castle[conf_row[idx0].first].first, c = castle[conf_col[idx1].first].second;
    return std::make_pair(r, c);
  };

  for (int i = 0; i < conf_row_cnt; ++i) {
    for (int j = 0; j < conf_col_cnt; ++j) {
      if (is_inter(i, j)) edge.emplace_back((std::array<int, 3>) {mp0[i], mp1[j], 1});
    }
  }

  Dinic::Init(tot, s, t, edge);
  int ans = conf_row_cnt + conf_col_cnt - Dinic::getMaxFlow();

  std::set<std::pair<int, int> > pos;
  {
    using namespace Dinic;
    std::vector<int> vis_r(conf_row_cnt), vis_c(conf_col_cnt);
    for (int u = 0; u < conf_row_cnt; ++u) {
      for (int i = head[mp0[u]], v, c; ~i; i = nxt[i]) if (i & 1 ^ 1) {
        v = rev_mp1[to[i]], c = cap[i];
        if (!c) pos.insert(get_inter(u, v));
        vis_r[u] = 1, vis_c[v] = 1;
      }
    }

    for (int i = 0; i < conf_row_cnt; ++i) if (!vis_r[i]) {
      auto [idx0, idx1] = conf_row[i];
      int r = castle[idx0].first;
      int mn = castle[idx0].second, mx = castle[idx1].second;
      if (mn > mx) std::swap(mn, mx);
      for (int j = mn + 1; j < mx; ++j) {
        std::pair<int, int> new_pos = std::make_pair(r, j);
        if (pos.count(new_pos)) continue;
        else {pos.insert(new_pos); break;}
      }
    }
    for (int i = 0; i < conf_col_cnt; ++i) if (!vis_c[i]) {
      auto [idx0, idx1] = conf_col[i];
      int c = castle[idx0].second;
      int mn = castle[idx0].first, mx = castle[idx1].first;
      if (mn > mx) std::swap(mn, mx);
      for (int j = mn + 1; j < mx; ++j) {
        std::pair<int, int> new_pos = std::make_pair(j, c);
        if (pos.count(new_pos)) continue;
        else {pos.insert(new_pos); break;}
      }
    }
  }

  std::cout << ans << '\n';
  for (auto [r, c] : pos) std::cout << r << ' ' << c << '\n';
}

signed main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  std::cout.tie(NULL);
  int t; std::cin >> t;
  while (t--) charming();
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3824kb

input:

4
7
1 3
6 6
4 7
2 1
6 3
4 1
2 6
3
3 4
6 4
3 1
2
1 1
2 2
0
3
1 1
1 3
3 3
1
1 2
3
1 1
1 3
2 3
0

output:

2
2 3
4 6
0
1
2 3
-1

result:

ok ok 4 cases (4 test cases)

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3608kb

input:

21
11
3 5
18 6
19 12
27 48
28 38
30 12
33 18
42 18
43 38
45 46
48 34
3
2 6
24 4
41 45
15
11 6
15 27
16 9
16 14
16 48
19 26
25 12
27 26
28 4
31 40
32 6
33 50
37 50
46 11
50 29
17
1 49
4 9
9 15
9 22
11 31
11 46
14 28
17 5
17 49
18 43
20 31
30 46
33 11
33 33
34 15
36 6
47 10
2
16 46
36 30
11
7 34
7 41
...

output:

3
20 12
29 38
34 18
5
12 6
16 10
16 15
20 26
34 50
0
1
16 10
0
1
43 22
5
1 3
1 13
33 10
42 44
44 45
0
5
8 1
21 15
27 41
29 26
44 4
1
32 9
0
0
0
0
6
12 11
23 10
23 44
24 46
29 21
35 34
0
3
20 30
31 17
43 25
0
-1
3
16 36
17 39
25 7
6
7 5
8 11

result:

wrong output format Unexpected end of file - int32 expected (test case 21)