제출 #969401

#제출 시각아이디문제언어결과실행 시간메모리
969401aegStranded Far From Home (BOI22_island)C++14
100 / 100
480 ms58036 KiB
#include <bits/stdc++.h> using namespace std; const int N = (int)2e5 + 7; int n, m, a[N], p[N]; vector<int> pos[N]; vector<int> need[N]; bool ans[N]; set<pair<long long, int> > have; long long s[N]; void comb(int u, int v) { int l = p[u]; int r = p[v]; if(l == r) { return; } have.erase({s[l], l}); have.erase({s[r], r}); if((int)pos[l].size() > (int)pos[r].size()) { for(auto x : pos[r]) { p[x] = l; pos[l].push_back(x); } for(auto x : need[r]) { need[l].push_back(x); } pos[r].clear(); need[r].clear(); s[l] += s[r]; if(!need[l].empty()) { have.insert({s[l], l}); } } else { for(auto x : pos[l]) { p[x] = r; pos[r].push_back(x); } for(auto x : need[l]) { need[r].push_back(x); } pos[l].clear(); need[l].clear(); s[r] += s[l]; if(!need[r].empty()) { have.insert({s[r], r}); } } } long long val[N]; int b[N]; bool cmp2(int i, int j) { return a[i] < a[j]; } vector<int> g[N]; int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for(int i = 1; i <= n; ++i) { cin >> a[i]; p[i] = i; b[i] = i; s[i] = a[i]; pos[i].push_back(i); need[i].push_back(i); } for(int i = 1; i <= n; ++i) { ans[i] = 1; } for(int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } sort(b+1, b+1+n, cmp2); for(int i = 1; i <= n; ++i) { if(a[b[i]] == a[b[n]]) { break; } int r = i; while(r<n && a[b[r]] == a[b[r+1]]) { r++; } for(int k = i; k <= r; ++k) { have.insert({a[b[r]], b[k]}); } for(int k = i; k <= r; ++k) { for(auto u : g[b[k]]) { if(a[u] <= a[b[k]]) { comb(u, b[k]); } } } for(int k = i; k <= r; ++k) { for(auto u : g[b[k]]) { long long cur = s[p[b[k]]]; if(cur >= a[u]) { comb(u, b[k]); } } } vector<pair<long long, int> > del; for(auto [cur, k] : have) { if(cur < a[b[r+1]]) { for(auto x : need[k]) { ans[x] = 0; } del.push_back({cur, k}); need[k].clear(); } else { break; } } for(auto e : del) { have.erase(e); } i = r; } for(int i = 1; i <= n; ++i) { cout << ans[i]; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

island.cpp: In function 'int main()':
island.cpp:112:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  112 |   for(auto [cur, k] : have) {
      |            ^
#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...