oj.uz

답안 #134506

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
134506 2019-07-23T00:27:08 Z degelo Tracks in the Snow (BOI13_tracks) C++17
80.3125 / 100
 2000 ms 782984 KB 
#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

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.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 12252 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 4 ms 1144 KB Output is correct
4 Correct 51 ms 12536 KB Output is correct
5 Correct 16 ms 6264 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 3 ms 1144 KB Output is correct
8 Correct 4 ms 1400 KB Output is correct
9 Correct 4 ms 2040 KB Output is correct
10 Correct 15 ms 5240 KB Output is correct
11 Correct 15 ms 5112 KB Output is correct
12 Correct 35 ms 6520 KB Output is correct
13 Correct 16 ms 6256 KB Output is correct
14 Correct 16 ms 6264 KB Output is correct
15 Correct 74 ms 12152 KB Output is correct
16 Correct 92 ms 12256 KB Output is correct
17 Correct 51 ms 11768 KB Output is correct
18 Correct 52 ms 12536 KB Output is correct

Subtask #2
50.3125 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 57368 KB Output is correct
2 Correct 283 ms 41652 KB Output is correct
3 Correct 1749 ms 219836 KB Output is correct
4 Correct 439 ms 88372 KB Output is correct
5 Correct 1046 ms 171412 KB Output is correct
6 Execution timed out 2086 ms 311480 KB Time limit exceeded
7 Correct 55 ms 59868 KB Output is correct
8 Correct 54 ms 57308 KB Output is correct
9 Correct 12 ms 1784 KB Output is correct
10 Correct 5 ms 1188 KB Output is correct
11 Correct 51 ms 56864 KB Output is correct
12 Correct 7 ms 3064 KB Output is correct
13 Correct 280 ms 41848 KB Output is correct
14 Correct 175 ms 27384 KB Output is correct
15 Correct 136 ms 32248 KB Output is correct
16 Correct 135 ms 15956 KB Output is correct
17 Correct 692 ms 87340 KB Output is correct
18 Correct 537 ms 95380 KB Output is correct
19 Correct 435 ms 88560 KB Output is correct
20 Correct 411 ms 72696 KB Output is correct
21 Correct 1054 ms 168060 KB Output is correct
22 Correct 1060 ms 171484 KB Output is correct
23 Correct 1323 ms 141200 KB Output is correct
24 Correct 940 ms 165124 KB Output is correct
25 Execution timed out 2037 ms 251908 KB Time limit exceeded
26 Execution timed out 2119 ms 782984 KB Time limit exceeded
27 Execution timed out 2083 ms 540180 KB Time limit exceeded
28 Execution timed out 2087 ms 312068 KB Time limit exceeded
29 Execution timed out 2095 ms 320556 KB Time limit exceeded
30 Execution timed out 2095 ms 316328 KB Time limit exceeded
31 Execution timed out 2082 ms 183320 KB Time limit exceeded
32 Execution timed out 2128 ms 638248 KB Time limit exceeded