oj.uz

Submission #66836

# Submission time Handle Problem Language Result Execution time Memory
66836 2018-08-12T12:13:43 Z yusufake Dango Maker (JOI18_dango_maker) C++
0 / 100
 2000 ms 263168 KB 
#include<bits/stdc++.h> 
using namespace std; 
 
#define mp make_pair 
#define pb push_back 
#define st first 
#define nd second 
 
typedef long long ll; 
typedef pair < int , int > pp; 
const int mod = 1e9 + 7; 
const int N   = 3e3 + 3; 

vector < int > u,v;
vector < pp > V[N*N];
pp Q[N*N];
int H[N][N][2],P[N*N],T[N*N],m,n,i,j,x,y,ans,nn,z,fl,sz,h,l,r;
char A[N][N];

void f(int x, int y, int h) { V[x].pb(mp(y,h)); T[x] = T[y] = 1; }

void g(int x, int y){
    for(int i=0; i<V[x].size(); i++)
        if(V[x][i].st == y){
            V[x][i].nd = 1 - V[x][i].nd;
            return;
        }
}

int main(){
    scanf("%d%d",&m,&n);
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
            scanf(" %c", &A[i][j]);
    for(i=1;i<=m;i++)
        for(j=1;j<=n-2;j++)
            if(A[i][j] == 'R' && A[i][j+1] == 'G' && A[i][j+2] == 'W'){
                H[x][y][0] = ++sz;
                u.pb(sz);
            }
    for(i=1;i<=m-2;i++)
        for(j=1;j<=n;j++)
            if(A[i][j] == 'R' && A[i+1][j] == 'G' && A[i+2][j] == 'W'){
                H[x][y][1] = ++sz;
                v.pb(sz);
            }
        
    for(i=1;i<=m;i++)
        for(j=1;j<=n-2;j++)
            if(A[i][j] == 'R' && A[i][j+1] == 'G' && A[i][j+2] == 'W'){
                h = 0;
                x = i; y = j;
                 if(x <= m-2 && A[x+1][y] == 'G' && A[x+2][y] == 'W') f(H[x][y][h],H[x][y][!h],1);
                 if(x <= m-1 && x >= 2 && A[x-1][y+1] == 'R' && A[x+1][y+1] == 'W') f(H[x][y][h],H[x-1][y+1][!h],1);
                 if(x >= 3 && A[x-2][y+2] == 'R' && A[x-1][y+2] == 'G') f(H[x][y][h],H[x-2][y+2][!h],1);
            }
    for(i=1;i<=m-2;i++)
        for(j=1;j<=n;j++){
            h = 1;
            x = i; y = j;
            if(A[i][j] == 'R' && A[i+1][j] == 'G' && A[i+2][j] == 'W'){
                if(y <= n-2 && A[x][y+1] == 'G' && A[x][y+2] == 'W') f(H[x][y][h],H[x][y][!h],0);
                if(y >= 2 && y <= n-1 && A[x+1][y-1] == 'R' && A[x+1][y+1] == 'W') f(H[x][y][h],H[x+1][y-1][!h],0);
                if(y >= 3 && A[x+2][y-2] == 'R' && A[x+2][y-1] == 'G') f(H[x][y][h],H[x+2][y-2][!h],0);
            }
        }
    
    for(i=1;i<=sz;i++) fl += !T[i];
    
    for(auto x : u){
        V[0].pb(mp(x,1));
        V[x].pb(mp(0,0));
    }
    for(auto x : v){
        V[x].pb(mp(sz+1,1));
        V[sz+1].pb(mp(x,0));
    }

    for(;; fl++){
        l = r = 0;
        Q[++r] = mp(0,-1);
        P[sz+1] = -1;
        for(;l<r;){
            x = Q[++l].st;
            P[x] = Q[l].nd;
            if(x == sz+1) break;
            for(auto y : V[x])
                if(y.nd)
                    Q[++r] = mp(y.st,x);
        }

        if(P[sz+1] == -1) break;
        
        else{
            for(x=sz+1; x ; x = P[x]){
                g(x,P[x]); g(P[x],x);
            }
        }
    }
    
    printf("%d",fl);
    return 0;
}

Compilation message

dango_maker.cpp: In function 'void g(int, int)':
dango_maker.cpp:23:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<V[x].size(); i++)
                  ~^~~~~~~~~~~~
dango_maker.cpp: In function 'int main()':
dango_maker.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&m,&n);
     ~~~~~^~~~~~~~~~~~~~
dango_maker.cpp:34:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c", &A[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 212216 KB Output is correct
2 Correct 199 ms 212332 KB Output is correct
3 Correct 178 ms 212332 KB Output is correct
4 Correct 176 ms 212332 KB Output is correct
5 Correct 182 ms 212332 KB Output is correct
6 Execution timed out 2074 ms 263168 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 212216 KB Output is correct
2 Correct 199 ms 212332 KB Output is correct
3 Correct 178 ms 212332 KB Output is correct
4 Correct 176 ms 212332 KB Output is correct
5 Correct 182 ms 212332 KB Output is correct
6 Execution timed out 2074 ms 263168 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 212216 KB Output is correct
2 Correct 199 ms 212332 KB Output is correct
3 Correct 178 ms 212332 KB Output is correct
4 Correct 176 ms 212332 KB Output is correct
5 Correct 182 ms 212332 KB Output is correct
6 Execution timed out 2074 ms 263168 KB Time limit exceeded
7 Halted 0 ms 0 KB -