Submission #111764

#TimeUsernameProblemLanguageResultExecution timeMemory
111764rajarshi_basuTracks in the Snow (BOI13_tracks)C++14
82.50 / 100
2132 ms495576 KiB
#include <iostream> #include <vector> #include <set> #include <iomanip> #include <algorithm> #include <functional> #include <stdio.h> #include <cmath> #include <queue> #include <string> #include <map> #include <complex> #include <stack> #include <set> #define FOR(i,n) for(int i=0;i<n;i++) #define FORE(i,a,b) for(int i=a;i<=b;i++) #define ll long long int #define vi vector<int> #define ii pair<ll,ll> #define pb push_back #define mp make_pair #define ff first #define ss second #define pll pair<ll,ll> #define cd complex<double> const int INF = 1e9; using namespace std; const int MAXN = 4000*4000+500; vector<ii> g[MAXN]; char grid[MAXN]; int n,m; inline int cost(char c1,char c2){ return (c1 == '.' or c2 == '.')?-1:(1-(c1==c2)); } int dist[MAXN]; bool vis[MAXN]; inline int change(int i,int j){ return i*m+j; } inline void insertEdge(int a,int b,int c,vector<ii>& v){ v.pb({b,c}); } /* inline void getEdges(int i,int j,vector<ii>& v){ if(i > 0 and cost(grid[i][j],grid[i-1][j])>=0){ insertEdge(change(i,j),change(i-1,j),cost(grid[i][j],grid[i-1][j]),v); } if(j > 0 and cost(grid[i][j],grid[i][j-1])>=0){ insertEdge(change(i,j),change(i,j-1),cost(grid[i][j],grid[i][j-1]),v); } if(i < n-1 and cost(grid[i][j],grid[i+1][j])>=0){ insertEdge(change(i,j),change(i+1,j),cost(grid[i][j],grid[i+1][j]),v); } if(j < m-1 and cost(grid[i][j],grid[i][j+1])>=0){ insertEdge(change(i,j),change(i,j+1),cost(grid[i][j],grid[i][j+1]),v); } } */ int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; string s; FOR(i,n){ cin >> s; FOR(j,m)grid[change(i,j)] = s[j]; } /* FOR(i,n){ FOR(j,m){ if(i > 0 and cost(grid[i][j],grid[i-1][j])>=0){ insertEdge(change(i,j),change(i-1,j),cost(grid[i][j],grid[i-1][j])); } if(j > 0 and cost(grid[i][j],grid[i][j-1])>=0){ insertEdge(change(i,j),change(i,j-1),cost(grid[i][j],grid[i][j-1])); } if(i < n-1 and cost(grid[i][j],grid[i+1][j])>=0){ insertEdge(change(i,j),change(i+1,j),cost(grid[i][j],grid[i+1][j])); } if(j < m-1 and cost(grid[i][j],grid[i][j+1])>=0){ insertEdge(change(i,j),change(i,j+1),cost(grid[i][j],grid[i][j+1])); } } }*/ FOR(i,MAXN)dist[i] = INF; queue<ii> q1; queue<ii> q2; q1.push({0,0}); while(1){ if(q1.empty() and q2.empty())break; if(q1.empty())swap(q1,q2); auto e = q1.front();q1.pop(); if(vis[e.ss])continue; vis[e.ss] = 1; dist[e.ss] = e.ff; vector<ii> v; int i = e.ss/m; int j = e.ss%m; if(i > 0 and cost(grid[change(i,j)],grid[change(i-1,j)])>=0){ v.pb({(i-1)*m+j,cost(grid[change(i,j)],grid[change(i-1,j)])}); } if(j > 0 and cost(grid[change(i,j)],grid[change(i,j-1)])>=0){ v.pb({(i)*m+j-1,cost(grid[change(i,j)],grid[change(i,j-1)])}); } if(i < n-1 and cost(grid[change(i,j)],grid[change(i+1,j)])>=0){ v.pb({(i+1)*m+j,cost(grid[change(i,j)],grid[change(i+1,j)])}); } if(j < m-1 and cost(grid[change(i,j)],grid[change(i,j+1)])>=0){ v.pb({(i)*m+j+1,cost(grid[change(i,j)],grid[change(i,j+1)])}); } for(auto f : v){ if(dist[f.ff] <= dist[e.ss]+f.ss)continue; if(f.ss == 0){ q1.push({e.ff,f.ff}); }else{ q2.push({e.ff+1,f.ff}); } } } //return 0; int mx = 0; FOR(i,n){ FOR(j,m){ if(grid[change(i,j)] != '.'){ mx = max(mx,dist[change(i,j)]); } // cout << setw(10) <<dist[change(i,j)] << " "; } //cout << endl; } cout << (mx + 1) << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...