oj.uz

Submission #1081290

# Submission time Handle Problem Language Result Execution time Memory
1081290 2024-08-29T21:07:13 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 = 2e7;
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 290 ms 562496 KB Output is correct
2 Correct 229 ms 550740 KB Output is correct
3 Correct 262 ms 550728 KB Output is correct
4 Correct 282 ms 558928 KB Output is correct
5 Correct 249 ms 551864 KB Output is correct
6 Correct 221 ms 550700 KB Output is correct
7 Correct 301 ms 550740 KB Output is correct
8 Correct 241 ms 550996 KB Output is correct
9 Correct 246 ms 550696 KB Output is correct
10 Correct 249 ms 551980 KB Output is correct
11 Correct 246 ms 553300 KB Output is correct
12 Correct 252 ms 554952 KB Output is correct
13 Correct 245 ms 551648 KB Output is correct
14 Correct 240 ms 551636 KB Output is correct
15 Correct 277 ms 559600 KB Output is correct
16 Correct 298 ms 562512 KB Output is correct
17 Correct 256 ms 555604 KB Output is correct
18 Correct 281 ms 559088 KB Output is correct

Subtask #2
52.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 551224 KB Output is correct
2 Correct 411 ms 582308 KB Output is correct
3 Correct 832 ms 734884 KB Output is correct
4 Correct 442 ms 578488 KB Output is correct
5 Correct 637 ms 709156 KB Output is correct
6 Runtime error 1070 ms 1048576 KB Execution killed with signal 9
7 Correct 239 ms 551252 KB Output is correct
8 Correct 235 ms 551144 KB Output is correct
9 Correct 258 ms 552272 KB Output is correct
10 Correct 236 ms 550988 KB Output is correct
11 Correct 234 ms 551012 KB Output is correct
12 Correct 239 ms 551036 KB Output is correct
13 Correct 393 ms 582224 KB Output is correct
14 Correct 333 ms 569176 KB Output is correct
15 Correct 275 ms 561744 KB Output is correct
16 Correct 334 ms 567888 KB Output is correct
17 Correct 657 ms 629844 KB Output is correct
18 Correct 401 ms 592900 KB Output is correct
19 Correct 450 ms 578472 KB Output is correct
20 Correct 383 ms 593520 KB Output is correct
21 Correct 624 ms 660820 KB Output is correct
22 Correct 698 ms 709472 KB Output is correct
23 Correct 1066 ms 707412 KB Output is correct
24 Correct 512 ms 662612 KB Output is correct
25 Correct 1046 ms 725160 KB Output is correct
26 Runtime error 1053 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1104 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1014 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1040 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1028 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2086 ms 1048576 KB Time limit exceeded
32 Runtime error 1095 ms 1048576 KB Execution killed with signal 9