oj.uz

답안 #1109849

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1109849 2024-11-07T20:00:33 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[ni][nj], comp[i][j]});
				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 130 ms 494800 KB Output isn't correct
2 Incorrect 113 ms 470100 KB Output isn't correct
3 Incorrect 117 ms 470600 KB Output isn't correct
4 Incorrect 143 ms 487408 KB Output isn't correct
5 Incorrect 153 ms 479624 KB Output isn't correct
6 Incorrect 133 ms 470088 KB Output isn't correct
7 Incorrect 138 ms 470724 KB Output isn't correct
8 Incorrect 144 ms 470856 KB Output isn't correct
9 Incorrect 145 ms 471624 KB Output isn't correct
10 Incorrect 151 ms 477512 KB Output isn't correct
11 Incorrect 164 ms 475000 KB Output isn't correct
12 Incorrect 154 ms 479816 KB Output isn't correct
13 Incorrect 156 ms 479560 KB Output isn't correct
14 Incorrect 151 ms 479568 KB Output isn't correct
15 Incorrect 203 ms 495688 KB Output isn't correct
16 Incorrect 173 ms 494664 KB Output isn't correct
17 Incorrect 176 ms 494152 KB Output isn't correct
18 Incorrect 181 ms 487240 KB Output isn't correct

Subtask #2
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 186 ms 504904 KB Output isn't correct
2 Incorrect 333 ms 613192 KB Output isn't correct
3 Runtime error 768 ms 1048576 KB Execution killed with signal 9
4 Incorrect 580 ms 810500 KB Output isn't correct
5 Runtime error 678 ms 1048576 KB Execution killed with signal 9
6 Runtime error 786 ms 1048576 KB Execution killed with signal 9
7 Incorrect 168 ms 505944 KB Output isn't correct
8 Incorrect 182 ms 504904 KB Output isn't correct
9 Incorrect 154 ms 475208 KB Output isn't correct
10 Incorrect 173 ms 472648 KB Output isn't correct
11 Incorrect 195 ms 505648 KB Output isn't correct
12 Incorrect 171 ms 473160 KB Output isn't correct
13 Incorrect 363 ms 613192 KB Output isn't correct
14 Incorrect 292 ms 554156 KB Output isn't correct
15 Incorrect 292 ms 564896 KB Output isn't correct
16 Incorrect 269 ms 528092 KB Output isn't correct
17 Incorrect 628 ms 830908 KB Output isn't correct
18 Incorrect 652 ms 834348 KB Output isn't correct
19 Incorrect 616 ms 810824 KB Output isn't correct
20 Incorrect 590 ms 777800 KB Output isn't correct
21 Runtime error 742 ms 1048576 KB Execution killed with signal 9
22 Runtime error 687 ms 1048576 KB Execution killed with signal 9
23 Runtime error 700 ms 1048576 KB Execution killed with signal 9
24 Runtime error 711 ms 1048576 KB Execution killed with signal 9
25 Runtime error 799 ms 1048576 KB Execution killed with signal 9
26 Runtime error 756 ms 1048576 KB Execution killed with signal 9
27 Runtime error 755 ms 1048576 KB Execution killed with signal 9
28 Runtime error 765 ms 1048576 KB Execution killed with signal 9
29 Runtime error 793 ms 1048576 KB Execution killed with signal 9
30 Runtime error 750 ms 1048576 KB Execution killed with signal 9
31 Runtime error 790 ms 1048576 KB Execution killed with signal 9
32 Runtime error 763 ms 1048576 KB Execution killed with signal 9