oj.uz

Submission #710689

# Submission time Handle Problem Language Result Execution time Memory
710689 2023-03-15T15:31:47 Z pcc Skandi (COCI20_skandi) C++14
55 / 110
 442 ms 57664 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);
            }
            else if(arr[i][j] == '1')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);
            }
            else if(arr[i][j] == '1')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);
            }
        }
    }
    for(int i = 2;i<=rcnt;i++){
        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++){
        if(vis[i])choose.push_back(i);
    }
    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:143:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  143 |         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 16 ms 32196 KB Correct.
2 Partially correct 16 ms 32304 KB First line is correct, but the reconstruction is not properly formatted.
3 Correct 16 ms 32212 KB Correct.
4 Partially correct 16 ms 32212 KB First line is correct, but the reconstruction is not properly formatted.
5 Correct 16 ms 32284 KB Correct.
6 Correct 16 ms 32212 KB Correct.
7 Partially correct 15 ms 32212 KB First line is correct, but the reconstruction is not properly formatted.
8 Correct 16 ms 32320 KB Correct.
9 Correct 17 ms 32212 KB Correct.
10 Partially correct 19 ms 32212 KB First line is correct, but the reconstruction is not properly formatted.
11 Correct 16 ms 32212 KB Correct.
12 Correct 15 ms 32212 KB Correct.
13 Correct 16 ms 32256 KB Correct.
14 Correct 16 ms 32316 KB Correct.
15 Correct 17 ms 32212 KB Correct.
16 Correct 17 ms 32308 KB Correct.
17 Correct 16 ms 32212 KB Correct.
18 Partially correct 18 ms 32320 KB First line is correct, but the reconstruction is not properly formatted.
19 Correct 18 ms 32320 KB Correct.
20 Correct 17 ms 32280 KB Correct.
21 Correct 16 ms 32212 KB Correct.
22 Partially correct 16 ms 32212 KB First line is correct, but the reconstruction is not properly formatted.
23 Correct 15 ms 32212 KB Correct.

Subtask #2
16.0 / 32.0

