oj.uz

Submission #710163

# Submission time Handle Problem Language Result Execution time Memory
710163 2023-03-15T05:22:41 Z pcc Skandi (COCI20_skandi) C++14
55 / 110
 319 ms 28072 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 505;
vector<int> paths[mxn*mxn];
struct Edge{
    int to,cap,flow;
    Edge(){
        to = cap = flow = 0;
    }
    Edge(int tt,int cc){
        to = tt,cap = cc;
        flow = 0;
    }
};
Edge edges[mxn*mxn*4];
string arr[mxn];
pii adding[mxn][mxn];
int pp = 0;
int rcnt = 1,ccnt = 0;
int ans = 0;
int level[mxn*mxn],ptr[mxn*mxn];

bool bfs(){
    fill(level,level+mxn*mxn,-1);
    queue<int> q;
    level[0] = 0;
    q.push(0);
    while(!q.empty()){
        auto now = q.front();
        q.pop();
        for(auto id:paths[now]){
            if(edges[id].cap-edges[id].flow == 0)continue;
            int nxt = edges[id].to;
            // cout<<now<<":"<<nxt<<endl;
            if(level[nxt] != -1)continue;
            q.push(nxt);
            level[nxt] = level[now]+1;
        }
    }
    return level[1] != -1;
}

int dfs(int now,int big){
    if(now == 1)return big;
    if(!big)return 0;
    for(int &cid = ptr[now];cid<paths[now].size();cid++){
        int id = paths[now][cid];
        if(edges[id].cap-edges[id].flow<=0)continue;
        int nxt = edges[id].to;
        if(level[nxt] != level[now]+1)continue;
        int tmp = dfs(nxt,min(big,edges[id].cap-edges[id].flow));
        if(!tmp)continue;
        edges[id].flow += tmp;
        edges[id^1].flow -= tmp;
        return tmp;
    }
    return 0;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i = 0;i<n;i++){
        cin>>arr[i];
    }
    for(int i =0;i<n;i++){
        rcnt++;
        char pre = '1';
        for(int j = 0;j<m;j++){
            if(arr[i][j] == '1'&&pre != '1')rcnt++;
            pre =arr[i][j];
            adding[i][j].fs = rcnt;
        }
    }
    for(int i = 0;i<m;i++){
        ccnt++;
        char pre = '1';
        for(int j= 0;j<n;j++){
            if(arr[j][i] == '1'&&pre != '1')ccnt++;
            pre = arr[j][i];
            adding[j][i].sc = ccnt+rcnt;
        }
    }
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(arr[i][j] == '1')continue;
            paths[adding[i][j].fs].push_back(pp);
            paths[adding[i][j].sc].push_back(pp^1);
            edges[pp] = Edge(adding[i][j].sc,1);
            edges[pp^1] = Edge(adding[i][j].fs,0);
            pp += 2;
        }
    }
    for(int i = 2;i<=rcnt;i++){
        paths[0].push_back(pp);
        paths[i].push_back(pp^1);
        edges[pp] = Edge(i,1);
        edges[pp^1] = Edge(0,0);
        pp += 2;
    }
    for(int i = rcnt+1;i<=ccnt+rcnt;i++){
        paths[i].push_back(pp);
        paths[1].push_back(pp^1);
        edges[pp] = Edge(1,1);
        edges[pp^1] = Edge(i,0);
        pp += 2;
    }
    // for(int i = 2;i<=rcnt+ccnt;i++){
    //     for(auto &j:paths[i]){
    //         cout<<i<<":"<<edges[j].to<<' '<<edges[j].cap<<endl;
    //     }
    // }
    while(bfs()){
        fill(ptr,ptr+mxn*mxn,0);
        int re = 0;
        while(re = dfs(0,mxn*mxn*mxn)){
            ans += re;
        }
    }
    cout<<ans;
    return 0;
}

Compilation message

