oj.uz

Submission #1081280

# Submission time Handle Problem Language Result Execution time Memory
1081280 2024-08-29T20:54:21 Z MrPavlito Tracks in the Snow (BOI13_tracks) C++17
56.25 / 100
 378 ms 451736 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 = 2e6;
const int mod7 = 1e9+7;
const long long inf = 1e18;
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 93 ms 82580 KB Output is correct
2 Correct 28 ms 63324 KB Output is correct
3 Correct 28 ms 63324 KB Output is correct
4 Correct 63 ms 76464 KB Output is correct
5 Correct 35 ms 64744 KB Output is correct
6 Correct 28 ms 63248 KB Output is correct
7 Correct 31 ms 63320 KB Output is correct
8 Correct 31 ms 63576 KB Output is correct
9 Correct 29 ms 63324 KB Output is correct
10 Correct 35 ms 65116 KB Output is correct
11 Correct 51 ms 66688 KB Output is correct
12 Correct 62 ms 69972 KB Output is correct
13 Correct 37 ms 64696 KB Output is correct
14 Correct 36 ms 64700 KB Output is correct
15 Correct 78 ms 77652 KB Output is correct
16 Correct 96 ms 82512 KB Output is correct
17 Correct 65 ms 71120 KB Output is correct
18 Correct 85 ms 76600 KB Output is correct

Subtask #2
26.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 64088 KB Output is correct
2 Correct 203 ms 112976 KB Output is correct
3 Runtime error 138 ms 194132 KB Execution killed with signal 11
4 Runtime error 127 ms 170004 KB Execution killed with signal 11
5 Runtime error 170 ms 229204 KB Execution killed with signal 11
6 Runtime error 378 ms 451736 KB Execution killed with signal 11
7 Correct 30 ms 63824 KB Output is correct
8 Correct 32 ms 64092 KB Output is correct
9 Correct 33 ms 65628 KB Output is correct
10 Correct 31 ms 63572 KB Output is correct
11 Correct 36 ms 63580 KB Output is correct
12 Correct 30 ms 63832 KB Output is correct
13 Correct 213 ms 112984 KB Output is correct
14 Correct 132 ms 92244 KB Output is correct
15 Correct 66 ms 78744 KB Output is correct
16 Correct 120 ms 90700 KB Output is correct
17 Runtime error 196 ms 250120 KB Execution killed with signal 11
18 Runtime error 130 ms 186828 KB Execution killed with signal 11
19 Runtime error 120 ms 169812 KB Execution killed with signal 11
20 Runtime error 144 ms 200784 KB Execution killed with signal 11
21 Runtime error 147 ms 196700 KB Execution killed with signal 11
22 Runtime error 183 ms 229204 KB Execution killed with signal 11
23 Runtime error 200 ms 255228 KB Execution killed with signal 11
24 Runtime error 146 ms 196700 KB Execution killed with signal 11
25 Runtime error 141 ms 188248 KB Execution killed with signal 11
26 Runtime error 378 ms 451528 KB Execution killed with signal 11
27 Runtime error 376 ms 451680 KB Execution killed with signal 11
28 Runtime error 363 ms 451680 KB Execution killed with signal 11
29 Runtime error 369 ms 451724 KB Execution killed with signal 11
30 Runtime error 377 ms 451668 KB Execution killed with signal 11
31 Runtime error 375 ms 450080 KB Execution killed with signal 11
32 Runtime error 331 ms 388176 KB Execution killed with signal 11