QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #609114 | #9412. Stop the Castle | orz_z | WA | 4ms | 31108kb | C++14 | 7.6kb | 2024-10-04 10:42:34 | 2024-10-04 10:42:35 |
Judging History
answer
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
//#pragma GCC optimize("Ofast,fast-math")
//#pragma GCC target("avx,avx2")
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef double db;
#define F(i, a, b) for(int i = a; i <= (b); ++i)
#define F2(i, a, b) for(int i = a; i < (b); ++i)
#define dF(i, a, b) for(int i = a; i >= (b); --i)
template<typename T> void debug(string s, T x) {
cerr << "[" << s << "] = [" << x << "]\n";
}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {
for (int i = 0, b = 0; i < (int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++;
else if (s[i] == ')' || s[i] == '}') b--;
else if (s[i] == ',' && b == 0) {
cerr << "[" << s.substr(0, i) << "] = [" << x << "] | ";
debug(s.substr(s.find_first_not_of(' ', i + 1)), args...);
break;
}
}
#ifdef ONLINE_JUDGE
#define Debug(...)
#else
#define Debug(...) debug(#__VA_ARGS__, __VA_ARGS__)
#endif
#define pb push_back
#define fi first
#define se second
#define Mry fprintf(stderr, "%.3lf MB\n", (&Med - &Mbe) / 1048576.0)
#define Try cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
typedef long long ll;
// namespace Fread {const int SIZE = 1 << 17; char buf[SIZE], *S, *T; inline char getchar() {if (S == T) {T = (S = buf) + fread(buf, 1, SIZE, stdin); if (S == T) return '\n';} return *S++;}}
// namespace Fwrite {const int SIZE = 1 << 17; char buf[SIZE], *S = buf, *T = buf + SIZE; inline void flush() {fwrite(buf, 1, S - buf, stdout), S = buf;} inline void putchar(char c) {*S++ = c;if (S == T) flush();} struct NTR {~NTR() {flush();}} ztr;}
// #ifdef ONLINE_JUDGE
// #define getchar Fread::getchar
// #define putchar Fwrite::putchar
// #endif
inline int ri() {
int x = 0;
bool t = 0;
char c = getchar();
while (c < '0' || c > '9') t |= c == '-', c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
return t ? -x : x;
}
inline void wi(int x) {
if (x < 0) {
putchar('-'), x = -x;
}
if (x > 9) wi(x / 10);
putchar(x % 10 + 48);
}
inline void wi(int x, char s) {
wi(x), putchar(s);
}
bool Mbe;
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3f;
const int _ = 2e5 + 5;
int n, m;
template<class tp>
struct Flow {
int Node;
int s, t, lv[_], cur[_];
int tot = 1, head[_], to[_ << 1], nxt[_ << 1];
tp w[_ << 1];
inline void add(int u, int v, tp dis) {
to[++tot] = v;
nxt[tot] = head[u];
w[tot] = dis;
head[u] = tot;
}
inline void Add(int u, int v, tp dis) {
add(u, v, dis);
add(v, u, 0);
}
inline bool bfs() {
F(i, 0, Node) lv[i] = -1;
lv[s] = 0;
memcpy(cur, head, sizeof(head));
queue<int> q;
q.push(s);
while (!q.empty()) {
int p = q.front();
q.pop();
for (int eg = head[p]; eg; eg = nxt[eg]) {
int v = to[eg];
tp vol = w[eg];
if (vol > 0 && lv[v] == -1)
lv[v] = lv[p] + 1, q.push(v);
}
}
return lv[t] != -1;
}
tp dfs(int p, tp flow = 2e9) {
if (p == t)
return flow;
tp rmn = flow;
for (int eg = cur[p]; eg && rmn; eg = nxt[eg]) {
cur[p] = eg;
int v = to[eg];
tp vol = w[eg];
if (vol > 0 && lv[v] == lv[p] + 1) {
tp c = dfs(v, min(vol, rmn));
rmn -= c;
w[eg] -= c;
w[eg ^ 1] += c;
}
}
return flow - rmn;
}
inline tp dinic() {
tp ans = 0;
while (bfs())
ans += dfs(s);
return ans;
}
void init() {
F(i, 0, Node) head[i] = 0;
tot = 1;
Node = 0;
}
};
Flow<int> A;
pii a[_], b[_]; int t, C[_];
int mp[805][805], mp1[805][805], mp2[805][805];
bool Med;
signed main() {
// Mry;
int T = ri();
int zkw = T;
while(T--) {
A.init();
n = ri();
t = 0;
F(i, 1, n) {
a[i].fi = ri(), a[i].se = ri();
C[++t] = a[i].fi, C[++t] = a[i].se;
}
m = ri();
F(i,1 , m) {
b[i].fi = ri(), b[i].se = ri();
C[++t] = b[i].fi, C[++t] = b[i].se;
}
if(zkw == 20) {
F(i, 1, n) cout << a[i].fi << ' ' << a[i].se << ' ';
cout <<'\n';
F(i, 1, m) cout << b[i].fi << ' ' << b[i].se << ' ';
return 0;
}
sort(C + 1, C + t + 1);
t = unique(C + 1, C + t + 1) - C - 1;
F(i, 1, n) {
a[i].fi = lower_bound(C + 1, C + t + 1, a[i].fi) - C;
a[i].se = lower_bound(C + 1, C + t + 1, a[i].se) - C;
}
F(i, 1, m) {
b[i].fi = lower_bound(C + 1, C + t + 1, b[i].fi) - C;
b[i].se = lower_bound(C + 1, C + t + 1, b[i].se) - C;
}
// t = 10;
F(i, 1, t) F(j, 1, t) {
mp[i][j] = mp1[i][j] = mp2[i][j] = 0;
}
F(i, 1, n) {
mp[a[i].fi][a[i].se] = 1;
}
F(i, 1, m) {
mp[b[i].fi][b[i].se] = 2;
}
// Debug("haha");
bool flg = 0;
int sum = 0;
int hangnode = 0, lienode = t + t + t;
static pii Zb[_];
F(i, 1, t) {
F(j, 1, t) if(mp[i][j] == 1) {
int nw = j + 1;
while(nw <= t && mp[i][nw] != 1) nw++;//, Debug(nw);
// Debug(i, j);
if(j < t && j + 1 == nw && mp[i][nw] == 1) {
Debug(j, nw);
flg = 1;
break;
}
// Debug(i, j, nw);
if(nw == t + 1) break;
bool fg = 1;
F(z, j + 1, nw - 1) {
fg &= (mp[i][z] == 0);
}
if(fg) {
++hangnode;
sum++;
// Debug("hang", i, j + 1, nw - 1);
F(z, j + 1, nw - 1) if(mp[i][z] == 0) mp1[i][z] = hangnode, Zb[hangnode] = {i, z};
}
// Debug(t, nw - 1, "done");
j = nw - 1;
}
// Debug(i);
if(flg) break;
}
if(flg) {
puts("-1");
continue;
}
// Debug("zj");
F(j, 1, t) {
F(i, 1, t) if(mp[i][j] == 1) {
int nw = i + 1;
while(nw <= t && mp[nw][j] != 1) nw++;
if(nw == t + 1) break;
if(i < t && i + 1 == nw && mp[nw][j] == 1) {
flg = 1;
break;
}
bool fg = 1;
F(z, i + 1, nw - 1) fg &= (mp[z][j] == 0);
if(fg) {
++lienode;
sum++;
// Debug("lie", i + 1, nw - 1, j);
F(z, i + 1, nw - 1) if(mp[z][j] == 0) mp2[z][j] = lienode, Zb[lienode] = {z, j};
}
i = nw - 1;
}
if(flg) break;
}
if(flg) {
puts("-1");
continue;
}
// Debug("114514");
A.s = 0, A.t = lienode + 1;
A.Node = A.t + 2;
F(i, 1, hangnode) A.Add(A.s, i, 1);
F(i, t + t + t + 1, lienode) A.Add(i, A.t, 1);
// Debug(hangnode, t + t + t, lienode);
vector<tuple<int, int, int, int, int>> g;
F(i, 1, t) F(j, 1, t) if(mp1[i][j] && mp2[i][j]) {
// Debug(i, j);
g.pb({A.tot + 1, i, j, mp1[i][j], mp2[i][j]});
A.Add(mp1[i][j], mp2[i][j], 1);
}
static int Flg[_];
F(i, 1, lienode) Flg[i] = 0;
int w = A.dinic();
// Debug(sum, w);
cout<<sum - w << '\n';
for(auto v : g) {
int a, b, c, d, e;
tie(a, b, c, d, e) = v;
if(A.w[a] == 0) {
cout << C[b] << ' ' << C[c] << '\n';
Flg[d] = Flg[e] = 1;
}
}
F(i, 1, hangnode) if(!Flg[i]) {
cout << C[Zb[i].fi] << ' ' <<C[Zb[i].se] << '\n';
}
F(i, t + t + t + 1, lienode) if(!Flg[i]) {
cout << C[Zb[i].fi] << ' ' <<C[Zb[i].se] << '\n';
}
}
// Try;
return 0;
}
/*
1
13
89287395 441913071
89287395 590314987
142917372 582720391
142917372 598813561
232930851 582720391
263974835 468188689
263974835 490702144
543529670 152471388
543529670 219371706
647691663 598813561
772865038 598813561
773363571 482933265
773363571 561453301
1
7
1 3
6 6
4 7
2 1
6 3
4 1
2 6
3
3 4
6 4
3 1
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
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 26172kb
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: 0
Accepted
time: 0ms
memory: 30572kb
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 28 12 41 18 42 38 5 16 12 16 47 31 6 26 26 36 50 0 1 41 10 0 1 43 35 5 1 9 1 40 33 47 44 46 42 44 0 5 27 41 29 40 44 34 10 1 31 15 1 32 11 0 0 0 0 6 23 10 35 34 12 39 23 45 29 32 34 46 0 3 20 31 43 32 34 17 0 -1 3 16 36 25 9 28 39 6 7 5 8 11 5 5 6 6 9 9 10 10
result:
ok ok 21 cases (21 test cases)
Test #3:
score: 0
Accepted
time: 4ms
memory: 31108kb
input:
2 200 7 52 9 160 10 4 12 61 18 436 19 430 20 499 24 139 25 416 29 53 33 153 35 275 35 310 37 25 38 477 39 349 42 120 44 158 45 330 49 486 50 204 51 67 52 138 52 305 56 139 63 132 66 4 67 327 70 484 71 67 72 308 74 218 76 479 81 139 82 90 86 201 87 335 91 35 91 220 92 496 94 29 94 436 96 359 97 299 1...
output:
46 52 139 91 160 94 35 126 61 132 67 154 138 154 496 185 147 187 467 199 432 224 153 260 275 270 305 277 356 306 374 311 186 334 367 349 61 352 112 393 307 35 308 126 300 187 447 224 430 261 491 274 109 277 270 311 481 390 366 440 191 453 374 65 4 143 25 349 35 70 67 80 139 332 177 277 186 287 272 4...
result:
ok ok 2 cases (2 test cases)
Test #4:
score: -100
Wrong Answer
time: 3ms
memory: 13832kb
input:
20 13 89287395 441913071 89287395 590314987 142917372 582720391 142917372 598813561 232930851 582720391 263974835 468188689 263974835 490702144 543529670 152471388 543529670 219371706 647691663 598813561 772865038 598813561 773363571 482933265 773363571 561453301 8 128947560 120560639 264980960 4742...
output:
89287395 441913071 89287395 590314987 142917372 582720391 142917372 598813561 232930851 582720391 263974835 468188689 263974835 490702144 543529670 152471388 543529670 219371706 647691663 598813561 772865038 598813561 773363571 482933265 773363571 561453301 128947560 120560639 264980960 474213553 2...
result:
wrong answer Integer parameter [name=K] equals to 89287395, violates the range [-1, 169] (test case 1)