# Verdict Execution time Memory Grader output
1 Partially correct 16 ms 33956 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 18 ms 33088 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 20 ms 33820 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 17 ms 32928 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 21 ms 32920 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 20 ms 32676 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 22 ms 32636 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 17 ms 33072 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 17 ms 34388 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 19 ms 34728 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 19 ms 34644 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 20 ms 34660 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 22 ms 34680 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 25 ms 34644 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 21 ms 34664 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 21 ms 34644 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 21 ms 34676 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 19 ms 34720 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 21 ms 34520 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 21 ms 34644 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 20 ms 34704 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 23 ms 34632 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 22 ms 34516 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 24 ms 34788 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 20 ms 34644 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 32196 KB Correct.
2 Partially correct 16 ms 32304 KB First line is correct, but the reconstruction is not properly formatted.
3 Correct 16 ms 32212 KB Correct.
4 Partially correct 16 ms 32212 KB First line is correct, but the reconstruction is not properly formatted.
5 Correct 16 ms 32284 KB Correct.
6 Correct 16 ms 32212 KB Correct.
7 Partially correct 15 ms 32212 KB First line is correct, but the reconstruction is not properly formatted.
8 Correct 16 ms 32320 KB Correct.
9 Correct 17 ms 32212 KB Correct.
10 Partially correct 19 ms 32212 KB First line is correct, but the reconstruction is not properly formatted.
11 Correct 16 ms 32212 KB Correct.
12 Correct 15 ms 32212 KB Correct.
13 Correct 16 ms 32256 KB Correct.
14 Correct 16 ms 32316 KB Correct.
15 Correct 17 ms 32212 KB Correct.
16 Correct 17 ms 32308 KB Correct.
17 Correct 16 ms 32212 KB Correct.
18 Partially correct 18 ms 32320 KB First line is correct, but the reconstruction is not properly formatted.
19 Correct 18 ms 32320 KB Correct.
20 Correct 17 ms 32280 KB Correct.
21 Correct 16 ms 32212 KB Correct.
22 Partially correct 16 ms 32212 KB First line is correct, but the reconstruction is not properly formatted.
23 Correct 15 ms 32212 KB Correct.
24 Partially correct 16 ms 33956 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 18 ms 33088 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 20 ms 33820 KB First line is correct, but the reconstruction is not properly formatted.
27 Partially correct 17 ms 32928 KB First line is correct, but the reconstruction is not properly formatted.
28 Partially correct 21 ms 32920 KB First line is correct, but the reconstruction is not properly formatted.
29 Partially correct 20 ms 32676 KB First line is correct, but the reconstruction is not properly formatted.
30 Partially correct 22 ms 32636 KB First line is correct, but the reconstruction is not properly formatted.
31 Partially correct 17 ms 33072 KB First line is correct, but the reconstruction is not properly formatted.
32 Partially correct 17 ms 34388 KB First line is correct, but the reconstruction is not properly formatted.
33 Partially correct 19 ms 34728 KB First line is correct, but the reconstruction is not properly formatted.
34 Partially correct 19 ms 34644 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 20 ms 34660 KB First line is correct, but the reconstruction is not properly formatted.
37 Partially correct 22 ms 34680 KB First line is correct, but the reconstruction is not properly formatted.
38 Partially correct 25 ms 34644 KB First line is correct, but the reconstruction is not properly formatted.
39 Partially correct 21 ms 34664 KB First line is correct, but the reconstruction is not properly formatted.
40 Partially correct 21 ms 34644 KB First line is correct, but the reconstruction is not properly formatted.
41 Partially correct 21 ms 34676 KB First line is correct, but the reconstruction is not properly formatted.
42 Partially correct 19 ms 34720 KB First line is correct, but the reconstruction is not properly formatted.
43 Partially correct 21 ms 34520 KB First line is correct, but the reconstruction is not properly formatted.
44 Partially correct 21 ms 34644 KB First line is correct, but the reconstruction is not properly formatted.
45 Partially correct 20 ms 34704 KB First line is correct, but the reconstruction is not properly formatted.
46 Partially correct 23 ms 34632 KB First line is correct, but the reconstruction is not properly formatted.
47 Partially correct 22 ms 34516 KB First line is correct, but the reconstruction is not properly formatted.
48 Partially correct 24 ms 34788 KB First line is correct, but the reconstruction is not properly formatted.
49 Partially correct 20 ms 34644 KB First line is correct, but the reconstruction is not properly formatted.
50 Partially correct 256 ms 53220 KB First line is correct, but the reconstruction is not properly formatted.
51 Partially correct 431 ms 43420 KB First line is correct, but the reconstruction is not properly formatted.
52 Partially correct 411 ms 55032 KB First line is correct, but the reconstruction is not properly formatted.
53 Partially correct 247 ms 53632 KB First line is correct, but the reconstruction is not properly formatted.
54 Partially correct 277 ms 51776 KB First line is correct, but the reconstruction is not properly formatted.
55 Partially correct 275 ms 56112 KB First line is correct, but the reconstruction is not properly formatted.
56 Partially correct 240 ms 54704 KB First line is correct, but the reconstruction is not properly formatted.
57 Partially correct 210 ms 54352 KB First line is correct, but the reconstruction is not properly formatted.
58 Partially correct 344 ms 42316 KB First line is correct, but the reconstruction is not properly formatted.
59 Partially correct 226 ms 51896 KB First line is correct, but the reconstruction is not properly formatted.
60 Partially correct 259 ms 54636 KB First line is correct, but the reconstruction is not properly formatted.
61 Partially correct 379 ms 50188 KB First line is correct, but the reconstruction is not properly formatted.
62 Partially correct 237 ms 54804 KB First line is correct, but the reconstruction is not properly formatted.
63 Partially correct 248 ms 54984 KB First line is correct, but the reconstruction is not properly formatted.
64 Partially correct 50 ms 38888 KB First line is correct, but the reconstruction is not properly formatted.
65 Partially correct 244 ms 54748 KB First line is correct, but the reconstruction is not properly formatted.
66 Partially correct 311 ms 52068 KB First line is correct, but the reconstruction is not properly formatted.
67 Partially correct 374 ms 52912 KB First line is correct, but the reconstruction is not properly formatted.
68 Partially correct 307 ms 56304 KB First line is correct, but the reconstruction is not properly formatted.
69 Partially correct 253 ms 54028 KB First line is correct, but the reconstruction is not properly formatted.
70 Partially correct 278 ms 54284 KB First line is correct, but the reconstruction is not properly formatted.
71 Partially correct 409 ms 56252 KB First line is correct, but the reconstruction is not properly formatted.
72 Partially correct 268 ms 56260 KB First line is correct, but the reconstruction is not properly formatted.
73 Partially correct 387 ms 57300 KB First line is correct, but the reconstruction is not properly formatted.
74 Partially correct 442 ms 55588 KB First line is correct, but the reconstruction is not properly formatted.
75 Partially correct 343 ms 57664 KB First line is correct, but the reconstruction is not properly formatted.