Submission #1289515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289515		bobtheguy	Tracks in the Snow (BOI13_tracks)	C++20	40.94 / 100	1648 ms	1114112 KiB

tracks

#include<bits/stdc++.h>
#define pll pair<int,int>
using namespace std;
 const int dx[4]={1,-1,0,0};
 const int dy[4]={0,0,-1,1};
 int id[4010][4010],a[4010][4010],cnt=0,x,y,h,w,i,j;
 char c;
 vector<pll> adj[10*1000010];
 int d[10*1000010];
 bool visited[10*1000010];
priority_queue<pll,vector<pll>,greater<pll>> pq;
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>h>>w;
    for (i=1;i<=h;i++){
        for (j=1;j<=w;j++){
            cin>>c;
            if (c=='R'){
                a[i][j]=1;
                id[i][j]=++cnt;
            }
            else if (c=='F'){
                a[i][j]=2;
                id[i][j]=++cnt;
            }
            else a[i][j]=0;
        }
    }
    for (i=1;i<=h;i++){
        for (j=1;j<=w;j++){
            for (int k=0;k<4;k++){
                x=dx[k]+i;y=dy[k]+j;
                if (x<0||y<0||x>h||y>w) continue;
                if (a[i][j]==0||a[x][y]==0) continue;
                if (a[i][j]==a[x][y]){
                    adj[id[i][j]].push_back({0,id[x][y]});
                    adj[id[x][y]].push_back({0,id[i][j]});
                }
                else{
                    adj[id[i][j]].push_back({1,id[x][y]});
                    adj[id[x][y]].push_back({1,id[i][j]});
                }
            }
        }
    }
    for (i=1;i<=cnt;i++) d[i]=1e9;
    d[1]=0;
    pq.push({0,1});
    while (!pq.empty()){
        int u=pq.top().second;
        pq.pop();
        if (visited[u]) continue;
        visited[u]=1;
        for (auto pr:adj[u]){
            int w=pr.first,v=pr.second;
            if (d[v]>d[u]+w){
                d[v]=d[u]+w;
                pq.push({d[v],v});
            }
        }
    }
    int ans=0;
    for (i=1;i<=cnt;i++){
        if (d[i]<1e9) ans=max(ans,d[i]);
    }
    cout<<ans+1;
}

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