oj.uz

Submission #710685

# Submission time Handle Problem Language Result Execution time Memory
710685 2023-03-15T15:24:32 Z pcc Skandi (COCI20_skandi) C++14
55 / 110
 376 ms 57776 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*2],matchy[mxn*mxn*2];
vector<int> choose;
bitset<mxn*mxn*2> 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;
}
set<int> st;

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;
                st.insert(i);
                st.insert(nxt);
            }
        }
    }
    assert(st.size() == ans*2);
    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:141:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  141 |         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:161:22: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  161 |     assert(st.size() == ans*2);
      |            ~~~~~~~~~~^~~~~~~~
skandi.cpp:176:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  176 |     assert(choose.size() == ans);
      |            ~~~~~~~~~~~~~~^~~~~~

Subtask #1
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 32212 KB Correct.
2 Partially correct 15 ms 32388 KB First line is correct, but the reconstruction is not properly formatted.
3 Correct 16 ms 32212 KB Correct.
4 Partially correct 16 ms 32304 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 15 ms 32212 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 15 ms 32196 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 32212 KB Correct.
9 Correct 16 ms 32212 KB Correct.
10 Partially correct 15 ms 32280 KB First line is correct, but the reconstruction is not properly formatted.
11 Correct 16 ms 32212 KB Correct.
12 Correct 16 ms 32324 KB Correct.
13 Correct 15 ms 32192 KB Correct.
14 Partially correct 15 ms 32212 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 15 ms 32276 KB First line is correct, but the reconstruction is not properly formatted.
16 Correct 16 ms 32296 KB Correct.
17 Correct 16 ms 32212 KB Correct.
18 Correct 16 ms 32212 KB Correct.
19 Partially correct 16 ms 32196 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 15 ms 32212 KB First line is correct, but the reconstruction is not properly formatted.
21 Correct 17 ms 32248 KB Correct.
22 Correct 15 ms 32212 KB Correct.
23 Partially correct 19 ms 32268 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 33088 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 17 ms 33748 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 15 ms 32988 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 17 ms 33044 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 16 ms 32724 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 16 ms 32608 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 17 ms 33108 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 19 ms 34388 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 21 ms 34728 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 20 ms 34652 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 20 ms 34644 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 19 ms 34636 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 20 ms 34688 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 20 ms 34644 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 19 ms 34644 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 20 ms 34652 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 20 ms 34644 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 21 ms 34684 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 19 ms 34552 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 19 ms 34660 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 22 ms 34644 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 20 ms 34680 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 18 ms 34472 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 20 ms 34644 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 19 ms 34636 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 16 ms 32212 KB Correct.
2 Partially correct 15 ms 32388 KB First line is correct, but the reconstruction is not properly formatted.
3 Correct 16 ms 32212 KB Correct.
4 Partially correct 16 ms 32304 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 15 ms 32212 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 15 ms 32196 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 32212 KB Correct.
9 Correct 16 ms 32212 KB Correct.
10 Partially correct 15 ms 32280 KB First line is correct, but the reconstruction is not properly formatted.
11 Correct 16 ms 32212 KB Correct.
12 Correct 16 ms 32324 KB Correct.
13 Correct 15 ms 32192 KB Correct.
14 Partially correct 15 ms 32212 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 15 ms 32276 KB First line is correct, but the reconstruction is not properly formatted.
16 Correct 16 ms 32296 KB Correct.
17 Correct 16 ms 32212 KB Correct.
18 Correct 16 ms 32212 KB Correct.
19 Partially correct 16 ms 32196 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 15 ms 32212 KB First line is correct, but the reconstruction is not properly formatted.
21 Correct 17 ms 32248 KB Correct.
22 Correct 15 ms 32212 KB Correct.
23 Partially correct 19 ms 32268 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 33088 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 17 ms 33748 KB First line is correct, but the reconstruction is not properly formatted.
27 Partially correct 15 ms 32988 KB First line is correct, but the reconstruction is not properly formatted.
28 Partially correct 17 ms 33044 KB First line is correct, but the reconstruction is not properly formatted.
29 Partially correct 16 ms 32724 KB First line is correct, but the reconstruction is not properly formatted.
30 Partially correct 16 ms 32608 KB First line is correct, but the reconstruction is not properly formatted.
31 Partially correct 17 ms 33108 KB First line is correct, but the reconstruction is not properly formatted.
32 Partially correct 19 ms 34388 KB First line is correct, but the reconstruction is not properly formatted.
33 Partially correct 21 ms 34728 KB First line is correct, but the reconstruction is not properly formatted.
34 Partially correct 20 ms 34652 KB First line is correct, but the reconstruction is not properly formatted.
35 Partially correct 20 ms 34644 KB First line is correct, but the reconstruction is not properly formatted.
36 Partially correct 19 ms 34636 KB First line is correct, but the reconstruction is not properly formatted.
37 Partially correct 20 ms 34688 KB First line is correct, but the reconstruction is not properly formatted.
38 Partially correct 20 ms 34644 KB First line is correct, but the reconstruction is not properly formatted.
39 Partially correct 19 ms 34644 KB First line is correct, but the reconstruction is not properly formatted.
40 Partially correct 20 ms 34652 KB First line is correct, but the reconstruction is not properly formatted.
41 Partially correct 20 ms 34644 KB First line is correct, but the reconstruction is not properly formatted.
42 Partially correct 21 ms 34684 KB First line is correct, but the reconstruction is not properly formatted.
43 Partially correct 19 ms 34552 KB First line is correct, but the reconstruction is not properly formatted.
44 Partially correct 19 ms 34660 KB First line is correct, but the reconstruction is not properly formatted.
45 Partially correct 22 ms 34644 KB First line is correct, but the reconstruction is not properly formatted.
46 Partially correct 20 ms 34680 KB First line is correct, but the reconstruction is not properly formatted.
47 Partially correct 18 ms 34472 KB First line is correct, but the reconstruction is not properly formatted.
48 Partially correct 20 ms 34644 KB First line is correct, but the reconstruction is not properly formatted.
49 Partially correct 19 ms 34636 KB First line is correct, but the reconstruction is not properly formatted.
50 Partially correct 184 ms 53220 KB First line is correct, but the reconstruction is not properly formatted.
51 Partially correct 356 ms 43296 KB First line is correct, but the reconstruction is not properly formatted.
52 Partially correct 352 ms 54916 KB First line is correct, but the reconstruction is not properly formatted.
53 Partially correct 186 ms 53704 KB First line is correct, but the reconstruction is not properly formatted.
54 Partially correct 243 ms 51804 KB First line is correct, but the reconstruction is not properly formatted.
55 Partially correct 260 ms 56176 KB First line is correct, but the reconstruction is not properly formatted.
56 Partially correct 198 ms 54744 KB First line is correct, but the reconstruction is not properly formatted.
57 Partially correct 193 ms 54356 KB First line is correct, but the reconstruction is not properly formatted.
58 Partially correct 348 ms 42408 KB First line is correct, but the reconstruction is not properly formatted.
59 Partially correct 201 ms 51924 KB First line is correct, but the reconstruction is not properly formatted.
60 Partially correct 264 ms 54668 KB First line is correct, but the reconstruction is not properly formatted.
61 Partially correct 315 ms 50188 KB First line is correct, but the reconstruction is not properly formatted.
62 Partially correct 257 ms 54892 KB First line is correct, but the reconstruction is not properly formatted.
63 Partially correct 243 ms 54956 KB First line is correct, but the reconstruction is not properly formatted.
64 Partially correct 42 ms 38980 KB First line is correct, but the reconstruction is not properly formatted.
65 Partially correct 219 ms 54740 KB First line is correct, but the reconstruction is not properly formatted.
66 Partially correct 293 ms 52148 KB First line is correct, but the reconstruction is not properly formatted.
67 Partially correct 344 ms 52828 KB First line is correct, but the reconstruction is not properly formatted.
68 Partially correct 259 ms 56428 KB First line is correct, but the reconstruction is not properly formatted.
69 Partially correct 218 ms 54112 KB First line is correct, but the reconstruction is not properly formatted.
70 Partially correct 225 ms 54372 KB First line is correct, but the reconstruction is not properly formatted.
71 Partially correct 376 ms 56304 KB First line is correct, but the reconstruction is not properly formatted.
72 Partially correct 202 ms 56316 KB First line is correct, but the reconstruction is not properly formatted.
73 Partially correct 325 ms 57320 KB First line is correct, but the reconstruction is not properly formatted.
74 Partially correct 371 ms 55624 KB First line is correct, but the reconstruction is not properly formatted.
75 Partially correct 343 ms 57776 KB First line is correct, but the reconstruction is not properly formatted.