Submission #134506

#	Time	Username	Problem	Language	Result	Execution time	Memory
134506		degelo	Tracks in the Snow (BOI13_tracks)	C++17	80.31 / 100	2128 ms	782984 KiB

tracks

#include<bits/stdc++.h>
#define maxn 4002
using namespace std;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int tab[maxn][maxn],rep[maxn][maxn],prof[maxn][maxn],marc[maxn][maxn];
int resp,n,m;
deque<pair<int ,int> > nv;
int find(int x,int y){
	//cout<<'1';
	int r=rep[x][y];
	if(r==m*x+y) return r;
	int ry=r%m;
	int rx=r/m;
	return rep[x][y]=find(rx,ry);
}
void une(int x1,int y1,int x2,int y2){
	//cout<<'2';
	int r1=find(x1,y1);
	x1=r1/m;y1=r1%m;
	int r2=find(x2,y2);
	x2=r2/m;y2=r2%m;
	if(r1==r2) return;
	if(prof[x1][y1]<prof[x2][y2]){
		rep[x1][y1]=r2;
		return; 
	}
	rep[x2][y2]=r1;
	if(prof[x1][y1]==prof[x2][y2]) prof[x1][y1]++;
}
void comp(int x,int y,int t){
	//cout<<x<<ends<<y<<endl;
	for(int i=0;i<4;i++){
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx==n||nx==-1||ny==m||ny==-1) continue;
		if(tab[nx][ny]==(3-t)&&find(nx,ny)!=find(0,0)){
			nv.push_back(make_pair(nx,ny));
		}
		if(tab[nx][ny]==t&&find(nx,ny)!=find(x,y)){
			une(nx,ny,x,y);
			comp(nx,ny,t);
		}
	}
}
void perc(int t){
	//cout<<nv.size()<<endl;
	resp++;
	int s=nv.size();
	for(int i=0;i<s;i++){
		int a=(nv.front()).first,b=(nv.front()).second;
		nv.pop_front();
		//cout<<a<<ends<<b<<endl;
		if(marc[a][b]==1) continue;
		marc[a][b]=1;
		comp(a,b,t);
		une(a,b,0,0);
	}
	if(nv.size()==0) return;
	perc(3-t);
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			char c;
			scanf(" %c",&c);
			if(c=='F') tab[i][j]=1;
			else if(c=='R') tab[i][j]=2;
			else tab[i][j]=0;
		}
	}
	/*for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cout<<tab[i][j]<<ends;
		}
		cout<<endl;
	}*/
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			rep[i][j]=m*i+j;
			prof[i][j]=1;
		}
	}
	nv.push_back(make_pair(0,0));
	perc(tab[0][0]);
	cout<<resp;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
tracks.cpp:66:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c",&c);
    ~~~~~^~~~~~~~~~

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