Submission #117594

#TimeUsernameProblemLanguageResultExecution timeMemory
117594KieranHorganSalesman (IOI09_salesman)C++17
0 / 100
862 ms10752 KiB
#pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #pragma GCC optimization ("unroll-loops") #include <bits/stdc++.h> using namespace std; #define endl '\n' #define ll long long #define int long long #define ld double #define pii pair<int,int> #define rand() abs((rand()<<15)|rand()) #define randll() abs(((long long)rand()<<30)|rand()) const int MOD = 1000000007; char grid[805][805]; int dist1[805][805]; pair<int,int> dist3[805][805]; int dist2[805][805]; int dist[805][805]; int vis[805][805]; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); long long seed; asm("rdtsc" : "=A"(seed)); srand(seed); int n, s; cin >> n >> s; int si, sj; int fi, fj; vector<pair<int,int>> p; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { cin >> grid[i][j]; if(grid[i][j]=='J') { si = i; sj = j; } if(grid[i][j]=='H') { fi = i; fj = j; } if(grid[i][j]=='P') { p.push_back({i,j}); } if(grid[i][j]=='B') grid[i][j]=0; } } vector<int> di = {1,0,-1,0}; vector<int> dj = {0,1,0,-1}; queue<pair<int,pair<int,int>>> q; memset(dist1,-1,sizeof(dist1)); dist1[si][sj]=0; q.push({0,{si,sj}}); while(!q.empty()) { int d = q.front().first; int i = q.front().second.first; int j = q.front().second.second; q.pop(); for(int x = 0; x < 4; x++) { if(grid[i+di[x]][j+dj[x]] == 0) continue; if(dist1[i+di[x]][j+dj[x]] != -1) continue; dist1[i+di[x]][j+dj[x]] = d+1; q.push({d+1,{i+di[x],j+dj[x]}}); } } for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(dist1[i][j]>0) { dist3[i][j] = {(dist1[i][j]+s-1)/s,(dist1[i][j]+s-1)%s}; } memset(dist2,-1,sizeof(dist2)); for(auto pp: p) { int pi = pp.first; int pj = pp.second; dist2[pi][pj]=0; q.push({0,{pi,pj}}); } while(!q.empty()) { int d = q.front().first; int i = q.front().second.first; int j = q.front().second.second; q.pop(); for(int x = 0; x < 4; x++) { if(grid[i+di[x]][j+dj[x]] == 0) continue; if(dist2[i+di[x]][j+dj[x]] != -1) continue; if(grid[i+di[x]][j+dj[x]] == 'H') continue; dist2[i+di[x]][j+dj[x]] = d+1; q.push({d+1,{i+di[x],j+dj[x]}}); } } for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(dist1[i][j]>=0) { dist[i][j] = dist2[i][j]-dist3[i][j].first-(dist3[i][j].second==s-1); } // for(int i = 1; i <= n; i++) { // for(int j = 1; j <= n; j++) { // cerr << dist3[i][j].first << ":" << dist3[i][j].second << " "; // } // cerr << endl; // } // cerr << endl; // for(int i = 1; i <= n; i++) { // for(int j = 1; j <= n; j++) { // cerr << dist2[i][j] << " "; // } // cerr << endl; // } // cerr << endl; // for(int i = 1; i <= n; i++) { // for(int j = 1; j <= n; j++) { // cerr << dist[i][j] << " "; // } // cerr << endl; // } // cerr << endl; priority_queue<pair<int,pair<int,int>>> pq; pq.push({dist[si][sj], {si, sj}}); int ans = dist[si][sj]; bool toBreak = 0; while(!pq.empty()) { int d = pq.top().first; int i = pq.top().second.first; int j = pq.top().second.second; pq.pop(); ans = min(ans, d); if(i==fi && j == fj) break; for(int x = 0; x < 4; x++) { if(grid[i+di[x]][j+dj[x]] == 'H') {toBreak = 1; break;} if(grid[i+di[x]][j+dj[x]] == 0) continue; if(dist1[i+di[x]][j+dj[x]] <= 0) continue; if(vis[i+di[x]][j+dj[x]]) continue; vis[i+di[x]][j+dj[x]] = 1; pq.push({dist[i+di[x]][j+dj[x]],{i+di[x],j+dj[x]}}); } if(toBreak)break; } cout << ans << endl; }

Compilation message (stderr)

salesman.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
salesman.cpp: In function 'int main()':
salesman.cpp:141:17: warning: 'fj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(i==fi && j == fj) break;
               ~~^~~~~
salesman.cpp:141:7: warning: 'fi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(i==fi && j == fj) break;
      ~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...