oj.uz

답안 #1109850

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1109850 2024-11-07T20:03:21 Z raspy Tracks in the Snow (BOI13_tracks) C++17
0 / 100
 799 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) continue;
		dfs(ni, nj, nc, n, m);
	}
}

int dfs1(int u, int p = -1)
{
	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++)
			dfs(i, j, nc++, n, m);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			for (ii d : pr)
			{
				int ni = i+d.f, nj = j+d.s;
				if (ni < 0 || nj < 0 || nj >= m || ni >= n) continue;
				if (pov.find({comp[ni][nj], comp[i][j]}) != pov.end()) continue;
				pov.insert({comp[ni][nj], comp[i][j]});
				pov.insert({comp[i][j], comp[ni][nj]});
				graf[comp[nj][ni]].pb(comp[i][j]);
				graf[comp[i][j]].pb(comp[nj][ni]);
			}
		}
	cout << dfs1(comp[0][0]) << "\n";
	return 0;
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 135 ms 494920 KB Output isn't correct
2 Incorrect 140 ms 470344 KB Output isn't correct
3 Incorrect 138 ms 470600 KB Output isn't correct
4 Incorrect 145 ms 487320 KB Output isn't correct
5 Incorrect 159 ms 479464 KB Output isn't correct
6 Incorrect 150 ms 470344 KB Output isn't correct
7 Incorrect 124 ms 470600 KB Output isn't correct
8 Incorrect 152 ms 470828 KB Output isn't correct
9 Incorrect 161 ms 471628 KB Output isn't correct
10 Incorrect 156 ms 477512 KB Output isn't correct
11 Incorrect 164 ms 474952 KB Output isn't correct
12 Incorrect 167 ms 479816 KB Output isn't correct
13 Incorrect 174 ms 479604 KB Output isn't correct
14 Incorrect 159 ms 479580 KB Output isn't correct
15 Incorrect 191 ms 495588 KB Output isn't correct
16 Incorrect 179 ms 495012 KB Output isn't correct
17 Incorrect 173 ms 494412 KB Output isn't correct
18 Incorrect 166 ms 487232 KB Output isn't correct

Subtask #2
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 178 ms 504904 KB Output isn't correct
2 Incorrect 322 ms 613192 KB Output isn't correct
3 Runtime error 799 ms 1048576 KB Execution killed with signal 9
4 Incorrect 577 ms 810828 KB Output isn't correct
5 Runtime error 680 ms 1048576 KB Execution killed with signal 9
6 Runtime error 771 ms 1048576 KB Execution killed with signal 9
7 Incorrect 170 ms 505920 KB Output isn't correct
8 Incorrect 181 ms 505004 KB Output isn't correct
9 Incorrect 149 ms 475208 KB Output isn't correct
10 Incorrect 152 ms 472648 KB Output isn't correct
11 Incorrect 176 ms 505712 KB Output isn't correct
12 Incorrect 149 ms 473160 KB Output isn't correct
13 Incorrect 335 ms 613308 KB Output isn't correct
14 Incorrect 264 ms 554280 KB Output isn't correct
15 Incorrect 272 ms 564832 KB Output isn't correct
16 Incorrect 237 ms 527944 KB Output isn't correct
17 Incorrect 677 ms 831308 KB Output isn't correct
18 Incorrect 640 ms 834376 KB Output isn't correct
19 Incorrect 649 ms 810572 KB Output isn't correct
20 Incorrect 558 ms 778296 KB Output isn't correct
21 Runtime error 744 ms 1048576 KB Execution killed with signal 9
22 Runtime error 722 ms 1048576 KB Execution killed with signal 9
23 Runtime error 724 ms 1048576 KB Execution killed with signal 9
24 Runtime error 702 ms 1048576 KB Execution killed with signal 9
25 Runtime error 798 ms 1048576 KB Execution killed with signal 9
26 Runtime error 714 ms 1048576 KB Execution killed with signal 9
27 Runtime error 719 ms 1048576 KB Execution killed with signal 9
28 Runtime error 739 ms 1048576 KB Execution killed with signal 9
29 Runtime error 793 ms 1048576 KB Execution killed with signal 9
30 Runtime error 787 ms 1048576 KB Execution killed with signal 9
31 Runtime error 773 ms 1048576 KB Execution killed with signal 9
32 Runtime error 758 ms 1048576 KB Execution killed with signal 9