oj.uz

Submission #756568

# Submission time Handle Problem Language Result Execution time Memory
756568 2023-06-11T23:03:12 Z yandabao Tracks in the Snow (BOI13_tracks) C++14
0 / 100
 1439 ms 1031124 KB 
#include <iostream>
#include <vector>
#include <limits>
#include <map>
#include <algorithm>
#include <set>
#include <string>
#include <cmath>
#include <climits>
#include <string.h>
#include <fstream>
#include <stack>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vb = vector<bool>;
using vvi= vector<vector<int> >;
using vll = vector<long long>;
using vpi = vector<pair<int, int> >;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int, int>;
#define f first
#define s second
#define mp make_pair
//cin.tie(0)->sync_with_stdio(0);

int H, W;
vector<vector<char> > ogGrid;
vvi numGrid, adjList;
int highest;
vector<pair<int, int> > connections;
stack<pair<int, pair<int, int> > > toExplore;
vi dist;


void traverse(char a, int b, int x, int y){
    if(x >= H || x < 0 || y >= W || y < 0 || numGrid[x][y] != 0 || ogGrid[x][y] == '.'){
        return;
    }
    if(ogGrid[x][y] != a){
        toExplore.push(mp(b, mp(x, y)));
        return;
    }
    numGrid[x][y] = b;
    traverse(a, b, x + 1, y);
    traverse(a, b, x, y + 1);
    traverse(a, b, x - 1, y);
    traverse(a, b, x, y - 1);
}

void BFS(int a, int b){
    dist[a] = b;
    for (int i = 0; i < sz(adjList[a]); i++)
    {
        if(dist[adjList[a][i]] == 0){
            BFS(adjList[a][i], b + 1);
        }
    }
}

int main(){
    cin >> H >> W;
    ogGrid.rsz(H); numGrid.rsz(H);
    for (int i = 0; i < H; i++)
    {
        numGrid[i].rsz(W);
        string str; cin >> str;
        ogGrid[i].rsz(W);
        for (int j = 0; j < W; j++)
        {
            ogGrid[i][j] = str[j];
        }
    }
    highest = 1;
    traverse(ogGrid[0][0], highest, 0, 0);
    while(sz(toExplore) > 0){
        pair<int, pair<int, int> > curr = toExplore.top(); toExplore.pop();
        if(numGrid[curr.s.f][curr.s.s] == 0){
            highest++;
            connections.pb(mp(curr.f, highest));
            traverse(ogGrid[curr.s.f][curr.s.s], highest, curr.s.f, curr.s.s);
        }
    }

    // for (int i = 0; i < H; i++)
    // {
    //     for (int j = 0; j < W; j++)
    //     {
    //         cout << numGrid[i][j];
    //     }
    //     cout << endl;
        
    // }
    
    adjList.rsz(highest);
    for (int i = 0; i < sz(connections); i++)
    {
        adjList[connections[i].f - 1].pb(connections[i].s - 1);
        adjList[connections[i].s - 1].pb(connections[i].f - 1);
    }

    dist.rsz(highest);
    BFS(0, 1);

    int maxVal = -1;

    for (int i = 0; i < sz(dist); i++)
    {
        maxVal = max(maxVal, dist[i]);
    }
    cout << maxVal - 1;
    

    // for (int i = 0; i < sz(adjList); i++)
    // {
    //     cout << i << ": ";
    //     for (int j = 0; j < sz(adjList[i]); j++)
    //     {
    //         cout << adjList[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 4152 KB Output isn't correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Incorrect 11 ms 2484 KB Output isn't correct
5 Incorrect 5 ms 1364 KB Output isn't correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Incorrect 5 ms 1236 KB Output isn't correct
11 Incorrect 4 ms 980 KB Output isn't correct
12 Incorrect 9 ms 1744 KB Output isn't correct
13 Incorrect 5 ms 1364 KB Output isn't correct
14 Incorrect 5 ms 1364 KB Output isn't correct
15 Incorrect 20 ms 4300 KB Output isn't correct
16 Incorrect 23 ms 4156 KB Output isn't correct
17 Incorrect 17 ms 4328 KB Output isn't correct
18 Incorrect 10 ms 2516 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1492 KB Output isn't correct
2 Incorrect 105 ms 22764 KB Output isn't correct
3 Incorrect 734 ms 219000 KB Output isn't correct
4 Incorrect 170 ms 41732 KB Output isn't correct
5 Incorrect 1056 ms 563220 KB Output isn't correct
6 Incorrect 1063 ms 187208 KB Output isn't correct
7 Incorrect 3 ms 1492 KB Output isn't correct
8 Incorrect 5 ms 1492 KB Output isn't correct
9 Incorrect 5 ms 1364 KB Output isn't correct
10 Incorrect 2 ms 920 KB Output isn't correct
11 Incorrect 4 ms 1364 KB Output isn't correct
12 Incorrect 4 ms 1620 KB Output isn't correct
13 Incorrect 97 ms 23004 KB Output isn't correct
14 Incorrect 55 ms 13508 KB Output isn't correct
15 Incorrect 60 ms 22284 KB Output isn't correct
16 Incorrect 44 ms 10176 KB Output isn't correct
17 Incorrect 240 ms 58936 KB Output isn't correct
18 Incorrect 236 ms 86448 KB Output isn't correct
19 Incorrect 161 ms 41712 KB Output isn't correct
20 Incorrect 165 ms 48228 KB Output isn't correct
21 Incorrect 428 ms 128612 KB Output isn't correct
22 Incorrect 1020 ms 563268 KB Output isn't correct
23 Incorrect 446 ms 112620 KB Output isn't correct
24 Incorrect 531 ms 223828 KB Output isn't correct
25 Incorrect 1166 ms 353040 KB Output isn't correct
26 Incorrect 1439 ms 1031124 KB Output isn't correct
27 Incorrect 1144 ms 623120 KB Output isn't correct
28 Incorrect 1075 ms 187048 KB Output isn't correct
29 Incorrect 1030 ms 193604 KB Output isn't correct
30 Incorrect 1137 ms 300732 KB Output isn't correct
31 Incorrect 985 ms 159792 KB Output isn't correct
32 Incorrect 1293 ms 572056 KB Output isn't correct