제출 #1305029

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305029		user184	Tracks in the Snow (BOI13_tracks)	C++20	18.85 / 100	712 ms	1114112 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 25e4+5, M=505;
char co[M][M];
int uf[ N ], mi[ N ][ 4 ], spojna[ N ], odw[ N ];
vector <int> graf[ N ];
map <pair<int,int>,bool> polo;
set <int> bylo;
queue <int> kol;

int finde( int x ){
    if( uf[x] == 0 )
        return 0;
    if( x == uf[ x ] )
        return x;
    uf[ x ] = finde( uf[ x ] );
    return uf[ x ];
}

void uni( int x, int y ){
    x = finde( x ); y = finde( y );
    mi[y][0] = min( mi[y][0], mi[x][0] );
    mi[y][1] = max( mi[y][1], mi[x][1] );
    mi[y][2] = min( mi[y][2], mi[x][0] );
    mi[y][3] = max( mi[y][3], mi[x][3] );
    uf[ x ] = y;
    return;
}

int zam( int x, int y, int ilewie ){
    x -= 1;
    x *= ilewie;
    x += y;
    return x;
}

int dfs( int x ){
    kol.push(x);
    int wyn=1;
    while( !kol.empty() ){
        int u = kol.front();
        kol.pop();
        wyn = odw[u];
        for( int i : graf[u] ){
            if( !odw[i] ){
                odw[i]=odw[u]+1;
                kol.push(i);
            }
        }
    }
    return wyn;
}

void pol( int x, int y, int do1, int do2, int ilewie ){
    if( !finde( zam(x+do1, y+do2, ilewie)) )
        return;
    if( spojna[ finde(zam(x+do1,y+do2,ilewie)) ] && spojna[ finde(zam(x,y,ilewie)) ] != spojna[ finde(zam(x+do1,y+do2,ilewie)) ] && !polo[{finde(zam(x,y,ilewie)), finde(zam(x+do1,y+do2,ilewie)) }] ){
        graf[ finde(zam(x+do1,y+do2,ilewie)) ].push_back( finde(zam(x,y,ilewie)) );
        graf[ finde(zam(x,y,ilewie)) ].push_back( finde(zam(x+do1,y+do2,ilewie)) );
        polo[ {finde(zam(x,y,ilewie)), finde(zam(x+do1,y+do2,ilewie))} ] = 1;
        polo[ {finde(zam(x+do1,y+do2,ilewie)), finde(zam(x,y,ilewie))} ] = 1;
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll ilewie, ilekol, ak = 1, odp = 0;
    char c;
    odw[0]=1; 
    cin >> ilewie >> ilekol;
    for( int i=1 ; i<=ilewie ; ++i ){
        for( int j=1 ; j<=ilekol; ++j ){
            cin >> c;
            co[i][j]=c;
            if( c == '.')
                continue;
            int w = zam(i,j,ilewie);
            uf[w] = w;
            mi[w][0] = i;
            mi[w][1] = i;
            mi[w][2] = j;
            mi[w][3] = j;
            if( co[i][j-1] == co[i][j] ){
                uni( zam(i,j,ilewie), zam(i,j-1,ilewie) );
            }
            if( co[i-1][j] == co[i][j] )
                uni( zam(i,j,ilewie), zam(i-1,j,ilewie) );
        }
    }
    for( int i=1; i<=ilewie ; ++i ){
        for( int j=1; j<=ilekol; ++j ){
            if( co[i][j] == '.' )
                continue;
            if( !spojna[ finde(zam(i,j,ilewie)) ] ){
                spojna[ finde(zam(i,j,ilewie)) ] = ak;
                ak++;
            }    
            pol( i, j, 0, -1, ilewie );
            pol( i, j, -1, 0, ilewie );
        }
    }
    for( int i=1; i<=ilewie ; ++i )
        for( int j=1; j<=ilekol; ++j ){
            int w = zam(i,j,ilewie);
            if( !odw[w] && ( mi[w][0] == 1 && mi[w][1] == ilewie ) || ( mi[w][2] == 1 && mi[w][3] == ilekol ) ){
                odw[w]=1;
                odp += dfs(w);
            }
        }
    if( finde( zam(1,1,ilewie)) )
        bylo.insert( finde( zam(1,1,ilewie) ) );
    for( int i=2 ; i <= ilewie ; ++i ){
        if( finde( zam(i,1,ilewie)) != finde( zam(i-1,1,ilewie) ) ){
            if( bylo.count(finde( zam(i,1,ilewie))) && !odw[finde(zam(1,i,ilewie))] ){
                odw[ finde( zam(i,1,ilewie)) ] = 1;
                odp += dfs(finde( zam(i,1,ilewie)));
            }
            bylo.insert( finde( zam(i,1,ilewie)) );
        }
        if( finde( zam(i,ilekol,ilewie)) != finde( zam(i-1,ilekol,ilewie) ) ){
            if( bylo.count(finde( zam(i,ilekol,ilewie))) && !odw[finde(zam(1,i,ilewie))] ){
                odw[ finde( zam(i,ilekol,ilewie)) ] = 1;
                odp += dfs(finde( zam(i,ilekol,ilewie)));
            }
            bylo.insert( finde( zam(i,ilekol,ilewie)) );
        }
        
    }
    for( int i=2; i <= ilekol; ++i ){
        if( finde( zam(1,i,ilewie)) != finde( zam(1,i-1,ilewie) ) && finde( zam(1,i,ilewie)) ){
            if( bylo.count(finde( zam(1,i,ilewie))) && !odw[finde(zam(1,i,ilewie))] ){
                odw[ finde( zam(1,i,ilewie)) ] = 1;
                odp += dfs(finde( zam(1,i,ilewie)));
            }
            bylo.insert( finde( zam(1,i,ilewie)) );
        }
        if( finde( zam(ilewie,i,ilewie)) != finde( zam(ilewie,i-1,ilewie) ) && finde( zam(ilewie,i,ilewie)) ){
            if( bylo.count(finde( zam(ilewie,i,ilewie))) && !odw[finde(zam(1,i,ilewie))] ){
                odw[ finde( zam(ilewie,i,ilewie)) ] = 1;
                odp += dfs(finde( zam(ilewie,i,ilewie)));
            }
            bylo.insert( finde( zam(ilewie,i,ilewie)) );
        }
    }
    for( int i=1; i<=ilewie ; ++i )
        for( int j=1; j<=ilekol; ++j )
            if( !odw[finde(zam(i,j,ilewie))] )
                odp += dfs( finde(zam(i,j,ilewie)) );
    cout << odp << '\n' ;

    return 0;
}

• Subtask 1: 16.6667 / 30
• Subtask 2: 2.1875 / 70