skandi.cpp: In function 'int dfs(int, int)':
skandi.cpp:51:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int &cid = ptr[now];cid<paths[now].size();cid++){
      |                             ~~~^~~~~~~~~~~~~~~~~~
skandi.cpp: In function 'int main()':
skandi.cpp:122:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  122 |         while(re = dfs(0,mxn*mxn*mxn)){
      |               ~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 9 ms 20180 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 10 ms 20200 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 10 ms 20240 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 10 ms 20192 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 13 ms 20272 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 13 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 10 ms 20320 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 9 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 10 ms 20272 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 11 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 11 ms 20300 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 9 ms 20320 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 11 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 9 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.

Subtask #2
16.0 / 32.0

# Verdict Execution time Memory Grader output
1 Partially correct 12 ms 21896 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 11 ms 20964 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 11 ms 21716 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 11 ms 20868 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 14 ms 20904 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 12 ms 20668 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 11 ms 20604 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 10 ms 21004 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 11 ms 22228 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 11 ms 22300 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 12 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 12 ms 22336 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 11 ms 22384 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 13 ms 22292 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 15 ms 22300 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 13 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 12 ms 22300 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 11 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 12 ms 22296 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 13 ms 22288 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 12 ms 22320 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 11 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 12 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 12 ms 22376 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 13 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 13 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.

Subtask #3
30.0 / 60.0

# Verdict Execution time Memory Grader output
1 Partially correct 9 ms 20180 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 10 ms 20200 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 10 ms 20240 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 10 ms 20192 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 13 ms 20272 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 13 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 10 ms 20320 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 9 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 10 ms 20272 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 11 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 11 ms 20300 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 9 ms 20320 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 11 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 9 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 12 ms 21896 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 11 ms 20964 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 11 ms 21716 KB First line is correct, but the reconstruction is not properly formatted.
27 Partially correct 11 ms 20868 KB First line is correct, but the reconstruction is not properly formatted.
28 Partially correct 14 ms 20904 KB First line is correct, but the reconstruction is not properly formatted.
29 Partially correct 12 ms 20668 KB First line is correct, but the reconstruction is not properly formatted.
30 Partially correct 11 ms 20604 KB First line is correct, but the reconstruction is not properly formatted.
31 Partially correct 10 ms 21004 KB First line is correct, but the reconstruction is not properly formatted.
32 Partially correct 11 ms 22228 KB First line is correct, but the reconstruction is not properly formatted.
33 Partially correct 11 ms 22300 KB First line is correct, but the reconstruction is not properly formatted.
34 Partially correct 12 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
35 Partially correct 12 ms 22336 KB First line is correct, but the reconstruction is not properly formatted.
36 Partially correct 11 ms 22384 KB First line is correct, but the reconstruction is not properly formatted.
37 Partially correct 13 ms 22292 KB First line is correct, but the reconstruction is not properly formatted.
38 Partially correct 15 ms 22300 KB First line is correct, but the reconstruction is not properly formatted.
39 Partially correct 13 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
40 Partially correct 12 ms 22300 KB First line is correct, but the reconstruction is not properly formatted.
41 Partially correct 11 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
42 Partially correct 12 ms 22296 KB First line is correct, but the reconstruction is not properly formatted.
43 Partially correct 13 ms 22288 KB First line is correct, but the reconstruction is not properly formatted.
44 Partially correct 12 ms 22320 KB First line is correct, but the reconstruction is not properly formatted.
45 Partially correct 11 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
46 Partially correct 12 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
47 Partially correct 12 ms 22376 KB First line is correct, but the reconstruction is not properly formatted.
48 Partially correct 13 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
49 Partially correct 13 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
50 Partially correct 124 ms 26380 KB First line is correct, but the reconstruction is not properly formatted.
51 Partially correct 274 ms 25436 KB First line is correct, but the reconstruction is not properly formatted.
52 Partially correct 251 ms 27624 KB First line is correct, but the reconstruction is not properly formatted.
53 Partially correct 115 ms 26696 KB First line is correct, but the reconstruction is not properly formatted.
54 Partially correct 163 ms 26664 KB First line is correct, but the reconstruction is not properly formatted.
55 Partially correct 161 ms 27572 KB First line is correct, but the reconstruction is not properly formatted.
56 Partially correct 102 ms 27052 KB First line is correct, but the reconstruction is not properly formatted.
57 Partially correct 108 ms 26876 KB First line is correct, but the reconstruction is not properly formatted.
58 Partially correct 319 ms 25400 KB First line is correct, but the reconstruction is not properly formatted.
59 Partially correct 120 ms 26512 KB First line is correct, but the reconstruction is not properly formatted.
60 Partially correct 134 ms 27036 KB First line is correct, but the reconstruction is not properly formatted.
61 Partially correct 262 ms 26688 KB First line is correct, but the reconstruction is not properly formatted.
62 Partially correct 156 ms 26992 KB First line is correct, but the reconstruction is not properly formatted.
63 Partially correct 134 ms 27256 KB First line is correct, but the reconstruction is not properly formatted.
64 Partially correct 33 ms 24864 KB First line is correct, but the reconstruction is not properly formatted.
65 Partially correct 138 ms 27204 KB First line is correct, but the reconstruction is not properly formatted.
66 Partially correct 203 ms 26824 KB First line is correct, but the reconstruction is not properly formatted.
67 Partially correct 244 ms 27468 KB First line is correct, but the reconstruction is not properly formatted.
68 Partially correct 170 ms 27624 KB First line is correct, but the reconstruction is not properly formatted.
69 Partially correct 131 ms 27064 KB First line is correct, but the reconstruction is not properly formatted.
70 Partially correct 135 ms 27336 KB First line is correct, but the reconstruction is not properly formatted.
71 Partially correct 272 ms 28040 KB First line is correct, but the reconstruction is not properly formatted.
72 Partially correct 104 ms 27368 KB First line is correct, but the reconstruction is not properly formatted.
73 Partially correct 218 ms 28072 KB First line is correct, but the reconstruction is not properly formatted.
74 Partially correct 283 ms 28016 KB First line is correct, but the reconstruction is not properly formatted.
75 Partially correct 207 ms 27984 KB First line is correct, but the reconstruction is not properly formatted.