oj.uz

Submission #153561

# Submission time Handle Problem Language Result Execution time Memory
153561 2019-09-14T15:43:22 Z mhy908 Dango Maker (JOI18_dango_maker) C++14
33 / 100
 843 ms 262148 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("03")
#define pb push_back
#define INF 987654321
using namespace std;
typedef long long LL;
int n, m, x;
vector<char> str[3010];
int ans;
vector<int> id;
vector<int> par;
vector<bool> used;
vector<int> dist, A, B;
vector<vector<int> > vc, link;
vector<vector<vector<int> > >col;
unordered_map<int, int> mp;
queue<int> Q;
int findpar(int num)
{
    if(num==par[num])return num;
    return par[num]=findpar(par[num]);
}
void mergepar(int a, int b)
{
    a=findpar(a);
    b=findpar(b);
    par[a]=par[b];
}
void bfs(int p)
{
    for(int i=0; i<vc[p].size(); i++){
        if(!used[i]){
            dist[i]=0;
            Q.push(i);
        }
        else dist[i]=INF;
    }
    while(!Q.empty()){
        int a=Q.front();
        Q.pop();
        for(int b: link[vc[p][a]]){
            b=mp[b];
            if(B[b]!=-1&&dist[B[b]]==INF){
                dist[B[b]]=dist[a]+1;
                Q.push(B[b]);
            }
        }
    }
}
bool dfs(int p, int a){
    for(int b: link[vc[p][a]]){
        b=mp[b];
        if(B[b]==-1||dist[B[b]]==dist[a]+1&&dfs(p, B[b])){
            used[a]=true;
            A[a]=b;
            B[b]=a;
            return true;
        }
    }
    return false;
}
int hopcroft_carp(int p)
{
    int match=0;
    while(1){
        bfs(p);
        int flow=0;
        for(int i=0; i<vc[p].size(); i++)
            if(!used[i]&&dfs(p, i))flow++;
        if(!flow)break;
        match+=flow;
    }
    return match/2;
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++){
        str[i].pb(0);
        for(int j=1; j<=m; j++){
            char y;
            scanf(" %c", &y);
            str[i].pb(y);
        }
    }
    col.resize(n+1);
    for(int i=1; i<=n; i++)col[i].resize(m+1);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(j+2<=m)
                if(str[i][j]=='R'&&str[i][j+1]=='G'&&str[i][j+2]=='W'){
                    ++x;
                    col[i][j].pb(x);
                    col[i][j+1].pb(x);
                    col[i][j+2].pb(x);
                }
            if(i+2<=n)
                if(str[i][j]=='R'&&str[i+1][j]=='G'&&str[i+2][j]=='W'){
                    ++x;
                    col[i][j].pb(x);
                    col[i+1][j].pb(x);
                    col[i+2][j].pb(x);
                }
        }
    }
    if(x>3000000)while(1){}
    for(int i=1; i<=n; i++){
        str[i].clear();
        vector<char>().swap(str[i]);
    }
    link.resize(x+1);
    for(int i=1; i<=x; i++)link[i].resize(3, -1);
    for(int i=0; i<=x; i++)par.pb(i);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(col[i][j].size()==2){
                mergepar(col[i][j][1], col[i][j][0]);
                if(link[col[i][j][1]][0]==-1)link[col[i][j][1]][0]=col[i][j][0];
                else if(link[col[i][j][1]][1]==-1)link[col[i][j][1]][1]=col[i][j][0];
                else if(link[col[i][j][1]][2]==-1)link[col[i][j][1]][2]=col[i][j][0];
                if(link[col[i][j][0]][0]==-1)link[col[i][j][0]][0]=col[i][j][1];
                else if(link[col[i][j][0]][1]==-1)link[col[i][j][0]][1]=col[i][j][1];
                else if(link[col[i][j][0]][2]==-1)link[col[i][j][0]][2]=col[i][j][1];
            }
        }
    }
    col.clear();
    vector<vector<vector<int> > >().swap(col);
    for(int i=1; i<=x; i++){
        id.pb(findpar(i));
    }
    sort(id.begin(), id.end());
    id.erase(unique(id.begin(), id.end()), id.end());
    int maxpar=1;
    for(int i=1; i<=x; i++){
        par[i]=lower_bound(id.begin(), id.end(), par[i])-id.begin();
        maxpar=max(maxpar, par[i]+1);
    }
    id.clear();
    vector<int>().swap(id);
    vc.resize(maxpar);
    for(int i=1; i<=x; i++){
        vc[par[i]].pb(i);
    }
    par.clear();
    vector<int>().swap(par);
    for(int i=0; i<maxpar; i++){
        if(vc[i].size()==1)ans++;
        else{
            for(int j=0; j<vc[i].size(); j++)mp[vc[i][j]]=j;
            used.resize(vc[i].size()+2);
            dist.resize(vc[i].size()+2);
            A.resize(vc[i].size()+2);
            B.resize(vc[i].size()+2);
            for(int j=0; j<A.size(); j++)A[j]=B[j]=-1;
            ans+=vc[i].size()-hopcroft_carp(i);
            mp.clear();
            dist.clear();
            A.clear();
            B.clear();
            used.clear();
            vector<int>().swap(dist);
            vector<int>().swap(A);
            vector<int>().swap(B);
            vector<bool>().swap(used);
        }
    }
    printf("%d", ans);
}

