Submission #1027980

#TimeUsernameProblemLanguageResultExecution timeMemory
1027980anangoStranded Far From Home (BOI22_island)C++17
0 / 100
2 ms604 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int INF = 1LL<<30; vector<int> people; vector<int> ans; class DSU { private: int n; vector<int> parent; vector<int> rank; vector<int> rank2; 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,0); } 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); if (rank2[u]==rank2[v]) rank2[u]++; rank[u]+=rank[v]; parent[v] = u; } int getrank(int u) { return rank[find(u)]; } void destroy(int u) { for (int i=0; i<n; i++) { if (find(i)==find(u)) { ans[i] = 0; } } } }; signed main() { #ifndef ONLINE_JUDGE // for getting input from input.txt freopen("input.txt", "r", stdin); // for writing output to output.txt freopen("output.txt", "w", stdout); #endif /*#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,1); 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); 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; } for (int i=0; i<n; i++) { cout << ans[i]; } cout << endl; }

Compilation message (stderr)

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