Submission #1028002

#TimeUsernameProblemLanguageResultExecution timeMemory
1028002anangoStranded Far From Home (BOI22_island)C++17
100 / 100
378 ms76996 KiB
#include <bits/stdc++.h> #define int long long //#define set unordered_set using namespace std; int INF = 1LL<<30; vector<int> people; vector<int> setmoves; vector<int> ans; class DSU { private: int n; vector<int> parent; vector<int> rank; vector<int> rank2; vector<set<int>> sets; public: DSU(int sz) { n = sz; parent=vector<int>(n); iota(parent.begin(), parent.end(), (int)0); rank=vector<int>(n,1); for (int i=0; i<n; i++) rank[i] = people[i]; rank2=vector<int>(n,1); sets=vector<set<int>>(n); for (int i=0; i<n; i++) sets[i] = {i}; } int find(int node) { if (node==parent[node]) return node; return parent[node] = find(parent[node]); } void link(int u, int v) { u=find(u); v=find(v); if (u==v) { return; } if (rank2[u]<rank2[v]) { swap(u,v); //swap(sets[u],sets[v]); } rank2[u]+=rank2[v]; rank2[v] = 0; rank[u]+=rank[v]; rank[v] = 0; for (int j:sets[v]) { sets[u].insert(j); setmoves[j]++; } sets[v].clear(); parent[v] = u; } int getrank(int u) { return rank[find(u)]; } void destroy(int u) { sets[u].clear(); } vector<set<int>> getsets() { return sets; } }; signed main() { int local = 0; if (local) { // for getting input from input.txt freopen("input.txt", "r", stdin); // for writing output to output.txt freopen("output.txt", "w", stdout); } /*#ifdef ONLINE_JUDGE ios_base::sync_with_stdio(false); cin.tie(NULL); #endif*/ //fast IO int n,m; cin >> n >> m; //want to calculate for each node, //the smallest w such that if we remove all nodes of weight > w, the connected component containing this node //has total weight at most w //use DSU //make w take on the weight of each node + 1, in increasing order //any set that has sum at most the current w is not allowable //actually it's easier to merge the sets of indices from small to large //so a set is marked as bad when it is merged into a larger set ans=vector<int>(n,0); people=vector<int>(n); for (int i=0; i<n; i++) cin >> people[i]; vector<int> order(n); iota(order.begin(), order.end(), (int)0); sort(order.begin(), order.end(), [&](const int i1, const int i2) { return people[i1]<people[i2]; }); vector<vector<int>> adjlist(n); for (int i=0; i<m; i++) { int u,v; cin >> u >> v; u--; v--; adjlist[u].push_back(v); adjlist[v].push_back(u); } DSU dsu(n); setmoves=vector<int>(n,0); vector<int> active(n,0); for (int oi=0; oi<n; oi++) { int k = order[oi]; //cout << "adding node " << oi <<" " << k <<" " << people[k] << endl; for (int j:adjlist[k]) { if (active[j]) { int r1 = dsu.getrank(j); // cout << "adding edge " << k <<" " << j <<" " << r1 << endl; if (r1<people[k]) { dsu.destroy(dsu.find(j)); } dsu.link(k,j); } else { //cout << "inactive edge " << k <<" " << j << endl; } } active[k] = 1; } vector<set<int>> settings = dsu.getsets(); for (auto i:settings) { for (auto j:i) { ans[j] = 1; } } int mamove = *max_element(setmoves.begin(), setmoves.end()); assert(mamove<30); for (int i=0; i<n; i++) { cout << ans[i]; } cout << endl; }

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
island.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...