oj.uz

Submission #710678

# Submission time Handle Problem Language Result Execution time Memory
710678 2023-03-15T15:13:19 Z pcc Skandi (COCI20_skandi) C++14
55 / 110
 347 ms 52928 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];
map<int,tuple<int,int,int>> mp;
vector<int> bipath[mxn*mxn*2];
int matchx[mxn*mxn],matchy[mxn*mxn];
vector<int> choose;
bitset<mxn*mxn> vis;


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;
}

void dfsans(int now){
    vis[now] = true;
    for(auto nxt:bipath[now]){
        if(matchy[nxt]&&!vis[matchy[nxt]]){
            vis[nxt] = true;
            dfsans(matchy[nxt]);
        }
    }
    return;
}

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++){
        char pre = '0';
        for(int j = 0;j<m;j++){
            if(arr[i][j] == '1'&&pre != '1'){
                rcnt++;
                mp[rcnt] = make_tuple(i+1,j+1,0);
            }
            pre =arr[i][j];
            adding[i][j].fs = rcnt;
        }
    }
    int ccnt = rcnt;
    for(int i = 0;i<m;i++){
        char pre = '0';
        for(int j= 0;j<n;j++){
            if(arr[j][i] == '1'&&pre != '1'){
                ccnt++;
                mp[ccnt] = make_tuple(j+1,i+1,1);
            }
            pre = arr[j][i];
            adding[j][i].sc = ccnt;
        }
    }
    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;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;
    }
    while(bfs()){
        fill(ptr,ptr+mxn*mxn,0);
        int re = 0;
        while(re = dfs(0,mxn*mxn*mxn)){
            ans += re;
        }
    }
    cout<<ans<<'\n';
    for(int i = 2;i<=rcnt;i++){
        for(auto &j:paths[i]){
            int nxt = edges[j].to;
            if(nxt == 0||nxt == 1)continue;
            // cout<<i<<":"<<nxt<<endl;
            bipath[i].push_back(nxt);
            bipath[nxt].push_back(i);
            if(edges[j].flow){
                matchx[i] = nxt;
                matchy[nxt] = i;
            }
        }
    }
    for(int i = 2;i<=rcnt;i++){
        // cout<<i<<":"<<matchx[i]<<'\n';
        if(!matchx[i])dfsans(i);
    }
    for(int i = 2;i<=rcnt;i++){
        if(!vis[i])choose.push_back(i);
    }
    for(int i = rcnt+1;i<=ccnt;i++){
        // cout<<i<<":"<<vis[i]<<endl;
        if(vis[i])choose.push_back(i);
    }
    // for(int i = 2;i<=rcnt;i++){
    //     cout<<i<<":";for(auto nxt:bipath[i])cout<<nxt<<' ';cout<<endl;
    // }
    assert(choose.size() == ans);
    for(auto &i:choose){
        cout<<get<0>(mp[i])<<' '<<get<1>(mp[i])<<' '<<(get<2>(mp[i]) == 0?"DESNO\n":"DOLJE\n");
    }
    return 0;
}

Compilation message

