Submission #603694

#TimeUsernameProblemLanguageResultExecution timeMemory
603694shrimbStranded Far From Home (BOI22_island)C++17
0 / 100
270 ms13900 KiB
#include"bits/stdc++.h" using namespace std; const int maxn = 200001; vector<int> adj[maxn]; bitset<maxn> vis; signed main () { int n, m; cin >> n >> m; int a[n + 1]; for (int i = 1 ; i <= n ; i++) cin >> a[i]; for (int i = 0 ; i < m ; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } int v[n + 1]; for (int i = 1 ; i <= n ; i++) { v[i] = i; sort(adj[i].begin(), adj[i].end(), [&](int x, int y){return a[x] < a[y];}); } int p[n + 1]; sort(v + 1, v + 1 + n, [&](int i, int j){return a[i] < a[j];}); for (int i = 1 ; i <= n ; i++) { p[v[i]] = i; } int l = 0, r = n + 1; while (r - l > 1) { int m = (l + r) / 2; // cerr << "m: " << m << endl; priority_queue<pair<int,int>> pq; // {-value, index} int cur = a[v[m]]; pq.push({0, v[m]}); vis = 0; vis[v[m]] = 1; int good = 0; while (pq.size()) { auto [w, i] = pq.top(); pq.pop(); w *= -1; if (cur >= w) { cur += w; // cerr << "i: " << i << "\n"; good++; } else { continue; } for (int j : adj[i]) { if (!vis[j]) { vis[j] = 1; pq.emplace(-a[j], j); } } } // cerr << good << endl; if (good == n) r = m; else l = m; } // cerr << "l: " << l << endl; // for (int i = 1 ; i <= n ; i++) cout << p[i] << " "; // cout << endl; for (int i = 1 ; i <= n ; i++) { if (p[i] <= l) cout << 0; else cout << 1; } cout << endl; }
#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...