oj.uz

Submission #1081300

# Submission time Handle Problem Language Result Execution time Memory
1081300 2024-08-29T21:21:57 Z MrPavlito Tracks in the Snow (BOI13_tracks) C++17
2.1875 / 100
 1232 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 dikstra()
{
    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]));
                }
            }
        }
        dikstra();
        int mx = 0;
        for(auto x: dist)if(x!=inf)mx = max(mx,x);
        cout << mx+1 << endl;
    }
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 450192 KB Output isn't correct
2 Incorrect 179 ms 438612 KB Output isn't correct
3 Incorrect 176 ms 438776 KB Output isn't correct
4 Incorrect 185 ms 446284 KB Output isn't correct
5 Incorrect 184 ms 439636 KB Output isn't correct
6 Incorrect 185 ms 438664 KB Output isn't correct
7 Incorrect 184 ms 438864 KB Output isn't correct
8 Incorrect 182 ms 438828 KB Output isn't correct
9 Incorrect 183 ms 438864 KB Output isn't correct
10 Incorrect 186 ms 440052 KB Output isn't correct
11 Incorrect 186 ms 440656 KB Output isn't correct
12 Incorrect 184 ms 442712 KB Output isn't correct
13 Incorrect 190 ms 439632 KB Output isn't correct
14 Incorrect 193 ms 439636 KB Output isn't correct
15 Incorrect 187 ms 447508 KB Output isn't correct
16 Incorrect 208 ms 450132 KB Output isn't correct
17 Incorrect 208 ms 443568 KB Output isn't correct
18 Incorrect 190 ms 446288 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 187 ms 439276 KB Output isn't correct
2 Incorrect 236 ms 470100 KB Output isn't correct
3 Incorrect 534 ms 620080 KB Output isn't correct
4 Incorrect 242 ms 466516 KB Output isn't correct
5 Incorrect 458 ms 595544 KB Output isn't correct
6 Runtime error 1138 ms 1048576 KB Execution killed with signal 9
7 Incorrect 174 ms 439124 KB Output isn't correct
8 Incorrect 195 ms 439120 KB Output isn't correct
9 Incorrect 198 ms 440144 KB Output isn't correct
10 Incorrect 177 ms 438924 KB Output isn't correct
11 Incorrect 184 ms 439168 KB Output isn't correct
12 Incorrect 188 ms 438996 KB Output isn't correct
13 Incorrect 231 ms 470096 KB Output isn't correct
14 Incorrect 222 ms 457044 KB Output isn't correct
15 Incorrect 203 ms 449600 KB Output isn't correct
16 Incorrect 208 ms 455764 KB Output isn't correct
17 Incorrect 332 ms 517456 KB Output isn't correct
18 Incorrect 262 ms 480812 KB Output isn't correct
19 Incorrect 236 ms 466260 KB Output isn't correct
20 Incorrect 256 ms 481300 KB Output isn't correct
21 Incorrect 375 ms 546508 KB Output isn't correct
22 Incorrect 469 ms 595360 KB Output isn't correct
23 Incorrect 457 ms 591816 KB Output isn't correct
24 Incorrect 363 ms 546600 KB Output isn't correct
25 Incorrect 508 ms 605728 KB Output isn't correct
26 Correct 1232 ms 1032136 KB Output is correct
27 Runtime error 1164 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1149 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1139 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1117 ms 1048576 KB Execution killed with signal 9
31 Incorrect 1032 ms 927852 KB Output isn't correct
32 Runtime error 1162 ms 1048576 KB Execution killed with signal 9