Submission #111752

#TimeUsernameProblemLanguageResultExecution timeMemory
111752rajarshi_basuTracks in the Snow (BOI13_tracks)C++14
0 / 100
731 ms454520 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[4000][4000]; 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; FOR(i,n){ FOR(j,m)cin >> grid[i][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; //getEdges(e.ss/m,e.ss%m,v); int i = e.ss/m; int j = e.ss%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]),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); } 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}); } //pq.push({dist[e.ss]+f.ss,f.ff}); } } */ //return 0; int mx = 0; FOR(i,n){ FOR(j,m){ if(grid[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...