QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #92572 | #6166. 世纪大逃亡 | donghanwen1225 | 100 ✓ | 3411ms | 22304kb | C++14 | 2.1kb | 2023-03-30 18:56:19 | 2023-03-30 18:56:23 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int inf=1<<30;
int n,m,q,s,t,mf,mc,px[200005],py[200005];int fx[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int tot=1,fir[400005],cur[400005],nxt[2000005],to[2000005],cap[2000005],val[2000005];
int vis[400005],rq[400005],dis[400005];
int ch(int x,int y){return (x-1)*m+y;}
void ins(int x,int y,int z,int w)
{
nxt[++tot]=fir[x];
fir[x]=tot;
to[tot]=y;
cap[tot]=z;val[tot]=w;
}
bool spfa()
{
for(int i=1;i<=t;i++) dis[i]=inf,cur[i]=fir[i],vis[i]=rq[i]=0;
queue<int> q;q.push(s);vis[s]=0,rq[s]=1;dis[s]=0;
while(!q.empty())
{
int now=q.front();q.pop();
for(int i=fir[now];i;i=nxt[i])
if(cap[i]&&dis[to[i]]>dis[now]+val[i])
{
dis[to[i]]=dis[now]+val[i];
if(!vis[to[i]])
{
vis[to[i]]=1;
rq[to[i]]++;
q.push(to[i]);
if(rq[to[i]]>t) return 0;
}
}
vis[now]=0;
}
return (dis[t]!=inf);
}
int dfs(int now,int sum)
{
if(vis[now]||!sum) return 0;
if(now==t) return sum;
vis[now]=1;int res=0,k=0;
for(int i=cur[now];i&∑i=nxt[i])
{
cur[now]=i;
if(!vis[to[i]]&&cap[i]&&dis[to[i]]==dis[now]+val[i])
{
k=dfs(to[i],min(cap[i],sum));
if(!k) dis[to[i]]=inf;
else
{
cap[i]-=k;cap[i^1]+=k;
res+=k;sum-=k;mc+=val[i];
}
}
}
vis[now]=0;return res;
}
int main()
{
ios::sync_with_stdio(false);
while(cin>>n>>m>>q)
{
for(int i=1;i<=q;i++) cin>>px[i]>>py[i];
s=2*n*m+1;t=2*n*m+2;mf=mc=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int cp=ch(i,j);
ins(cp,cp+n*m,1,0),ins(cp+n*m,cp,0,0);
for(int k=0;k<4;k++)
{
int tx=i+fx[k][0],ty=j+fx[k][1],np=ch(tx,ty);
if(tx<=0||ty<=0||tx>n||ty>m) continue;
ins(cp+n*m,np,1,1),ins(np,cp+n*m,0,-1);
}
if(i==1||i==n||j==1||j==m) ins(cp+n*m,t,1,0),ins(t,cp+n*m,0,0);
}
for(int i=1;i<=q;i++)
{
int cp=ch(px[i],py[i]);
ins(s,cp,1,0),ins(cp,s,0,0);
}
while(spfa()) mf+=dfs(s,inf);
if(mf<q) cout<<"-1\n";
else cout<<mc<<"\n";
for(int i=1;i<=t;i++) fir[i]=cur[i]=0;tot=1;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 5ms
memory: 15844kb
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: 39ms
memory: 15900kb
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: 81ms
memory: 19812kb
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: 368ms
memory: 20028kb
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: 682ms
memory: 18208kb
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: 1439ms
memory: 22060kb
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: 968ms
memory: 18108kb
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: 3411ms
memory: 18440kb
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: 592ms
memory: 20208kb
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: 3224ms
memory: 22304kb
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