oj.uz

Submission #1081291

# Submission time Handle Problem Language Result Execution time Memory
1081291 2024-08-29T21:08:14 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);
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 264 ms 452476 KB Output is correct
2 Correct 199 ms 440776 KB Output is correct
3 Correct 194 ms 440656 KB Output is correct
4 Correct 224 ms 448872 KB Output is correct
5 Correct 198 ms 441592 KB Output is correct
6 Correct 180 ms 440720 KB Output is correct
7 Correct 187 ms 440660 KB Output is correct
8 Correct 198 ms 440912 KB Output is correct
9 Correct 197 ms 440660 KB Output is correct
10 Correct 192 ms 441804 KB Output is correct
11 Correct 203 ms 442960 KB Output is correct
12 Correct 215 ms 444756 KB Output is correct
13 Correct 206 ms 441632 KB Output is correct
14 Correct 199 ms 441648 KB Output is correct
15 Correct 240 ms 449620 KB Output is correct
16 Correct 256 ms 452548 KB Output is correct
17 Correct 226 ms 445780 KB Output is correct
18 Correct 367 ms 448856 KB Output is correct

Subtask #2
52.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 441168 KB Output is correct
2 Correct 372 ms 471780 KB Output is correct
3 Correct 777 ms 617504 KB Output is correct
4 Correct 410 ms 467024 KB Output is correct
5 Correct 611 ms 595280 KB Output is correct
6 Runtime error 1147 ms 1048576 KB Execution killed with signal 9
7 Correct 196 ms 441172 KB Output is correct
8 Correct 193 ms 441168 KB Output is correct
9 Correct 198 ms 442192 KB Output is correct
10 Correct 193 ms 440904 KB Output is correct
11 Correct 186 ms 440916 KB Output is correct
12 Correct 199 ms 441016 KB Output is correct
13 Correct 366 ms 471696 KB Output is correct
14 Correct 262 ms 459088 KB Output is correct
15 Correct 206 ms 451360 KB Output is correct
16 Correct 279 ms 457736 KB Output is correct
17 Correct 605 ms 518224 KB Output is correct
18 Correct 339 ms 481360 KB Output is correct
19 Correct 402 ms 465108 KB Output is correct
20 Correct 332 ms 480332 KB Output is correct
21 Correct 549 ms 541264 KB Output is correct
22 Correct 605 ms 590496 KB Output is correct
23 Correct 1022 ms 593896 KB Output is correct
24 Correct 553 ms 548436 KB Output is correct
25 Correct 951 ms 607484 KB Output is correct
26 Execution timed out 2066 ms 1040240 KB Time limit exceeded
27 Runtime error 1160 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1194 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1250 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1137 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2059 ms 941108 KB Time limit exceeded
32 Runtime error 1174 ms 1048576 KB Execution killed with signal 9