Compilation message

dango_maker.cpp: In function 'void bfs(int)':
dango_maker.cpp:31:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<vc[p].size(); i++){
                  ~^~~~~~~~~~~~~
dango_maker.cpp: In function 'bool dfs(int, int)':
dango_maker.cpp:53:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         if(B[b]==-1||dist[B[b]]==dist[a]+1&&dfs(p, B[b])){
dango_maker.cpp: In function 'int hopcroft_carp(int)':
dango_maker.cpp:68:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<vc[p].size(); i++)
                      ~^~~~~~~~~~~~~
dango_maker.cpp: In function 'int main()':
dango_maker.cpp:150:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0; j<vc[i].size(); j++)mp[vc[i][j]]=j;
                          ~^~~~~~~~~~~~~
dango_maker.cpp:155:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0; j<A.size(); j++)A[j]=B[j]=-1;
                          ~^~~~~~~~~
dango_maker.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
dango_maker.cpp:82:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c", &y);
             ~~~~~^~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 424 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 0 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 424 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 0 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 3 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 380 KB Output is correct
25 Correct 2 ms 380 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 2 ms 380 KB Output is correct
29 Correct 2 ms 376 KB Output is correct
30 Correct 2 ms 368 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Correct 2 ms 376 KB Output is correct
34 Correct 2 ms 376 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 2 ms 376 KB Output is correct
37 Correct 2 ms 376 KB Output is correct
38 Correct 2 ms 420 KB Output is correct
39 Correct 2 ms 376 KB Output is correct
40 Correct 2 ms 348 KB Output is correct
41 Correct 2 ms 376 KB Output is correct
42 Correct 2 ms 376 KB Output is correct
43 Correct 2 ms 376 KB Output is correct
44 Correct 2 ms 348 KB Output is correct
45 Correct 2 ms 380 KB Output is correct
46 Correct 2 ms 376 KB Output is correct
47 Correct 2 ms 376 KB Output is correct
48 Correct 2 ms 376 KB Output is correct
49 Correct 2 ms 376 KB Output is correct
50 Correct 2 ms 376 KB Output is correct
51 Correct 2 ms 376 KB Output is correct
52 Correct 2 ms 376 KB Output is correct
53 Correct 2 ms 376 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 424 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 0 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 3 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 380 KB Output is correct
25 Correct 2 ms 380 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 2 ms 380 KB Output is correct
29 Correct 2 ms 376 KB Output is correct
30 Correct 2 ms 368 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Correct 2 ms 376 KB Output is correct
34 Correct 2 ms 376 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 2 ms 376 KB Output is correct
37 Correct 2 ms 376 KB Output is correct
38 Correct 2 ms 420 KB Output is correct
39 Correct 2 ms 376 KB Output is correct
40 Correct 2 ms 348 KB Output is correct
41 Correct 2 ms 376 KB Output is correct
42 Correct 2 ms 376 KB Output is correct
43 Correct 2 ms 376 KB Output is correct
44 Correct 2 ms 348 KB Output is correct
45 Correct 2 ms 380 KB Output is correct
46 Correct 2 ms 376 KB Output is correct
47 Correct 2 ms 376 KB Output is correct
48 Correct 2 ms 376 KB Output is correct
49 Correct 2 ms 376 KB Output is correct
50 Correct 2 ms 376 KB Output is correct
51 Correct 2 ms 376 KB Output is correct
52 Correct 2 ms 376 KB Output is correct
53 Correct 2 ms 376 KB Output is correct
54 Correct 3 ms 504 KB Output is correct
55 Correct 3 ms 760 KB Output is correct
56 Correct 6 ms 1144 KB Output is correct
57 Correct 7 ms 1272 KB Output is correct
58 Correct 157 ms 36188 KB Output is correct
59 Runtime error 843 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
60 Halted 0 ms 0 KB -