oj.uz

Submission #710030

# Submission time Handle Problem Language Result Execution time Memory
710030 2023-03-15T03:55:47 Z pcc Skandi (COCI20_skandi) C++14
25 / 110
 10000 ms 26632 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);
        ans += dfs(0,mxn*mxn*mxn);
    }
    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++){
      |                             ~~~^~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 11 ms 20308 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 20308 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 10 ms 20328 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 9 ms 20224 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 15 ms 20236 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 9 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 20308 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 10 ms 20320 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 12 ms 20232 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 9 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 10 ms 20204 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 10 ms 20268 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 10 ms 20300 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 10 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 24 ms 21916 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 16 ms 21076 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 37 ms 21732 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 18 ms 21000 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 29 ms 20960 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 17 ms 20656 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 20 ms 20616 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 36 ms 21036 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 25 ms 22288 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 142 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 171 ms 22380 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 168 ms 22376 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 180 ms 22380 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 157 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 165 ms 22384 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 155 ms 22376 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 152 ms 22372 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 149 ms 22368 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 150 ms 22476 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 115 ms 22296 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 151 ms 22388 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 151 ms 22388 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 143 ms 22384 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 87 ms 22360 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 147 ms 22388 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 133 ms 22476 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 11 ms 20308 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 20308 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 10 ms 20328 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 9 ms 20224 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 15 ms 20236 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 9 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 20308 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 10 ms 20320 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 12 ms 20232 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 9 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 10 ms 20204 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 10 ms 20268 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 10 ms 20300 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 10 ms 20308 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 24 ms 21916 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 16 ms 21076 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 37 ms 21732 KB First line is correct, but the reconstruction is not properly formatted.
27 Partially correct 18 ms 21000 KB First line is correct, but the reconstruction is not properly formatted.
28 Partially correct 29 ms 20960 KB First line is correct, but the reconstruction is not properly formatted.
29 Partially correct 17 ms 20656 KB First line is correct, but the reconstruction is not properly formatted.
30 Partially correct 20 ms 20616 KB First line is correct, but the reconstruction is not properly formatted.
31 Partially correct 36 ms 21036 KB First line is correct, but the reconstruction is not properly formatted.
32 Partially correct 25 ms 22288 KB First line is correct, but the reconstruction is not properly formatted.
33 Partially correct 142 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
34 Partially correct 171 ms 22380 KB First line is correct, but the reconstruction is not properly formatted.
35 Partially correct 168 ms 22376 KB First line is correct, but the reconstruction is not properly formatted.
36 Partially correct 180 ms 22380 KB First line is correct, but the reconstruction is not properly formatted.
37 Partially correct 157 ms 22356 KB First line is correct, but the reconstruction is not properly formatted.
38 Partially correct 165 ms 22384 KB First line is correct, but the reconstruction is not properly formatted.
39 Partially correct 155 ms 22376 KB First line is correct, but the reconstruction is not properly formatted.
40 Partially correct 152 ms 22372 KB First line is correct, but the reconstruction is not properly formatted.
41 Partially correct 149 ms 22368 KB First line is correct, but the reconstruction is not properly formatted.
42 Partially correct 150 ms 22476 KB First line is correct, but the reconstruction is not properly formatted.
43 Partially correct 115 ms 22296 KB First line is correct, but the reconstruction is not properly formatted.
44 Partially correct 151 ms 22388 KB First line is correct, but the reconstruction is not properly formatted.
45 Partially correct 151 ms 22388 KB First line is correct, but the reconstruction is not properly formatted.
46 Partially correct 143 ms 22384 KB First line is correct, but the reconstruction is not properly formatted.
47 Partially correct 87 ms 22360 KB First line is correct, but the reconstruction is not properly formatted.
48 Partially correct 147 ms 22388 KB First line is correct, but the reconstruction is not properly formatted.
49 Partially correct 133 ms 22476 KB First line is correct, but the reconstruction is not properly formatted.
50 Execution timed out 10050 ms 26632 KB Time limit exceeded
51 Halted 0 ms 0 KB -