skandi.cpp: In function 'int dfs(int, int)':
skandi.cpp:58:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int &cid = ptr[now];cid<paths[now].size();cid++){
      |                             ~~~^~~~~~~~~~~~~~~~~~
skandi.cpp: In function 'int main()':
skandi.cpp:140:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  140 |         while(re = dfs(0,mxn*mxn*mxn)){
      |               ~~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from skandi.cpp:1:
skandi.cpp:172:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  172 |     assert(choose.size() == ans);
      |            ~~~~~~~~~~~~~~^~~~~~

Subtask #1
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 32224 KB Correct.
2 Partially correct 14 ms 32220 KB First line is correct, but the reconstruction is not properly formatted.
3 Correct 16 ms 32212 KB Correct.
4 Partially correct 15 ms 32228 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 15 ms 32220 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 15 ms 32212 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 15 ms 32212 KB First line is correct, but the reconstruction is not properly formatted.
8 Correct 15 ms 32312 KB Correct.
9 Correct 15 ms 32332 KB Correct.
10 Partially correct 15 ms 32212 KB First line is correct, but the reconstruction is not properly formatted.
11 Correct 15 ms 32212 KB Correct.
12 Correct 16 ms 32212 KB Correct.
13 Correct 15 ms 32220 KB Correct.
14 Partially correct 15 ms 32224 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 15 ms 32228 KB First line is correct, but the reconstruction is not properly formatted.
16 Correct 17 ms 32212 KB Correct.
17 Correct 16 ms 32332 KB Correct.
18 Correct 16 ms 32276 KB Correct.
19 Partially correct 16 ms 32340 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 18 ms 32204 KB First line is correct, but the reconstruction is not properly formatted.
21 Correct 15 ms 32248 KB Correct.
22 Correct 17 ms 32264 KB Correct.
23 Partially correct 15 ms 32272 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 17 ms 34060 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 16 ms 32980 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 16 ms 33748 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 21 ms 32996 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 16 ms 32992 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 15 ms 32612 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 15 ms 32596 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 16 ms 33084 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 17 ms 34344 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 18 ms 34652 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 22 ms 34652 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 19 ms 34628 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 19 ms 34644 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 22 ms 34568 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 19 ms 34540 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 18 ms 34588 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 20 ms 34516 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 19 ms 34520 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 19 ms 34636 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 19 ms 34520 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 18 ms 34544 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 18 ms 34784 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 18 ms 34556 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 19 ms 34540 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 19 ms 34596 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 19 ms 34616 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 Correct 15 ms 32224 KB Correct.
2 Partially correct 14 ms 32220 KB First line is correct, but the reconstruction is not properly formatted.
3 Correct 16 ms 32212 KB Correct.
4 Partially correct 15 ms 32228 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 15 ms 32220 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 15 ms 32212 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 15 ms 32212 KB First line is correct, but the reconstruction is not properly formatted.
8 Correct 15 ms 32312 KB Correct.
9 Correct 15 ms 32332 KB Correct.
10 Partially correct 15 ms 32212 KB First line is correct, but the reconstruction is not properly formatted.
11 Correct 15 ms 32212 KB Correct.
12 Correct 16 ms 32212 KB Correct.
13 Correct 15 ms 32220 KB Correct.
14 Partially correct 15 ms 32224 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 15 ms 32228 KB First line is correct, but the reconstruction is not properly formatted.
16 Correct 17 ms 32212 KB Correct.
17 Correct 16 ms 32332 KB Correct.
18 Correct 16 ms 32276 KB Correct.
19 Partially correct 16 ms 32340 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 18 ms 32204 KB First line is correct, but the reconstruction is not properly formatted.
21 Correct 15 ms 32248 KB Correct.
22 Correct 17 ms 32264 KB Correct.
23 Partially correct 15 ms 32272 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 17 ms 34060 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 16 ms 32980 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 16 ms 33748 KB First line is correct, but the reconstruction is not properly formatted.
27 Partially correct 21 ms 32996 KB First line is correct, but the reconstruction is not properly formatted.
28 Partially correct 16 ms 32992 KB First line is correct, but the reconstruction is not properly formatted.
29 Partially correct 15 ms 32612 KB First line is correct, but the reconstruction is not properly formatted.
30 Partially correct 15 ms 32596 KB First line is correct, but the reconstruction is not properly formatted.
31 Partially correct 16 ms 33084 KB First line is correct, but the reconstruction is not properly formatted.
32 Partially correct 17 ms 34344 KB First line is correct, but the reconstruction is not properly formatted.
33 Partially correct 18 ms 34652 KB First line is correct, but the reconstruction is not properly formatted.
34 Partially correct 22 ms 34652 KB First line is correct, but the reconstruction is not properly formatted.
35 Partially correct 19 ms 34628 KB First line is correct, but the reconstruction is not properly formatted.
36 Partially correct 19 ms 34644 KB First line is correct, but the reconstruction is not properly formatted.
37 Partially correct 22 ms 34568 KB First line is correct, but the reconstruction is not properly formatted.
38 Partially correct 19 ms 34540 KB First line is correct, but the reconstruction is not properly formatted.
39 Partially correct 18 ms 34588 KB First line is correct, but the reconstruction is not properly formatted.
40 Partially correct 20 ms 34516 KB First line is correct, but the reconstruction is not properly formatted.
41 Partially correct 19 ms 34520 KB First line is correct, but the reconstruction is not properly formatted.
42 Partially correct 19 ms 34636 KB First line is correct, but the reconstruction is not properly formatted.
43 Partially correct 19 ms 34520 KB First line is correct, but the reconstruction is not properly formatted.
44 Partially correct 18 ms 34544 KB First line is correct, but the reconstruction is not properly formatted.
45 Partially correct 18 ms 34784 KB First line is correct, but the reconstruction is not properly formatted.
46 Partially correct 18 ms 34556 KB First line is correct, but the reconstruction is not properly formatted.
47 Partially correct 19 ms 34540 KB First line is correct, but the reconstruction is not properly formatted.
48 Partially correct 19 ms 34596 KB First line is correct, but the reconstruction is not properly formatted.
49 Partially correct 19 ms 34616 KB First line is correct, but the reconstruction is not properly formatted.
50 Partially correct 167 ms 49372 KB First line is correct, but the reconstruction is not properly formatted.
51 Partially correct 310 ms 42088 KB First line is correct, but the reconstruction is not properly formatted.
52 Partially correct 296 ms 50756 KB First line is correct, but the reconstruction is not properly formatted.
53 Partially correct 157 ms 49692 KB First line is correct, but the reconstruction is not properly formatted.
54 Partially correct 228 ms 48400 KB First line is correct, but the reconstruction is not properly formatted.
55 Partially correct 216 ms 51632 KB First line is correct, but the reconstruction is not properly formatted.
56 Partially correct 158 ms 50548 KB First line is correct, but the reconstruction is not properly formatted.
57 Partially correct 160 ms 50240 KB First line is correct, but the reconstruction is not properly formatted.
58 Partially correct 289 ms 41728 KB First line is correct, but the reconstruction is not properly formatted.
59 Partially correct 165 ms 48492 KB First line is correct, but the reconstruction is not properly formatted.
60 Partially correct 193 ms 50564 KB First line is correct, but the reconstruction is not properly formatted.
61 Partially correct 291 ms 47188 KB First line is correct, but the reconstruction is not properly formatted.
62 Partially correct 198 ms 50660 KB First line is correct, but the reconstruction is not properly formatted.
63 Partially correct 184 ms 50876 KB First line is correct, but the reconstruction is not properly formatted.
64 Partially correct 45 ms 39016 KB First line is correct, but the reconstruction is not properly formatted.
65 Partially correct 186 ms 50720 KB First line is correct, but the reconstruction is not properly formatted.
66 Partially correct 277 ms 48716 KB First line is correct, but the reconstruction is not properly formatted.
67 Partially correct 315 ms 49380 KB First line is correct, but the reconstruction is not properly formatted.
68 Partially correct 229 ms 51948 KB First line is correct, but the reconstruction is not properly formatted.
69 Partially correct 201 ms 50012 KB First line is correct, but the reconstruction is not properly formatted.
70 Partially correct 205 ms 50204 KB First line is correct, but the reconstruction is not properly formatted.
71 Partially correct 347 ms 51916 KB First line is correct, but the reconstruction is not properly formatted.
72 Partially correct 177 ms 51704 KB First line is correct, but the reconstruction is not properly formatted.
73 Partially correct 288 ms 52592 KB First line is correct, but the reconstruction is not properly formatted.
74 Partially correct 340 ms 51520 KB First line is correct, but the reconstruction is not properly formatted.
75 Partially correct 282 ms 52928 KB First line is correct, but the reconstruction is not properly formatted.