제출 #533137

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
533137		iamvaruag	Tracks in the Snow (BOI13_tracks)	C++17	0 / 100	2049 ms	987628 KiB

tracks

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<b;i++)
#define all(a) (a).begin(),(a).end()
#define ps(x,y) fixed<<setprecision(y)<<x          //cout<<ps(ans,5);
#define sz(a) ((int) (a).size())//this is to avoid common error in far manager
#define fastIO ios::sync_with_stdio(0);cin.tie(0);
#define mod 1000000007
#define count_1(x) __builtin_popcountll(x)
#define count_0(x) __builtin_ctzll(x)
#define gcd __gcd
typedef tree<int, null_type,less<int>, rb_tree_tag, tree_order_statistics_node_update > pbds;//*find_by_order(index) order_of_key
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
    int operator()(int x) const { return x ^ RANDOM; }
};
template<typename T1,typename T2>
using umap=gp_hash_table<T1,T2,chash>;
int powmod(int a, int b){a%=mod;int res = 1;while(b>0){if(b&1)res=(res * a)%mod;a=(a*a)%mod;b >>= 1;}return res;}
int power(int a, int b){int res = 1;while(b>0){if(b&1)res=(res * a);a=(a*a);b >>= 1;}return res;}
int inv(int n){return powmod(n,mod-2);}
const int dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};
//bool ok(int x,int y){return x>=1 && y>=1 && x<=n && y<=n;}
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif
void IO(string s){
fastIO
if(s.empty()){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
freopen("error.txt","w",stderr);
#endif
}
else{
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);  
}
}
void solve(){
int n,m;cin>>n>>m;
vector<vector<char>> arr(n+1,vector<char>(m+1));
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        cin>>arr[i][j];
    }
}
auto ok=[&](int x,int y){
return x>=1 and y>=1 and x<=n and y<=m;
};
vector<vector<int>>vis(n+1,vector<int>(m+1,0));
auto dfs=[&](pair<int,int> v,int parent,auto&& dfs)->void{
    vis[v.first][v.second]=parent;
 for(int i=0;i<4;i++){
    int newx=v.first+dx[i],newy=v.second+dy[i];
    if(ok(newx,newy)){
       if(!vis[newx][newy] and arr[newx][newy]==arr[v.first][v.second])dfs({newx,newy},parent,dfs);
    }
 }
};
int cnt=1;
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(!vis[i][j]){
            dfs({i,j},cnt,dfs);
            cnt++;
        }
    }
}
deque<pair<int,int>> q;
int dist[n+1][m+1];
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dist[i][j]=INT_MAX;
q.push_back({1,1});
dist[1][1]=0;
while(sz(q)!=0){
pair<int,int> v=q.front();q.pop_front();
for(int i=0;i<4;i++){
    int newx=v.first+dx[i],newy=v.second+dy[i];
    if(ok(newx,newy)){
        if(dist[newx][newy]==INT_MAX){
            if(vis[newx][newy]==vis[v.first][v.second]){
                if(dist[newx][newy]>dist[v.first][v.second]){
                    dist[newx][newy]=dist[v.first][v.second];
                q.push_front({newx,newy});
                }
            }
            else{
                if(dist[newx][newy]>dist[v.first][v.second]+1){
                  dist[newx][newy]=dist[v.first][v.second]+1;
                  q.push_back({newx,newy});
                }
            }
        }
    }
}
}
int ans=INT_MIN;
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        ans=max(ans,dist[i][j]);
    }
}
cout<<ans<<endl;
}
int32_t main(){
fastIO
// IO("");
int t=1;
//cin>>t;
for(int i=1;i<=t;i++){
//cout<<"Case #"<<i<<": ";
solve();
}
return 0;}

컴파일 시 표준 에러 (stderr) 메시지

tracks.cpp: In function 'void IO(std::string)':
tracks.cpp:58:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 | freopen("input.txt","r",stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:59:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 | freopen("output.txt","w",stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:60:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 | freopen("error.txt","w",stderr);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:64:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 | freopen((s+".in").c_str(),"r",stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:65:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 | freopen((s+".out").c_str(),"w",stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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