oj.uz

Submission #1081289

# Submission time Handle Problem Language Result Execution time Memory
1081289 2024-08-29T21:05:17 Z MrPavlito Tracks in the Snow (BOI13_tracks) C++17
56.25 / 100
 463 ms 462928 KB 
#include <bits/stdc++.h>
//#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>

using namespace std;

const int MAXN = 3e6;
const int mod7 = 1e9+7;
const long long inf = 1e9;
vector<vector<pii>> graf(MAXN);
vector<bool> visited(MAXN);
char val[MAXN];
vector<int> dist(MAXN,inf);

set<pii> pq;

/*
void dfs(int nod)
{
    visited[nod] = 1;
    pq.insert(mp(0, nod));
    dist[nod] = 0;
    for(auto x: graf[nod])if(val[nod] == val[x.fi] && !visited[x.fi])dfs(x.fi);
}
*/

void dikstra()
{
    dist[0] = 0;
    pq.insert({0,0});
    while(!pq.empty())
    {
        auto it = pq.begin();
        int u = it -> sc;
        pq.erase(it);
        for(auto x: graf[u])
        {
            int nod = x.fi;
            int w = x.sc;
            if(dist[nod] > dist[u]+w)
            {
                pq.erase({dist[nod], nod});
                dist[nod] = dist[u]+w;
                pq.insert({dist[nod], nod});
            }
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--)
    {
        int n,m;
        cin >> n >> m;
        for(int i=0; i<n; i++)
        {
            string s;cin >> s;
            for(int j=0; j<m; j++)
            {

                val[i*m+j] = s[j];
                if(s[j] == '.')continue;
                if(i>0 && val[(i-1)*m+j] != '.')
                {
                    graf[i*m+j].pb(mp((i-1)*m+j,val[i*m+j] != val[(i-1)*m+j]));
                    graf[(i-1)*m+j].pb(mp(i*m+j,val[i*m+j] != val[(i-1)*m+j]));
                }
                if(j>0 && val[i*m+j-1] != '.')
                {
                    graf[i*m+j].pb(mp(i*m+j-1,val[i*m+j] != val[i*m+j-1]));
                    graf[i*m+j-1].pb(mp(i*m+j,val[i*m+j] != val[i*m+j-1]));
                }
            }
        }
        //dfs(0);
        dikstra();
        int mx = 0;
        for(auto x: dist)if(x!=inf)mx = max(mx,x);
        cout << mx+1 << endl;
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 94804 KB Output is correct
2 Correct 40 ms 83032 KB Output is correct
3 Correct 42 ms 83028 KB Output is correct
4 Correct 72 ms 91220 KB Output is correct
5 Correct 40 ms 83792 KB Output is correct
6 Correct 39 ms 83036 KB Output is correct
7 Correct 40 ms 82984 KB Output is correct
8 Correct 37 ms 83280 KB Output is correct
9 Correct 40 ms 83036 KB Output is correct
10 Correct 47 ms 84136 KB Output is correct
11 Correct 45 ms 85072 KB Output is correct
12 Correct 56 ms 87120 KB Output is correct
13 Correct 45 ms 83928 KB Output is correct
14 Correct 45 ms 83792 KB Output is correct
15 Correct 83 ms 91872 KB Output is correct
16 Correct 90 ms 94852 KB Output is correct
17 Correct 71 ms 87888 KB Output is correct
18 Correct 70 ms 91216 KB Output is correct

Subtask #2
26.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 83540 KB Output is correct
2 Correct 223 ms 114004 KB Output is correct
3 Runtime error 186 ms 230992 KB Execution killed with signal 11
4 Runtime error 161 ms 211796 KB Execution killed with signal 11
5 Runtime error 225 ms 270932 KB Execution killed with signal 11
6 Runtime error 442 ms 462672 KB Execution killed with signal 11
7 Correct 42 ms 83536 KB Output is correct
8 Correct 43 ms 83540 KB Output is correct
9 Correct 43 ms 84412 KB Output is correct
10 Correct 41 ms 83352 KB Output is correct
11 Correct 43 ms 83280 KB Output is correct
12 Correct 42 ms 83288 KB Output is correct
13 Correct 207 ms 113984 KB Output is correct
14 Correct 130 ms 101204 KB Output is correct
15 Correct 71 ms 93616 KB Output is correct
16 Correct 119 ms 99924 KB Output is correct
17 Runtime error 268 ms 281468 KB Execution killed with signal 6
18 Runtime error 171 ms 228228 KB Execution killed with signal 11
19 Runtime error 167 ms 212304 KB Execution killed with signal 11
20 Runtime error 190 ms 239444 KB Execution killed with signal 6
21 Runtime error 180 ms 234268 KB Execution killed with signal 11
22 Runtime error 219 ms 271096 KB Execution killed with signal 11
23 Runtime error 243 ms 286032 KB Execution killed with signal 11
24 Runtime error 178 ms 238168 KB Execution killed with signal 11
25 Runtime error 174 ms 229460 KB Execution killed with signal 11
26 Runtime error 431 ms 462676 KB Execution killed with signal 11
27 Runtime error 463 ms 462676 KB Execution killed with signal 11
28 Runtime error 443 ms 462908 KB Execution killed with signal 11
29 Runtime error 431 ms 462928 KB Execution killed with signal 11
30 Runtime error 459 ms 462700 KB Execution killed with signal 11
31 Runtime error 458 ms 461512 KB Execution killed with signal 11
32 Runtime error 377 ms 407468 KB Execution killed with signal 11