oj.uz

Submission #1081288

# Submission time Handle Problem Language Result Execution time Memory
1081288 2024-08-29T21:04:24 Z MrPavlito Tracks in the Snow (BOI13_tracks) C++17
67.1875 / 100
 2000 ms 1048576 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 = 5e6;
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 130 ms 176872 KB Output is correct
2 Correct 65 ms 157524 KB Output is correct
3 Correct 68 ms 157692 KB Output is correct
4 Correct 105 ms 170836 KB Output is correct
5 Correct 68 ms 158800 KB Output is correct
6 Correct 64 ms 157608 KB Output is correct
7 Correct 82 ms 157516 KB Output is correct
8 Correct 69 ms 158020 KB Output is correct
9 Correct 66 ms 157520 KB Output is correct
10 Correct 72 ms 159576 KB Output is correct
11 Correct 74 ms 161104 KB Output is correct
12 Correct 90 ms 164436 KB Output is correct
13 Correct 75 ms 158896 KB Output is correct
14 Correct 73 ms 158980 KB Output is correct
15 Correct 116 ms 172112 KB Output is correct
16 Correct 126 ms 176720 KB Output is correct
17 Correct 96 ms 165244 KB Output is correct
18 Correct 102 ms 170920 KB Output is correct

Subtask #2
37.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 158292 KB Output is correct
2 Correct 256 ms 207184 KB Output is correct
3 Runtime error 331 ms 488272 KB Execution killed with signal 11
4 Correct 284 ms 197072 KB Output is correct
5 Runtime error 403 ms 572244 KB Execution killed with signal 11
6 Execution timed out 3083 ms 1048576 KB Time limit exceeded
7 Correct 69 ms 158300 KB Output is correct
8 Correct 71 ms 158288 KB Output is correct
9 Correct 74 ms 159824 KB Output is correct
10 Correct 72 ms 158040 KB Output is correct
11 Correct 79 ms 157900 KB Output is correct
12 Correct 71 ms 158048 KB Output is correct
13 Correct 237 ms 207200 KB Output is correct
14 Correct 165 ms 186464 KB Output is correct
15 Correct 113 ms 172896 KB Output is correct
16 Correct 153 ms 184912 KB Output is correct
17 Correct 507 ms 282308 KB Output is correct
18 Correct 250 ms 217172 KB Output is correct
19 Correct 283 ms 196940 KB Output is correct
20 Correct 227 ms 222548 KB Output is correct
21 Runtime error 342 ms 496240 KB Execution killed with signal 11
22 Runtime error 404 ms 572496 KB Execution killed with signal 11
23 Runtime error 462 ms 633172 KB Execution killed with signal 11
24 Runtime error 323 ms 491248 KB Execution killed with signal 11
25 Runtime error 322 ms 469892 KB Execution killed with signal 11
26 Execution timed out 3100 ms 1048576 KB Time limit exceeded
27 Execution timed out 3201 ms 1048576 KB Time limit exceeded
28 Execution timed out 3207 ms 1048576 KB Time limit exceeded
29 Execution timed out 3252 ms 1048576 KB Time limit exceeded
30 Execution timed out 3206 ms 1048576 KB Time limit exceeded
31 Execution timed out 3201 ms 1048576 KB Time limit exceeded
32 Runtime error 819 ms 983376 KB Execution killed with signal 11