제출 #1120237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1120237		vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	84.69 / 100	2137 ms	561220 KiB

tracks

// Ali
 
// #pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 8e6+23, inf = 2e9, LG = 19,pr = 31;
vector<int> graph[sze];
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
const int asz = 4e3 +5;
int cp[asz][asz];
int n,m;
int used[sze];

int check(int a,int b){
    return (a>=0 && a<n && b>=0 && b<m);
}

void fast(){
    cin>>n>>m;
    vector<vector<char>> arr(n,vector<char>(m)); 
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>arr[i][j];
        }
    }
    int ct =1 ;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(!cp[i][j] && arr[i][j]!='.'){
                cp[i][j] = (ct++);
                queue<pair<int,int>> q;
                q.push({i,j});
                while(!q.empty()){
                    pair<int,int> node = q.front();q.pop();
                    for(int x=0;x<4;x++){
                        if(check(node.first + dx[x], node.second + dy[x]) && !cp[node.first + dx[x]][node.second + dy[x]] && arr[node.first + dx[x]][node.second +dy[x] ]==arr[i][j]){
                            cp[node.first + dx[x]][node.second + dy[x]] = cp[i][j];
                            q.push({node.first + dx[x],node.second + dy[x]});
                        }
                    }
                }
            }
        }
    }
    int a,b;
    set<pair<int,int>> var;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(cp[i][j]){
                a = cp[i][j];
                for(int x =0;x<4;x++){
                    if(check(i + dx[x], j + dy[x]) &&  cp[i + dx[x]][j+ dy[x]] && cp[i][j]!=cp[i + dx[x]][j + dy[x]]){
                        b = cp[i+dx[x]][j + dy[x]];
                        if(var.find({min(a,b),max(a,b)})==var.end()){
                            var.ins({min(a,b),max(a,b)});
                            graph[a].pb(b);
                            graph[b].pb(a);
                        }
                    }
                }
            }
        }
    }
    int ans=1;
    queue<pair<int,int>> q;
    q.push({1,1});
    used[1]=1;
    while(!q.empty()){
        pii node = q.front();q.pop();
        ans=max(ans,node.second);
        for(auto v:graph[node.first]){
            if(!used[v]){
                used[v]=1;
                q.push({v,node.second +1});
            }
        }
    }
    putr(ans);
}  
/*
5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF

1 2
2 1 3

*/
 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int tt = 1;
    // cin>>tt;
 
    while(tt--){
        fast();
    }
    return 0;
}

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