Submission #1256421

#TimeUsernameProblemLanguageResultExecution timeMemory
1256421BigBadBullyStranded Far From Home (BOI22_island)C++20
10 / 100
1097 ms51780 KiB
#include <bits/stdc++.h> #define int long long #define pii pair<int, int> #define ff first #define ss second using namespace std; const int inf = 1e18 + 5; const int mod = 1e9 + 7; const int maxm = 5e6 + 1; const pii bad = {inf, inf}; using ll = long long; using ld = long double; void solve() { int n, m; cin >> n >> m; vector<int> v(n); for (int i = 0; i < n; i++) cin >> v[i]; vector<vector<pii>> adj(n); for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; adj[--a].push_back({v[--b], b}); adj[b].push_back({v[a], a}); } for(auto&a:adj) sort(a.begin(),a.end()),reverse(a.begin(),a.end()); vector<list<pii>> graph(n); for (int i =0 ; i < n; i++) { for (pii x : adj[i]) graph[i].push_back(x); if(graph[i].size()) reverse(graph[i].begin(),graph[i].end()); } vector<pii> orig(n); for (int i = 0; i < n; i++) orig[i] = {v[i], i}; sort(orig.begin(), orig.end()); vector<int> par(n, 0); for (int i = 0; i < n; i++) par[i] = i; auto sz = v; function<int(int)> fnd = [&](int x) -> int { if (par[x] == x) return x; return par[x] = fnd(par[x]); }; auto unite = [&](int a, int b) { a = fnd(a), b = fnd(b); if(a==b)return; if (graph[a].size() > graph[b].size()) swap(a, b); graph[b].merge(graph[a]); par[a] = b; sz[b] += sz[a]; }; vector<int> af(n, -1); orig.push_back({inf, inf}); int l = 0; for (int r = 1; r <= n; r++) { if (orig[r].ff != orig[r - 1].ff) { for (int i = l; i < r; i++) { int idx = orig[i].ss; while(adj[idx].size() && (adj[idx].back()).ff <= orig[i].ff) unite(adj[idx].back().ss,idx),adj[idx].pop_back(); } for (int i = l; i < r; i++) { int idx = fnd(orig[i].ss); int ri = orig[i].ss; while(graph[idx].size() && graph[idx].front().ff <= orig[i].ff) graph[idx].pop_front(); auto gurt = graph[idx]; if (gurt.empty()) af[ri] = ri; else if (sz[fnd(ri)] >= gurt.front().ff) af[ri] = gurt.front().ss; } l = r; } } fnd = [&](int x)->int { if (af[x] == -1)return -1; if (af[x]==x)return x; return af[x] = fnd(af[x]); }; for (int i = 0; i < n; i++) { if (fnd(i)>=0) cout << '1'; else cout << '0'; } cout << '\n'; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); }
#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...