oj.uz

Submission #710691

# Submission time Handle Problem Language Result Execution time Memory
710691 2023-03-15T15:32:36 Z pcc Skandi (COCI20_skandi) C++14
110 / 110
 479 ms 57680 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[j][i] == '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
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 32252 KB Correct.
2 Correct 18 ms 32268 KB Correct.
3 Correct 16 ms 32212 KB Correct.
4 Correct 16 ms 32216 KB Correct.
5 Correct 15 ms 32212 KB Correct.
6 Correct 21 ms 32212 KB Correct.
7 Correct 17 ms 32228 KB Correct.
8 Correct 18 ms 32324 KB Correct.
9 Correct 18 ms 32260 KB Correct.
10 Correct 14 ms 32296 KB Correct.
11 Correct 19 ms 32248 KB Correct.
12 Correct 15 ms 32296 KB Correct.
13 Correct 15 ms 32272 KB Correct.
14 Correct 16 ms 32208 KB Correct.
15 Correct 18 ms 32252 KB Correct.
16 Correct 18 ms 32320 KB Correct.
17 Correct 20 ms 32212 KB Correct.
18 Correct 20 ms 32308 KB Correct.
19 Correct 17 ms 32304 KB Correct.
20 Correct 18 ms 32324 KB Correct.
21 Correct 15 ms 32212 KB Correct.
22 Correct 18 ms 32288 KB Correct.
23 Correct 15 ms 32204 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 34060 KB Correct.
2 Correct 16 ms 32980 KB Correct.
3 Correct 16 ms 33748 KB Correct.
4 Correct 20 ms 32932 KB Correct.
5 Correct 19 ms 32980 KB Correct.
6 Correct 18 ms 32648 KB Correct.
7 Correct 17 ms 32596 KB Correct.
8 Correct 18 ms 33108 KB Correct.
9 Correct 18 ms 34424 KB Correct.
10 Correct 24 ms 34624 KB Correct.
11 Correct 26 ms 34768 KB Correct.
12 Correct 24 ms 34644 KB Correct.
13 Correct 26 ms 34644 KB Correct.
14 Correct 20 ms 34704 KB Correct.
15 Correct 28 ms 34692 KB Correct.
16 Correct 26 ms 34644 KB Correct.
17 Correct 20 ms 34608 KB Correct.
18 Correct 28 ms 34652 KB Correct.
19 Correct 18 ms 34664 KB Correct.
20 Correct 19 ms 34636 KB Correct.
21 Correct 20 ms 34740 KB Correct.
22 Correct 21 ms 34664 KB Correct.
23 Correct 19 ms 34648 KB Correct.
24 Correct 20 ms 34568 KB Correct.
25 Correct 24 ms 34644 KB Correct.
26 Correct 26 ms 34716 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 32252 KB Correct.
2 Correct 18 ms 32268 KB Correct.
3 Correct 16 ms 32212 KB Correct.
4 Correct 16 ms 32216 KB Correct.
5 Correct 15 ms 32212 KB Correct.
6 Correct 21 ms 32212 KB Correct.
7 Correct 17 ms 32228 KB Correct.
8 Correct 18 ms 32324 KB Correct.
9 Correct 18 ms 32260 KB Correct.
10 Correct 14 ms 32296 KB Correct.
11 Correct 19 ms 32248 KB Correct.
12 Correct 15 ms 32296 KB Correct.
13 Correct 15 ms 32272 KB Correct.
14 Correct 16 ms 32208 KB Correct.
15 Correct 18 ms 32252 KB Correct.
16 Correct 18 ms 32320 KB Correct.
17 Correct 20 ms 32212 KB Correct.
18 Correct 20 ms 32308 KB Correct.
19 Correct 17 ms 32304 KB Correct.
20 Correct 18 ms 32324 KB Correct.
21 Correct 15 ms 32212 KB Correct.
22 Correct 18 ms 32288 KB Correct.
23 Correct 15 ms 32204 KB Correct.
24 Correct 20 ms 34060 KB Correct.
25 Correct 16 ms 32980 KB Correct.
26 Correct 16 ms 33748 KB Correct.
27 Correct 20 ms 32932 KB Correct.
28 Correct 19 ms 32980 KB Correct.
29 Correct 18 ms 32648 KB Correct.
30 Correct 17 ms 32596 KB Correct.
31 Correct 18 ms 33108 KB Correct.
32 Correct 18 ms 34424 KB Correct.
33 Correct 24 ms 34624 KB Correct.
34 Correct 26 ms 34768 KB Correct.
35 Correct 24 ms 34644 KB Correct.
36 Correct 26 ms 34644 KB Correct.
37 Correct 20 ms 34704 KB Correct.
38 Correct 28 ms 34692 KB Correct.
39 Correct 26 ms 34644 KB Correct.
40 Correct 20 ms 34608 KB Correct.
41 Correct 28 ms 34652 KB Correct.
42 Correct 18 ms 34664 KB Correct.
43 Correct 19 ms 34636 KB Correct.
44 Correct 20 ms 34740 KB Correct.
45 Correct 21 ms 34664 KB Correct.
46 Correct 19 ms 34648 KB Correct.
47 Correct 20 ms 34568 KB Correct.
48 Correct 24 ms 34644 KB Correct.
49 Correct 26 ms 34716 KB Correct.
50 Correct 274 ms 53332 KB Correct.
51 Correct 479 ms 43296 KB Correct.
52 Correct 400 ms 54884 KB Correct.
53 Correct 266 ms 53632 KB Correct.
54 Correct 351 ms 51836 KB Correct.
55 Correct 332 ms 56140 KB Correct.
56 Correct 259 ms 54708 KB Correct.
57 Correct 230 ms 54292 KB Correct.
58 Correct 386 ms 42292 KB Correct.
59 Correct 246 ms 51876 KB Correct.
60 Correct 271 ms 54764 KB Correct.
61 Correct 394 ms 50188 KB Correct.
62 Correct 275 ms 54840 KB Correct.
63 Correct 278 ms 55040 KB Correct.
64 Correct 51 ms 38860 KB Correct.
65 Correct 264 ms 54732 KB Correct.
66 Correct 328 ms 52160 KB Correct.
67 Correct 379 ms 52768 KB Correct.
68 Correct 309 ms 56396 KB Correct.
69 Correct 278 ms 53864 KB Correct.
70 Correct 276 ms 54212 KB Correct.
71 Correct 437 ms 56188 KB Correct.
72 Correct 238 ms 56192 KB Correct.
73 Correct 359 ms 57336 KB Correct.
74 Correct 430 ms 55588 KB Correct.
75 Correct 378 ms 57680 KB Correct.