Submission #882685

#TimeUsernameProblemLanguageResultExecution timeMemory
882685aegJakarta Skyscrapers (APIO15_skyscraper)C++14
57 / 100
1072 ms21716 KiB
#pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") #include <bits/stdc++.h> using namespace std; const int MAXM = 3e4+5, MAXN = 3e4+5; int n, p[MAXM], m, secloc; vector<int> a(MAXN, INT_MAX); queue<int> b[MAXN]; struct triple { int first, second; char third; triple() : first(0), second(0), third(0) {} triple(int a, int b, char c) :first(a), second(b), third(c) {} }; queue<triple> curr, oth; signed main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for(int i = 0; i < m; i++) { int tmp; cin >> tmp >> p[i]; if(i==0) curr.push({tmp, p[0], 3}); b[tmp].push(i); if(i==1) secloc = tmp; } int curval = 0; while(!curr.empty()) { auto cur = curr.front(); curr.pop(); if(a[cur.first] == INT_MAX) { while(!b[cur.first].empty()) { int x = b[cur.first].front(); b[cur.first].pop(); if(p[x] != cur.second) curr.push({cur.first, p[x], 3}); } } a[cur.first] = min(a[cur.first], curval); if(cur.first >= cur.second && cur.third != 2) oth.push({cur.first - cur.second, cur.second, 1}); if(cur.first < n - cur.second && cur.third != 1) oth.push({cur.first + cur.second, cur.second, 2}); if(curr.empty()) { swap(curr, oth); curval ++; } } cout << (a[secloc] == INT_MAX ? -1 : a[secloc]) << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...