QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#605815 | #9412. Stop the Castle | zqx | WA | 85ms | 125884kb | C++23 | 5.0kb | 2024-10-02 19:48:01 | 2024-10-02 19:48:02 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
struct Dinic {
long long INF = 1e18;
int SIZ = 5e5 + 3;
int n, m;
int H[5000005], V[5000005], N[5000005], F[5000005], t = 1;
int add(int u, int v, int f) {
V[++ t] = v, N[t] = H[u], F[t] = f, H[u] = t;
V[++ t] = u, N[t] = H[v], F[t] = 0, H[v] = t;
n = max(n, u);
n = max(n, v);
return t;
}
void clear() {
for (int i = 1; i <= n; ++ i)
H[i] = 0;
n = m = 0, t = 1;
}
int D[5000005];
bool bfs(int s, int t) {
queue <int> Q;
for (int i = 1; i <= n; ++ i)
D[i] = 0;
Q.push(s), D[s] = 1;
while (!Q.empty()) {
int u = Q.front();
Q.pop();
for (int i = H[u]; i; i = N[i]) {
const int &v = V[i];
const int &f = F[i];
if (f != 0 && !D[v]) {
D[v] = D[u] + 1;
Q.push(v);
}
}
}
return D[t] != 0;
}
int C[5000005];
long long dfs(int s, int t, int u, long long maxf) {
if (u == t)
return maxf;
long long totf = 0;
for (int &i = C[u]; i; i = N[i]) {
const int &v = V[i];
const int &f = F[i];
if (D[v] == D[u] + 1) {
long long resf = dfs(s, t, v, min(maxf, 1ll * f));
totf += resf;
maxf -= resf;
F[i ] -= resf;
F[i ^ 1] += resf;
if (maxf == 0)
return totf;
}
}
return totf;
}
long long dinic(int s, int t) {
long long ans = 0;
while (bfs(s, t)) {
memcpy(C, H, sizeof(H));
ans += dfs(s, t, s, INF);
}
return ans;
}
} a;
#define all(tar) tar.begin(),tar.end()
int n,m;
const int maxx=2e3+5;
int mp[maxx][maxx];//0无 1防御塔 2障碍
vector<int>num;
int get_pos(int x){
return lower_bound(all(num),x)-num.begin()+1;
}
pair<int,int>p1[maxx],p2[maxx];
int id[maxx][maxx][2],idx;
int G1[maxx][maxx],G2[maxx][maxx];
void solve(){
a.clear();
num.clear();
idx=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>p1[i].first>>p1[i].second;
num.push_back(p1[i].first);
num.push_back(p1[i].second);
num.push_back(p1[i].first+1);
num.push_back(p1[i].second+1);
}
cin>>m;
int s=++idx,t=++idx;
for(int i=1;i<=m;i++){
cin>>p2[i].first>>p2[i].second;
num.push_back(p2[i].first);
num.push_back(p2[i].second);
num.push_back(p2[i].first+1);
num.push_back(p2[i].second+1);
}
sort(all(num));
int len=num.size();
num.erase(unique(all(num)),num.end());
for(int i=1;i<=len;i++){
for(int j=1;j<=len;j++){
G1[i][j]=G2[i][j]=mp[i][j]=0;
}
}
for(int i=1;i<=n;i++){
int x=get_pos(p1[i].first);
int y=get_pos(p1[i].second);
mp[x][y]=2;
}
for(int i=1;i<=m;i++){
int x=get_pos(p2[i].first);
int y=get_pos(p2[i].second);
mp[x][y]=1;
}
int ans=0;
for(int i=1;i<=len;i++){
for(int j=1;j<=len;j++){
id[i][j][0]=++idx;
id[i][j][1]=++idx;
a.add(s,id[i][j][0],1);
a.add(id[i][j][1],t,1);
if(mp[i][j]==2){
if(mp[i-1][j]==2||mp[i][j-1]==2){
cout<<"-1\n";
return ;
}
}
}
}
for(int i=1;i<=len;i++){
int pre=0;
for(int j=1;j<=len;j++){
if(mp[i][j]==2){
if(pre){
++ans;
for(int k=pre+1;k<j;k++){
G1[i][k]=pre;
}
}
pre=j;
}else if(mp[i][j]==1){
pre=0;
}
}
}
for(int i=1;i<=len;i++){
int pre=0;
for(int j=1;j<=len;j++){
if(mp[j][i]==2){
if(pre){
++ans;
for(int k=pre+1;k<j;k++){
G2[k][i]=pre;
}
}
pre=j;
}else if(mp[j][i]==1){
pre=0;
}
}
}
vector<array<int,3>>e;
int c=0;
for(int i=1;i<=len;i++){
for(int j=1;j<=len;j++){
if(G1[i][j]&&G2[i][j]){
e.push_back({i,j,a.t+1});
++c;
a.add(id[i][G1[i][j]][0],id[G2[i][j]][j][1],1);
}
}
}
int p=a.dinic(s,t);
if(n==200)cout<<ans<<" "<<p<<" "<<c<<'\n';
cout<<ans-p<<'\n';
for(auto [x,y,z]:e){
if(a.F[z]==0)cout<<num[x-1]<<" "<<num[y-1]<<'\n',mp[x][y]=1;
}
for(int i=1;i<=len;i++){
int pre=0;
for(int j=1;j<=len;j++){
if(mp[i][j]==2){
if(pre){
cout<<num[i-1]<<" "<<num[pre]<<'\n';
}
pre=j;
}else if(mp[i][j]==1){
pre=0;
}
}
}
for(int i=1;i<=len;i++){
int pre=0;
for(int j=1;j<=len;j++){
if(mp[j][i]==2){
if(pre){
cout<<num[pre]<<" "<<num[i-1]<<'\n';
}
pre=j;
}else if(mp[j][i]==1){
pre=0;
}
}
}
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin>>T;
while(T--){
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 40784kb
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: 7ms
memory: 48336kb
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 34 18 29 38 5 16 10 16 15 12 6 20 26 34 50 0 1 16 10 0 1 43 22 5 1 3 1 13 33 10 44 45 42 44 0 5 27 41 29 26 44 4 8 1 21 15 1 32 9 0 0 0 0 6 23 10 35 34 12 11 23 44 29 21 24 46 0 3 20 30 43 25 31 17 0 -1 3 16 36 25 7 17 39 6 7 5 8 11 5 5 6 4 4 9 3 10
result:
ok ok 21 cases (21 test cases)
Test #3:
score: -100
Wrong Answer
time: 85ms
memory: 125884kb
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:
66 20 106 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 276 126 214 187 433 224 393 261 468 274 67 277 189 311 455 390 308 440 179 453 251 11 4 38 25 240 35 52 67 57 139 292 177 271 186 2...
result:
wrong answer There are still 63 pairs of castles which can attack each other (test case 1)