oj.uz

Submission #1081301

# Submission time Handle Problem Language Result Execution time Memory
1081301 2024-08-29T21:28:16 Z MrPavlito Tracks in the Snow (BOI13_tracks) C++17
82.5 / 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 = 4000*4000+5;
const int mod7 = 1e9+7;
const long long inf = 1e9;
vector<vector<pii>> graf(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 222 ms 450292 KB Output is correct
2 Correct 171 ms 438680 KB Output is correct
3 Correct 174 ms 438864 KB Output is correct
4 Correct 211 ms 446800 KB Output is correct
5 Correct 176 ms 439504 KB Output is correct
6 Correct 171 ms 438612 KB Output is correct
7 Correct 168 ms 438864 KB Output is correct
8 Correct 160 ms 438864 KB Output is correct
9 Correct 166 ms 438868 KB Output is correct
10 Correct 177 ms 439888 KB Output is correct
11 Correct 181 ms 440912 KB Output is correct
12 Correct 188 ms 442960 KB Output is correct
13 Correct 169 ms 439468 KB Output is correct
14 Correct 174 ms 439636 KB Output is correct
15 Correct 218 ms 447312 KB Output is correct
16 Correct 229 ms 450388 KB Output is correct
17 Correct 194 ms 443476 KB Output is correct
18 Correct 216 ms 446808 KB Output is correct

Subtask #2
52.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 439124 KB Output is correct
2 Correct 326 ms 468812 KB Output is correct
3 Correct 752 ms 607568 KB Output is correct
4 Correct 370 ms 462836 KB Output is correct
5 Correct 560 ms 588372 KB Output is correct
6 Runtime error 1204 ms 1048576 KB Execution killed with signal 9
7 Correct 173 ms 439148 KB Output is correct
8 Correct 169 ms 439120 KB Output is correct
9 Correct 194 ms 440144 KB Output is correct
10 Correct 168 ms 439120 KB Output is correct
11 Correct 167 ms 438868 KB Output is correct
12 Correct 175 ms 439132 KB Output is correct
13 Correct 323 ms 468820 KB Output is correct
14 Correct 254 ms 456312 KB Output is correct
15 Correct 205 ms 448592 KB Output is correct
16 Correct 252 ms 455252 KB Output is correct
17 Correct 569 ms 514128 KB Output is correct
18 Correct 288 ms 477356 KB Output is correct
19 Correct 355 ms 462932 KB Output is correct
20 Correct 308 ms 478288 KB Output is correct
21 Correct 521 ms 539364 KB Output is correct
22 Correct 571 ms 588628 KB Output is correct
23 Correct 1002 ms 587844 KB Output is correct
24 Correct 434 ms 541520 KB Output is correct
25 Correct 914 ms 597080 KB Output is correct
26 Execution timed out 2097 ms 1026132 KB Time limit exceeded
27 Runtime error 1117 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1129 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1221 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1178 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2105 ms 930184 KB Time limit exceeded
32 Runtime error 1134 ms 1048576 KB Execution killed with signal 9