oj.uz

답안 #771216

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
771216 2023-07-02T16:04:11 Z synthesis Tracks in the Snow (BOI13_tracks) C++17
19.7917 / 100
 2000 ms 438052 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define pii pair<int, int>
#define pb push_back
#define vi vector<int>
#define all(x) x.begin(), x.end()

using namespace std;
using namespace __gnu_pbds;
using ll = long long int;
using ull = unsigned long long int;

constexpr ll mod = 1e9 + 7;
constexpr ll INF = LONG_LONG_MAX;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
string moves = "URDL";

int main()
{
    //tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> q;
    /*freopen("problemname.in", "r", stdin);
    freopen("problemname.out", "w", stdout);*/
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    char a[n][m];
    for(int i = 0;i<n;++i) {
        for(int j = 0;j<m;++j) {
            cin >> a[i][j];
        }
    }
    bool vis[n][m];
    int cc[n][m], c = 0;
    memset(cc, 0, sizeof cc);
    memset(vis, false, sizeof vis);
    for(int i = 0;i<n;++i) {
        for(int j = 0;j<m;++j) {
            if (!vis[i][j]) {
                queue<pii> q;
                q.push({i, j});
                ++c;
                vis[i][j] = true;
                cc[i][j] = c;
                while(!q.empty()) {
                    pii node = q.front();
                    q.pop(); 
                    for(int k = 0;k<4;++k) {
                        int nx = node.fi + dx[k], ny = node.se + dy[k];
                        if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                            if (a[nx][ny] == a[i][j] && !vis[nx][ny]) {
                                q.push({nx, ny});
                                vis[nx][ny] = true;
                                cc[nx][ny] = c;
                            }
                        }
                    }
                }
            }
        }
    }
    memset(vis, false, sizeof vis);
    set<int> adj[c + 1];
    int d[c + 1];
    memset(d, 0, sizeof d);
    for(int i = 0;i<n;++i) {
        for(int j = 0;j<m;++j) {
            if (!vis[i][j]) {
                queue<pii> q;
                q.push({i, j});
                vis[i][j] = true;
                while(!q.empty()) {
                    pii node = q.front();
                    q.pop(); 
                    for(int k = 0;k<4;++k) {
                        int nx = node.fi + dx[k], ny = node.se + dy[k];
                        if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                            if (a[nx][ny] == a[i][j] && !vis[nx][ny]) {
                                q.push({nx, ny});
                                vis[nx][ny] = true;
                            }
                            if (cc[nx][ny] != cc[i][j] && cc[nx][ny] != 0) {
                                adj[cc[i][j]].insert(cc[nx][ny]);
                            }
                        }
                    }
                }
            }
        }
    }
    queue<int> q;
    q.push(cc[0][0]);
    bool ok[c + 1];
    memset(ok, false, sizeof ok);
    ok[cc[0][0]] = true;
    d[cc[0][0]] = 0;
    int ans = 0;
    while(!q.empty()) {
        int node = q.front();
        q.pop();
        for(const int& v:adj[node]) {
            if (!ok[v]) {
                q.push(v);
                ok[v] = true;
                d[v] = d[node] + 1;
                ans = max(ans, d[v]);
            }
        }
    }
    cout << ans + 1 << endl;
    return 0;
}

Subtask #1
6.66666666667 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 45 ms 9792 KB Output isn't correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Correct 13 ms 1812 KB Output is correct
5 Incorrect 13 ms 3444 KB Output isn't correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Correct 2 ms 340 KB Output is correct
9 Incorrect 1 ms 588 KB Output isn't correct
10 Incorrect 10 ms 2900 KB Output isn't correct
11 Correct 4 ms 724 KB Output is correct
12 Incorrect 17 ms 3948 KB Output isn't correct
13 Incorrect 13 ms 3540 KB Output isn't correct
14 Incorrect 12 ms 3492 KB Output isn't correct
15 Incorrect 46 ms 10700 KB Output isn't correct
16 Incorrect 44 ms 9820 KB Output isn't correct
17 Incorrect 44 ms 14156 KB Output isn't correct
18 Correct 13 ms 1764 KB Output is correct

Subtask #2
13.125 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 2260 KB Output isn't correct
2 Incorrect 257 ms 64232 KB Output isn't correct
3 Execution timed out 2059 ms 215192 KB Time limit exceeded
4 Incorrect 438 ms 110448 KB Output isn't correct
5 Execution timed out 2041 ms 420328 KB Time limit exceeded
6 Correct 1877 ms 181152 KB Output is correct
7 Incorrect 6 ms 1996 KB Output isn't correct
8 Incorrect 7 ms 2336 KB Output isn't correct
9 Incorrect 8 ms 2352 KB Output isn't correct
10 Incorrect 3 ms 1148 KB Output isn't correct
11 Incorrect 5 ms 1108 KB Output isn't correct
12 Incorrect 7 ms 4052 KB Output isn't correct
13 Incorrect 260 ms 64304 KB Output isn't correct
14 Incorrect 151 ms 37588 KB Output isn't correct
15 Incorrect 216 ms 51524 KB Output isn't correct
16 Incorrect 111 ms 27840 KB Output isn't correct
17 Incorrect 753 ms 169128 KB Output isn't correct
18 Incorrect 1082 ms 213656 KB Output isn't correct
19 Incorrect 497 ms 110488 KB Output isn't correct
20 Incorrect 708 ms 105944 KB Output isn't correct
21 Execution timed out 2102 ms 275288 KB Time limit exceeded
22 Execution timed out 2080 ms 438052 KB Time limit exceeded
23 Incorrect 1635 ms 319488 KB Output isn't correct
24 Execution timed out 2067 ms 213764 KB Time limit exceeded
25 Execution timed out 2024 ms 269732 KB Time limit exceeded
26 Correct 1343 ms 77880 KB Output is correct
27 Correct 1662 ms 102268 KB Output is correct
28 Correct 1839 ms 181752 KB Output is correct
29 Correct 1722 ms 148152 KB Output is correct
30 Correct 1603 ms 132160 KB Output is correct
31 Incorrect 1919 ms 359408 KB Output isn't correct
32 Incorrect 1473 ms 136212 KB Output isn't correct