oj.uz

Submission #539430

# Submission time Handle Problem Language Result Execution time Memory
539430 2022-03-18T21:57:12 Z Antekb Dango Maker (JOI18_dango_maker) C++14
13 / 100
 49 ms 70876 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
using ll=long long;
const int N=3005, M=3e6+5;
const ll INF=1e18;
vector<int> E[M];
int vis[M], match[M];
int co[N][N], poz[N][N], pio[N][N];
int col=1;
bool dfs(int v){
    vis[v]=col;
    for(int u:E[v]){
        if(!match[u]){
            match[u]=v;
            return 1;
        }
        else{
            if(vis[match[u]]!=col && dfs(match[u])){
                match[u]=v;
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    int n, m;
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        string s;
        cin>>s;
        for(int j=0; j<m; j++){
            if(s[j]=='R')co[i][j+1]=1;
            else if(s[j]=='G')co[i][j+1]=2;
            else co[i][j+1]=3;
        }
    }
    int wsk1=0, wsk2=0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(co[i-1][j]==1 && co[i][j]==2 && co[i+1][j]==3){
                pio[i][j]=++wsk1;
            }
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(co[i][j-1]==1 && co[i][j]==2 && co[i][j+1]==3){
                poz[i][j]=++wsk2;
            }
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(pio[i][j] && poz[i-1][j+1])E[pio[i][j]].push_back(poz[i-1][j+1]);
            if(pio[i][j] && poz[i+1][j-1])E[pio[i][j]].push_back(poz[i+1][j-1]);
        }
    }
    int ans=wsk1+wsk2;
    for(int i=1; i<=wsk1; i++){
        if(dfs(i))ans--;
        else{
            col++;
            if(dfs(i))ans--;
        }
    }
    cout<<ans;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 70856 KB Output is correct
2 Correct 43 ms 70876 KB Output is correct
3 Correct 38 ms 70732 KB Output is correct
4 Correct 41 ms 70664 KB Output is correct
5 Correct 38 ms 70692 KB Output is correct
6 Correct 49 ms 70740 KB Output is correct
7 Correct 40 ms 70736 KB Output is correct
8 Correct 39 ms 70744 KB Output is correct
9 Correct 40 ms 70756 KB Output is correct
10 Correct 40 ms 70784 KB Output is correct
11 Correct 40 ms 70768 KB Output is correct
12 Correct 40 ms 70760 KB Output is correct
13 Correct 39 ms 70764 KB Output is correct
14 Correct 43 ms 70760 KB Output is correct
15 Correct 38 ms 70732 KB Output is correct
16 Correct 44 ms 70724 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 70856 KB Output is correct
2 Correct 43 ms 70876 KB Output is correct
3 Correct 38 ms 70732 KB Output is correct
4 Correct 41 ms 70664 KB Output is correct
5 Correct 38 ms 70692 KB Output is correct
6 Correct 49 ms 70740 KB Output is correct
7 Correct 40 ms 70736 KB Output is correct
8 Correct 39 ms 70744 KB Output is correct
9 Correct 40 ms 70756 KB Output is correct
10 Correct 40 ms 70784 KB Output is correct
11 Correct 40 ms 70768 KB Output is correct
12 Correct 40 ms 70760 KB Output is correct
13 Correct 39 ms 70764 KB Output is correct
14 Correct 43 ms 70760 KB Output is correct
15 Correct 38 ms 70732 KB Output is correct
16 Correct 44 ms 70724 KB Output is correct
17 Incorrect 38 ms 70760 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 70856 KB Output is correct
2 Correct 43 ms 70876 KB Output is correct
3 Correct 38 ms 70732 KB Output is correct
4 Correct 41 ms 70664 KB Output is correct
5 Correct 38 ms 70692 KB Output is correct
6 Correct 49 ms 70740 KB Output is correct
7 Correct 40 ms 70736 KB Output is correct
8 Correct 39 ms 70744 KB Output is correct
9 Correct 40 ms 70756 KB Output is correct
10 Correct 40 ms 70784 KB Output is correct
11 Correct 40 ms 70768 KB Output is correct
12 Correct 40 ms 70760 KB Output is correct
13 Correct 39 ms 70764 KB Output is correct
14 Correct 43 ms 70760 KB Output is correct
15 Correct 38 ms 70732 KB Output is correct
16 Correct 44 ms 70724 KB Output is correct
17 Incorrect 38 ms 70760 KB Output isn't correct
18 Halted 0 ms 0 KB -