oj.uz

답안 #1109855

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1109855 2024-11-07T20:13:21 Z raspy Tracks in the Snow (BOI13_tracks) C++17
23.0208 / 100
 2000 ms 1048576 KB 
#include <bits/stdc++.h>

// #define int long long
#define vi vector<int>
#define ii pair<int, int>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define P 31
#define mod 1'000'000'007
#define inf 1'000'000'000'000
#define pb push_back
#define str string
#define sz(x) (x).size()
#define vvi vector<vi>
#define fun function
#define oopt cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
#define file freopen("problemname.in", "r", stdin); freopen("pr.out", "w", stdout);
#define dbg(v) cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;

using namespace std;
template <class T, int SZ> using arr = array<T, SZ>;

int a[4001][4001];
int comp[4001][4001];
vi graf[20000001];
set<ii> pov;
vector<ii> pr = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

void dfs(int i, int j, int nc, int n, int m)
{
	if (comp[i][j]) return;
	comp[i][j] = nc;
	for (ii d : pr)
	{
		int ni = i+d.f, nj = j+d.s;
		if (ni < 0 || nj < 0 || nj >= m || ni >= n || a[ni][nj] != a[i][j]) continue;
		dfs(ni, nj, nc, n, m);
	}
}

int dfs1(int u, int p = -1)
{
	// cout << u << " " << p << "\n";
	int rez = 0;
	for (int v : graf[u])
		if (v != p)
			rez = max(rez, dfs1(v, u));
	return rez+1;
}

signed main()
{
	oopt;
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			char c;
			cin >> c;
			if (c == 'F') a[i][j] = 1;
			else if (c == 'R') a[i][j] = 2;
		}
	int nc = 1;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (a[i][j])
				dfs(i, j, nc++, n, m);
	// for (int i = 0; i < n; i++)
	// 	for (int j = 0; j < m; j++)
	// 		cout << comp[i][j] << " \n"[j == m-1];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			if (a[i][j] == 0) continue;
			for (ii d : pr)
			{
				int ni = i+d.f, nj = j+d.s;
				if (ni < 0 || nj < 0 || nj >= m || ni >= n || comp[ni][nj] == comp[i][j] || !a[ni][nj])
					continue;
				if (pov.find({comp[ni][nj], comp[i][j]}) != pov.end()) continue;
				// cout << a[i][j] << " " << a[ni][nj] << " " << comp[i][j] << " " << comp[ni][nj] << "\n";
				pov.insert({comp[ni][nj], comp[i][j]});
				pov.insert({comp[i][j], comp[ni][nj]});
				graf[comp[ni][nj]].pb(comp[i][j]);
				graf[comp[i][j]].pb(comp[ni][nj]);
			}
		}
	cout << dfs1(comp[0][0]) << "\n";
	return 0;
}

Subtask #1
3.33333333333 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 671 ms 1048576 KB Execution killed with signal 9
2 Correct 111 ms 470184 KB Output is correct
3 Runtime error 640 ms 1048576 KB Execution killed with signal 9
4 Runtime error 694 ms 1048576 KB Execution killed with signal 9
5 Runtime error 654 ms 1048576 KB Execution killed with signal 9
6 Correct 108 ms 470296 KB Output is correct
7 Runtime error 641 ms 1048576 KB Execution killed with signal 9
8 Runtime error 635 ms 1048576 KB Execution killed with signal 9
9 Runtime error 629 ms 1048576 KB Execution killed with signal 9
10 Runtime error 630 ms 1048576 KB Execution killed with signal 9
11 Runtime error 1116 ms 1048576 KB Execution killed with signal 9
12 Runtime error 678 ms 1048576 KB Execution killed with signal 9
13 Runtime error 636 ms 1048576 KB Execution killed with signal 9
14 Runtime error 653 ms 1048576 KB Execution killed with signal 9
15 Runtime error 684 ms 1048576 KB Execution killed with signal 9
16 Runtime error 648 ms 1048576 KB Execution killed with signal 9
17 Runtime error 641 ms 1048576 KB Execution killed with signal 9
18 Runtime error 708 ms 1048576 KB Execution killed with signal 9

Subtask #2
19.6875 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 501900 KB Output is correct
2 Runtime error 798 ms 1048576 KB Execution killed with signal 9
3 Runtime error 1638 ms 1048576 KB Execution killed with signal 9
4 Runtime error 861 ms 1048576 KB Execution killed with signal 9
5 Execution timed out 2118 ms 988960 KB Time limit exceeded
6 Execution timed out 2093 ms 769724 KB Time limit exceeded
7 Correct 173 ms 503368 KB Output is correct
8 Correct 191 ms 501936 KB Output is correct
9 Runtime error 974 ms 1048576 KB Execution killed with signal 9
10 Correct 148 ms 470856 KB Output is correct
11 Execution timed out 2089 ms 532704 KB Time limit exceeded
12 Correct 134 ms 473160 KB Output is correct
13 Runtime error 824 ms 1048576 KB Execution killed with signal 9
14 Runtime error 1861 ms 1048576 KB Execution killed with signal 9
15 Correct 283 ms 511560 KB Output is correct
16 Runtime error 724 ms 1048576 KB Execution killed with signal 9
17 Runtime error 1039 ms 1048576 KB Execution killed with signal 9
18 Correct 825 ms 614632 KB Output is correct
19 Runtime error 841 ms 1048576 KB Execution killed with signal 9
20 Runtime error 933 ms 1048576 KB Execution killed with signal 9
21 Execution timed out 2084 ms 697236 KB Time limit exceeded
22 Execution timed out 2101 ms 986120 KB Time limit exceeded
23 Runtime error 1505 ms 1048576 KB Execution killed with signal 9
24 Correct 1308 ms 793464 KB Output is correct
25 Execution timed out 2088 ms 842892 KB Time limit exceeded
26 Runtime error 738 ms 1048576 KB Execution killed with signal 9
27 Correct 990 ms 833352 KB Output is correct
28 Execution timed out 2083 ms 895836 KB Time limit exceeded
29 Execution timed out 2050 ms 1048576 KB Time limit exceeded
30 Runtime error 1783 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2082 ms 711448 KB Time limit exceeded
32 Runtime error 1326 ms 1048576 KB Execution killed with signal 9