Submission #710678

#	Time	Username	Problem	Language	Result	Execution time	Memory
710678		pcc	Skandi (COCI20_skandi)	C++14	55 / 110	347 ms	52928 KiB

Main

#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 (stderr)

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 / 18
• Subtask 2: 16 / 32
• Subtask 3: 30 / 60