Submission #1305424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305424		user184	Tracks in the Snow (BOI13_tracks)	C++20	0 / 100	2108 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 ], byl[ N ];
vector <int> graf[ N ];
map <pair<int,int>,bool> polo;
set <int> bylo;
queue <int> kol;
priority_queue <pair<int,int>> pri;

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 );
    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 dij(){
    int wyn = 0, sp, u, v;
    while( !pri.empty() ){
        u = pri.top().first; v = pri.top().second ; 
        pri.pop();
        if( byl[v] != u || finde(v) != v )
            continue;
        wyn++ ;
        odw[v] = 1;
        sp = v;
        for( int i : graf[v] ){
            if( odw[i] )
                continue;
            byl[i]--;
            if( sp != v )
                for( int j : graf[finde(sp)])
                    if( !polo[ {finde(i),j} ] ){
                        graf[finde(i)].push_back(j);
                        polo[ {finde(i),j} ] = 1;
                        polo[ {j, finde(i)} ] = 1;
                    }
            uni( sp, i );
            sp = i;
            pri.push( {byl[i], i} );
        }
    }
    return wyn;
}

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,ilekol);
            uf[w] = w;
            mi[w][0] = i;
            mi[w][1] = i;
            mi[w][2] = j;
            mi[w][3] = j;
            if( j != 1 && co[i][j-1] == co[i][j] ){
                uni( zam(i,j,ilekol), zam(i,j-1,ilekol) );
            }
            if( i != 1 && co[i-1][j] == co[i][j] )
                uni( zam(i,j,ilekol), zam(i-1,j,ilekol) );
        }
    }
    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,ilekol)) ] ){
                spojna[ finde(zam(i,j,ilekol)) ] = ak;
                ak++;
            }    
            pol( i, j, 0, -1, ilekol );
            pol( i, j, -1, 0, ilekol );
        }
    }
    for( int i = 0 ; i <= ilewie*ilekol ; ++i ){
        if( finde(i) && !byl[ finde(i)] ){
            byl[ finde(i) ] = graf[finde(i)].size()+1;
            pri.push( {byl[finde(i)], finde(i)} );
        }
    }
    cout << dij() << '\n';;

    return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70