QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#92509#6166. 世纪大逃亡abcdefg100 ✓3596ms24240kbC++173.1kb2023-03-30 17:26:422023-03-30 17:26:44

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-30 17:26:44]
  • 评测
  • 测评结果:100
  • 用时:3596ms
  • 内存:24240kb
  • [2023-03-30 17:26:42]
  • 提交

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