oj.uz

Submission #756572

# Submission time Handle Problem Language Result Execution time Memory
756572 2023-06-11T23:12:23 Z yandabao Tracks in the Snow (BOI13_tracks) C++14
31.7708 / 100
 1350 ms 1019420 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 || dist[adjList[a][i]] > b + 1){
            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;
    

    // 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
3.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 4144 KB Output isn't correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 300 KB Output isn't correct
4 Incorrect 10 ms 2516 KB Output isn't correct
5 Incorrect 5 ms 1364 KB Output isn't correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Incorrect 1 ms 304 KB Output isn't correct
9 Incorrect 1 ms 308 KB Output isn't correct
10 Incorrect 4 ms 1236 KB Output isn't correct
11 Incorrect 3 ms 924 KB Output isn't correct
12 Incorrect 8 ms 1724 KB Output isn't correct
13 Incorrect 5 ms 1364 KB Output isn't correct
14 Incorrect 6 ms 1364 KB Output isn't correct
15 Incorrect 22 ms 4244 KB Output isn't correct
16 Incorrect 24 ms 4140 KB Output isn't correct
17 Incorrect 18 ms 4280 KB Output isn't correct
18 Incorrect 10 ms 2516 KB Output isn't correct

Subtask #2
28.4375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1492 KB Output is correct
2 Incorrect 95 ms 21732 KB Output isn't correct
3 Incorrect 725 ms 204052 KB Output isn't correct
4 Incorrect 163 ms 38472 KB Output isn't correct
5 Correct 1050 ms 555256 KB Output is correct
6 Incorrect 1120 ms 172148 KB Output isn't correct
7 Correct 4 ms 1492 KB Output is correct
8 Correct 5 ms 1504 KB Output is correct
9 Incorrect 4 ms 1364 KB Output isn't correct
10 Correct 2 ms 960 KB Output is correct
11 Incorrect 3 ms 1264 KB Output isn't correct
12 Correct 3 ms 1620 KB Output is correct
13 Incorrect 97 ms 21740 KB Output isn't correct
14 Incorrect 53 ms 12976 KB Output isn't correct
15 Correct 58 ms 21696 KB Output is correct
16 Incorrect 45 ms 9852 KB Output isn't correct
17 Incorrect 230 ms 55292 KB Output isn't correct
18 Correct 236 ms 82944 KB Output is correct
19 Incorrect 161 ms 38484 KB Output isn't correct
20 Incorrect 172 ms 45268 KB Output isn't correct
21 Incorrect 426 ms 120196 KB Output isn't correct
22 Correct 1012 ms 555224 KB Output is correct
23 Incorrect 450 ms 105252 KB Output isn't correct
24 Correct 534 ms 215536 KB Output is correct
25 Correct 1004 ms 338176 KB Output is correct
26 Correct 1350 ms 1019420 KB Output is correct
27 Correct 1099 ms 607392 KB Output is correct
28 Incorrect 1109 ms 171432 KB Output isn't correct
29 Incorrect 1002 ms 178004 KB Output isn't correct
30 Incorrect 1050 ms 285628 KB Output isn't correct
31 Incorrect 931 ms 149816 KB Output isn't correct
32 Incorrect 1087 ms 556360 KB Output isn't correct