제출 #882692

#제출 시각아이디문제언어결과실행 시간메모리
882692aegJakarta Skyscrapers (APIO15_skyscraper)C++14
57 / 100
1002 ms21696 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; { int tmp; cin >> tmp >> p[0]; curr.push({tmp, p[0], 3}); b[tmp].push(0); } { int tmp; cin >> tmp >> p[1]; secloc = tmp; b[tmp].push(1); } for(int i = 2; i < m; i++) { int tmp; cin >> tmp >> p[i]; b[tmp].push(i); } 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 & 1) oth.push({cur.first - cur.second, cur.second, 1}); if(cur.first < n - cur.second && cur.third & 2) 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...