oj.uz

Submission #710035

# Submission time Handle Problem Language Result Execution time Memory
710035 2023-03-15T03:57:22 Z pcc Skandi (COCI20_skandi) C++14
25 / 110
 10000 ms 26344 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int,int>
#define fs first
#define sc second
#pragma GCC optimize("O3")
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);
        ans += dfs(0,mxn*mxn*mxn);
    }
    cout<<ans;
    return 0;
}

Compilation message

skandi.cpp: In function 'int dfs(int, int)':
skandi.cpp:52:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int &cid = ptr[now];cid<paths[now].size();cid++){
      |                             ~~~^~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 12 ms 20180 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 13 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 12 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 12 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 12 ms 20248 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 11 ms 20212 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 12 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 12 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 10 ms 20288 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 10 ms 20316 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 12 ms 20204 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 15 ms 20240 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 12 ms 20204 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 12 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 11 ms 20224 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 12 ms 20220 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 14 ms 20224 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 13 ms 20224 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 13 ms 20260 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 11 ms 20296 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 11 ms 20304 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 12 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 11 ms 20196 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 19 ms 21972 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 22 ms 21044 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 34 ms 21636 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 24 ms 20948 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 25 ms 20968 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 20 ms 20632 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 20 ms 20508 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 41 ms 20948 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 21 ms 22348 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 132 ms 22368 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 148 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 151 ms 22364 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 150 ms 22264 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 146 ms 22476 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 149 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 176 ms 22380 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 143 ms 22360 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 120 ms 22368 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 150 ms 22388 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 121 ms 22352 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 154 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 157 ms 22344 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 144 ms 22372 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 79 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 144 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 142 ms 22372 KB First line is correct, but the reconstruction is not properly formatted.

Subtask #3
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Partially correct 12 ms 20180 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 13 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 12 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 12 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 12 ms 20248 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 11 ms 20212 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 12 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 12 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 10 ms 20288 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 10 ms 20316 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 12 ms 20204 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 15 ms 20240 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 12 ms 20204 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 12 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 11 ms 20224 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 12 ms 20220 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 14 ms 20224 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 13 ms 20224 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 13 ms 20260 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 11 ms 20296 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 11 ms 20304 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 12 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 11 ms 20196 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 19 ms 21972 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 22 ms 21044 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 34 ms 21636 KB First line is correct, but the reconstruction is not properly formatted.
27 Partially correct 24 ms 20948 KB First line is correct, but the reconstruction is not properly formatted.
28 Partially correct 25 ms 20968 KB First line is correct, but the reconstruction is not properly formatted.
29 Partially correct 20 ms 20632 KB First line is correct, but the reconstruction is not properly formatted.
30 Partially correct 20 ms 20508 KB First line is correct, but the reconstruction is not properly formatted.
31 Partially correct 41 ms 20948 KB First line is correct, but the reconstruction is not properly formatted.
32 Partially correct 21 ms 22348 KB First line is correct, but the reconstruction is not properly formatted.
33 Partially correct 132 ms 22368 KB First line is correct, but the reconstruction is not properly formatted.
34 Partially correct 148 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
35 Partially correct 151 ms 22364 KB First line is correct, but the reconstruction is not properly formatted.
36 Partially correct 150 ms 22264 KB First line is correct, but the reconstruction is not properly formatted.
37 Partially correct 146 ms 22476 KB First line is correct, but the reconstruction is not properly formatted.
38 Partially correct 149 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
39 Partially correct 176 ms 22380 KB First line is correct, but the reconstruction is not properly formatted.
40 Partially correct 143 ms 22360 KB First line is correct, but the reconstruction is not properly formatted.
41 Partially correct 120 ms 22368 KB First line is correct, but the reconstruction is not properly formatted.
42 Partially correct 150 ms 22388 KB First line is correct, but the reconstruction is not properly formatted.
43 Partially correct 121 ms 22352 KB First line is correct, but the reconstruction is not properly formatted.
44 Partially correct 154 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
45 Partially correct 157 ms 22344 KB First line is correct, but the reconstruction is not properly formatted.
46 Partially correct 144 ms 22372 KB First line is correct, but the reconstruction is not properly formatted.
47 Partially correct 79 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
48 Partially correct 144 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
49 Partially correct 142 ms 22372 KB First line is correct, but the reconstruction is not properly formatted.
50 Execution timed out 10065 ms 26344 KB Time limit exceeded
51 Halted 0 ms 0 KB -