QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#92509 | #6166. 世纪大逃亡 | abcdefg | 100 ✓ | 3596ms | 24240kb | C++17 | 3.1kb | 2023-03-30 17:26:42 | 2023-03-30 17:26:44 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<queue>
#define ano ((i-1)^1)+1
using namespace std;
const int N=1e6+100,INF=0x7f7f7f7f;
int n,m,S,tot,s,t,f,ans;
int head[N],ver[2*N],Next[2*N],edge[2*N],cost[2*N];
int minf[N],pre[N],d[N];
bool v[N];
void add(int x,int y,int z,int c)
{
ver[++tot]=y,edge[tot]=z,cost[tot]=c,Next[tot]=head[x],head[x]=tot;
ver[++tot]=x,edge[tot]=0,cost[tot]=-c,Next[tot]=head[y],head[y]=tot;
}
bool spfa()
{
for(int i=0;i<=t;i++)
d[i]=INF,v[i]=0;
queue<int> q;
q.push(s);
v[s]=1,d[s]=0,minf[s]=INF;
while(q.size())
{
int x=q.front();q.pop();v[x]=0;
for(int i=head[x];i;i=Next[i])
{
if(!edge[i])
continue;
int y=ver[i];
if(d[x]+cost[i]<d[y])
{
d[y]=d[x]+cost[i];
minf[y]=min(minf[x],edge[i]);
pre[y]=i;
if(!v[y])
{
v[y]=1;
q.push(y);
}
}
}
}
return d[t]!=INF;
}/*
void update()
{
int x=t;
while(x!=s)
{
int i=pre[x];
edge[i]-=minf[t];
edge[ano]+=minf[t];
x=ver[ano];
}
f+=minf[t];
ans+=d[t]*minf[t];
}*///单路增广
int dinic(int x,int flow)
{
if(x==t)
return flow;
v[x]=1;
int rest=flow,use;
for(int i=head[x];i && rest;i=Next[i])
{
int y=ver[i];
if(v[y] || !edge[i] || d[y]!=d[x]+cost[i])
continue;
use=dinic(y,min(rest,edge[i]));
if(!use)
d[y]=0;
edge[i]-=use,edge[ano]+=use,rest-=use;
ans+=cost[i]*use;
}
return flow-rest;
}
int id(int x,int y,int z)
{
return (x-1)*m+y+z*n*m;
}
void clear()
{
t=2*n*m+1,ans=tot=f=0;
for(int i=0;i<=t;i++)
head[i]=pre[i]=minf[i]=0;
}
int main()
{
//freopen("covid.in", "r", stdin);
//freopen("covid.out", "w", stdout);
while(scanf("%d%d%d",&n,&m,&S)!=EOF)
{
clear();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
add(id(i,j,0),id(i,j,1),1,0);
if(i!=1)
add(id(i,j,1),id(i-1,j,0),1,1);
if(i!=n)
add(id(i,j,1),id(i+1,j,0),1,1);
if(j!=1)
add(id(i,j,1),id(i,j-1,0),1,1);
if(j!=m)
add(id(i,j,1),id(i,j+1,0),1,1);
if(i==1 || i==n || j==1 || j==m)
add(id(i,j,1),t,1,0);
}
for(int i=1,x,y;i<=S;i++)
{
scanf("%d%d",&x,&y);
add(s,id(x,y,0),1,0);
}/*
while(spfa())
update();*///单路增广
while(spfa())
{
int flow;
do{
for(int i=0;i<=t;i++)
v[i]=0;
flow=dinic(s,INF);
f+=flow;
}while(flow);
}
if(f==S)
printf("%d\n",ans);
else
puts("-1");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 6ms
memory: 20156kb
input:
13 11 35 6 6 11 2 7 8 3 9 9 9 12 2 2 7 12 6 8 3 2 1 3 1 3 7 11 10 6 11 7 7 12 11 6 10 10 1 5 8 9 6 13 3 3 2 12 10 13 7 8 2 5 10 4 10 5 2 1 1 8 5 6 1 1 2 5 11 3 8 9 1 8 13 3 2 5 1 5 5 2 9 7 4 9 3 3 7 5 2 6 4 7 6 3 2 6 2 1 2 2 4 13 9 2 11 2 8 1 2 3 1 3 9 2 1 4 12 4 9 4 10 6 20 28 1 17 5 17 5 3 2 17 2 ...
output:
69 3 4 1 4 24 100 61 28 2 36 20 0 1 4 0 -1 0 0 34 3 0 2 39 0 21 0 15 6 43 3 -1 16 1 59 0 2 20 1 0 12 -1 1 4 60 7 22 2 0 2 0 4 5 15 0 4 1 2 0 0 1 12 22 33 6 13 2 21 10 34 1 12 -1 0 24 17 0 27 6 23 3 2 5 8 1 46 0 0 3 59 0 37 0 0 84 33 2 13 14 55
result:
ok 100 numbers
Test #2:
score: 10
Accepted
time: 46ms
memory: 18032kb
input:
36 26 3 31 10 16 12 1 17 27 1 1 17 1 19 6 24 1 2 19 6 9 1 5 3 16 3 16 4 6 4 15 4 15 6 6 6 9 3 13 6 7 4 4 5 14 6 1 6 12 1 5 5 11 6 17 1 3 5 10 1 5 2 3 2 40 5 1 31 1 16 27 37 14 19 12 23 12 22 16 10 5 14 13 27 5 4 12 7 5 7 8 24 7 22 3 4 15 4 16 21 9 10 14 14 4 12 6 24 11 11 14 7 16 19 10 18 7 23 11 22...
output:
16 0 23 0 124 -1 82 73 192 85 70 172 0 1 -1 67 -1 -1 10 72 10 -1 6 66 37 91 -1 -1 2 -1 7 5 16 2 -1 197 84 50 0 31 179 0 -1 60 -1 114 -1 -1 1 234 -1 1 -1 0 135 6 -1 24 136 -1 106 14 19 169 106 0 0 22 106 170 -1 4 -1 25 17 -1 242 0 0 47 90 -1 -1 9 10 34 0 19 8 -1 99 117 0 0 -1 133 -1 9 -1 53
result:
ok 100 numbers
Test #3:
score: 10
Accepted
time: 95ms
memory: 20036kb
input:
29 26 79 8 9 24 19 23 11 13 3 20 21 3 13 12 15 3 26 1 19 9 9 11 16 18 23 6 8 13 9 5 23 15 4 17 9 14 7 8 11 29 8 9 15 2 26 10 23 23 24 25 5 7 23 21 25 15 26 19 8 9 1 1 1 21 9 16 21 27 18 15 9 23 8 10 16 14 19 26 20 17 23 15 14 3 18 8 1 26 10 21 7 28 5 26 21 3 15 2 25 27 25 12 14 17 3 11 3 28 3 26 2 2...
output:
374 369 26 0 336 3 1 312 0 658 76 450 82 170 1 254 3 -1 7 12 38 17 192 212 489 -1 232 128 124 96 2 126 40 29 0 -1 7 59 0 128 57 234 291 23 1 221 -1 161 0 147 524 0 57 6 100 185 12 264 176 4 262 114 2 52 5 80 -1 381 19 1 40 -1 5 35 16 13 -1 13 50 121 -1 220 407 96 186 42 36 37 20 698 0 -1 230 -1 2 21...
result:
ok 100 numbers
Test #4:
score: 10
Accepted
time: 417ms
memory: 18148kb
input:
66 71 4 2 13 25 12 1 37 32 63 14 50 79 5 20 4 3 3 1 9 2 5 24 12 11 11 5 3 15 10 24 1 2 10 25 5 1 4 48 8 3 1 12 13 37 6 16 14 7 4 45 5 22 8 14 6 48 7 47 4 8 9 27 4 5 1 17 7 40 1 7 13 27 7 50 6 17 5 31 4 25 2 21 10 16 14 12 2 6 3 11 8 40 14 1 9 14 14 41 14 33 2 5 2 3 9 31 12 4 14 14 3 10 13 43 9 40 14...
output:
20 213 0 -1 73 256 91 -1 78 -1 543 -1 0 -1 2 31 -1 -1 -1 -1 -1 0 0 172 -1 423 0 -1 268 -1 84 -1 4 150 -1 7 142 -1 796 -1 214 -1 -1 10 1057 19 0 0 320 0
result:
ok 50 numbers
Test #5:
score: 10
Accepted
time: 754ms
memory: 20152kb
input:
65 49 175 42 2 50 33 38 21 1 48 13 29 59 8 46 20 11 41 20 34 42 28 23 43 6 10 36 29 9 4 29 24 34 21 30 33 62 18 52 1 35 32 29 10 3 38 8 7 27 36 24 14 56 10 12 37 26 8 44 28 32 14 15 12 48 39 42 34 62 27 35 42 29 1 40 32 3 36 53 22 23 24 25 30 24 26 41 28 44 37 51 14 23 34 35 41 12 8 41 20 28 29 43 4...
output:
-1 262 192 0 -1 173 -1 133 967 -1 -1 611 385 -1 55 -1 1066 -1 -1 1966 4494 -1 -1 -1 504 -1 1066 -1 267 7 0 -1 -1 420 1017 222 49 -1 2003 2005
result:
ok 40 numbers
Test #6:
score: 10
Accepted
time: 1559ms
memory: 24240kb
input:
25 7 4 22 4 21 7 16 7 19 6 119 54 188 10 13 25 11 57 51 21 39 40 44 90 24 92 47 89 30 31 42 14 11 105 4 18 20 118 50 86 5 28 19 44 19 36 34 79 46 61 31 51 42 69 46 101 27 117 16 64 48 42 54 62 42 113 8 79 48 77 37 79 28 10 17 19 20 116 37 93 46 43 3 57 28 21 44 26 23 67 43 112 29 17 3 99 1 63 27 5 4...
output:
4 2334 -1 -1 3700 992 253 -1 -1 2642 0 1914 -1 -1 1598 1941 1286 469 12 1278 1825 6 -1 1842 1490 900 1198 349 1162 28 1410 0 -1 -1 920 205 -1 -1 0 -1
result:
ok 40 numbers
Test #7:
score: 10
Accepted
time: 1076ms
memory: 18248kb
input:
132 29 164 53 3 123 11 54 25 87 29 113 6 27 14 120 15 66 22 110 16 68 6 73 6 78 10 47 12 86 14 131 25 65 29 102 21 97 7 102 1 5 7 34 3 7 16 39 25 78 11 112 11 61 25 121 4 79 17 10 11 118 7 18 18 4 12 75 23 115 27 4 5 50 11 25 29 44 20 110 3 60 16 26 16 28 2 74 13 12 5 95 13 10 10 27 5 28 4 102 16 13...
output:
1056 4303 6 7 -1 800 901 99 4032 306 1837 143 -1 1261 434 -1 1777 1239 1548 -1 -1 371 -1 410 -1 24 192 -1 2041 201
result:
ok 30 numbers
Test #8:
score: 10
Accepted
time: 3596ms
memory: 20312kb
input:
141 113 446 25 79 49 94 140 109 57 20 111 61 3 15 141 16 110 19 62 79 95 66 46 3 3 36 112 96 38 77 82 107 141 71 38 39 111 23 101 44 63 3 61 85 112 33 111 107 139 22 54 49 97 82 76 34 115 10 6 25 46 22 74 10 133 76 136 93 114 6 29 20 49 89 81 54 10 81 30 113 60 66 19 41 114 113 68 1 85 71 102 30 31 ...
output:
-1 7245 -1 2592 6908 4267 6457 1741 2224 2384 5481 3976 -1 3848 4969 -1 5280 -1 683 2419 2784 4218 1424 6469
result:
ok 24 numbers
Test #9:
score: 10
Accepted
time: 659ms
memory: 20228kb
input:
313 31 124 139 13 199 2 100 28 51 9 3 28 143 4 111 25 188 4 114 28 189 3 167 1 254 26 45 5 174 26 302 15 281 6 165 3 302 19 238 7 119 8 271 26 148 16 24 14 9 22 78 26 160 2 5 1 308 6 190 4 124 12 67 28 258 17 71 13 297 30 71 6 27 26 61 27 96 27 86 10 51 15 118 14 237 10 112 29 6 24 305 17 19 19 234 ...
output:
831 730 6368 205 97 618 289 1583 46 2114 2463 51 390 3128 321
result:
ok 15 numbers
Test #10:
score: 10
Accepted
time: 3515ms
memory: 22328kb
input:
120 157 315 38 109 23 5 33 85 6 67 65 145 47 123 103 78 3 104 19 109 60 32 50 120 32 118 25 15 16 143 118 93 118 101 72 99 114 7 67 94 6 63 32 25 64 140 60 6 112 37 55 133 11 114 91 71 6 68 34 91 57 73 85 45 49 81 10 73 16 48 75 107 20 106 84 136 23 114 48 20 6 125 76 33 47 30 48 8 48 56 113 61 87 1...
output:
7168 5472 11642 9146 10626 767 2768 6696 8684 1578 3539 7671 -1 12023 12769 29 351 3754 4853 5983
result:
ok 20 numbers