Submission #919702

#	Time	Username	Problem	Language	Result	Execution time	Memory
919702		PieArmy	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1227 ms	317600 KiB

tracks

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n';
const ll inf=2000000000000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}

void code(){
    int n,m;cin>>n>>m;
    vector<vector<int>>team(n,vector<int>(m,-1));
    char arr[n][m];for(auto &a:arr)for(char &x:a)cin>>x;
    queue<int>q;
    int las=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(arr[i][j]=='.')continue;
            if(team[i][j]!=-1)continue;
            char tur=arr[i][j];
            q.push(i*m+j);
            team[i][j]=las;
            while(q.size()){
                int pos=q.front();
                q.pop();
                int x=pos/m,y=pos%m;
                if(x+1!=n&&arr[x+1][y]==tur&&team[x+1][y]==-1){
                    team[x+1][y]=team[x][y];
                    q.push(pos+m);
                }
                if(x&&arr[x-1][y]==tur&&team[x-1][y]==-1){
                    team[x-1][y]=team[x][y];
                    q.push(pos-m);
                }
                if(y+1!=m&&arr[x][y+1]==tur&&team[x][y+1]==-1){
                    team[x][y+1]=team[x][y];
                    q.push(pos+1);
                }
                if(y&&arr[x][y-1]==tur&&team[x][y-1]==-1){
                    team[x][y-1]=team[x][y];
                    q.push(pos-1);
                }
            }
            las++;
        }
    }
    vector<vector<int>>komsu(las,vector<int>(0));
    for(int i=0;i<n;i++){
        for(int j=0;j<m-1;j++){
            if(arr[i][j]=='.'||arr[i][j+1]=='.'||team[i][j]==team[i][j+1])continue;
            komsu[team[i][j]].pb(team[i][j+1]);
            komsu[team[i][j+1]].pb(team[i][j]);
        }
    }
    for(int i=0;i<n-1;i++){
        for(int j=0;j<m;j++){
            if(arr[i][j]=='.'||arr[i+1][j]=='.'||team[i][j]==team[i+1][j])continue;
            komsu[team[i][j]].pb(team[i+1][j]);
            komsu[team[i+1][j]].pb(team[i][j]);
        }
    }
    int ans=0;
    vector<int>vis(las,0);
    vis[team[0][0]]=1;
    q.push(team[0][0]);
    while(q.size()){
        int pos=q.front();
        q.pop();
        ans=vis[pos];
        for(int x:komsu[pos]){
            if(vis[x])continue;
            vis[x]=vis[pos]+1;
            q.push(x);
        }
    }
    cout<<ans;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
    int t=1;
    if(!t)cin>>t;
    while(t--){code();cout<<endl;}
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:83:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                            ~~~~~~~^~~~~~~~~~~~~~~~~
tracks.cpp:83:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~

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