Submission #1051070

#TimeUsernameProblemLanguageResultExecution timeMemory
1051070sofijavelkovskaStranded Far From Home (BOI22_island)C++17
10 / 100
392 ms71636 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN=2e5, INF=2e9; int n, m; int a[MAXN]; vector<int> adj[MAXN]; int link[MAXN], csize[MAXN], cindex[MAXN]; long long sum[MAXN]; set<pair<int, int> > neighbours[MAXN]; bool compare(int x, int y) { return a[x]<a[y]; } int find(int x) { if (x==link[x]) return x; return link[x]=find(link[x]); } void unite(int x, int y, int maxvalue) { x=find(x); y=find(y); if (neighbours[cindex[x]].size()<neighbours[cindex[y]].size()) swap(x, y); for (auto t : neighbours[cindex[y]]) if (t.first>maxvalue) neighbours[cindex[x]].insert(t); neighbours[cindex[y]].clear(); cindex[y]=cindex[x]; if (csize[x]<csize[y]) swap(x, y); csize[x]=csize[x]+csize[y]; sum[x]=sum[x]+sum[y]; link[y]=x; return; } vector<bool> brute() { vector<bool> possible(n, 0); for (int i=0; i<n; i++) { priority_queue<pair<int, int> > pq; pq.push({-a[i], i}); long long sum=0; bool visited[n]={false}; while (!pq.empty()) { int x=pq.top().second; pq.pop(); if (x!=i && sum<a[x]) continue; if (visited[x]) continue; visited[x]=true; sum=sum+a[x]; for (auto y : adj[x]) if (!visited[y]) pq.push({-a[y], y}); } if (*min_element(visited, visited+n)==1) possible[i]=true; } return possible; } int main() { //ios_base::sync_with_stdio(0); //cin.tie(0); srand(time(0)); int tc=0; //cin >> tc; //while (true) { /*n=rand()%5+1; m=n-1+rand()%5; if (m>n*(n-1)/2) continue; tc=tc+1; cout << "tc " << tc << '\n'; for (int i=0; i<n; i++) { adj[i].clear(); neighbours[i].clear(); } for (int i=0; i<n; i++) a[i]=rand()%5+1; set<pair<int, int> > used; for (int x=1; x<n; x++) { int y=rand()%x; adj[x].push_back(y); adj[y].push_back(x); used.insert({x, y}); } while (used.size()<m) { int x=rand()%n; int y=rand()%n; if (x==y) continue; if (used.count({x, y}) || used.count({y, x})) continue; adj[x].push_back(y); adj[y].push_back(x); used.insert({x, y}); }*/ cin >> n >> m; for (int i=0; i<n; i++) cin >> a[i]; for (int i=0; i<m; i++) { int x, y; cin >> x >> y; adj[x-1].push_back(y-1); adj[y-1].push_back(x-1); } /*cin >> n >> m; for (int i=0; i<n; i++) cin >> a[i]; for (int i=0; i<m; i++) { int x, y; cin >> x >> y; adj[x-1].push_back(y-1); adj[y-1].push_back(x-1); }*/ int sorted[n]; for (int i=0; i<n; i++) sorted[i]=i; sort(sorted, sorted+n, compare); for (int i=0; i<n; i++) { link[i]=i; csize[i]=1; sum[i]=a[i]; cindex[i]=i; for (auto x : adj[i]) neighbours[i].insert({a[x], x}); } map<int, vector<int> > byvalue; for (int i=0; i<n; i++) byvalue[a[i]].push_back(i); bool possible[n]; for (int i=0; i<n; i++) possible[i]=true; queue<int> q; for (auto k : byvalue) { for (auto x : k.second) { for (auto y : adj[x]) if (a[y]<=a[x] && find(x)!=find(y)) unite(x, y, a[x]); } for (auto x : k.second) { int leader=find(x); while (!neighbours[cindex[leader]].empty() && (*neighbours[cindex[leader]].begin()).first<=a[x]) neighbours[cindex[leader]].erase(neighbours[cindex[leader]].begin()); if (neighbours[cindex[leader]].empty()) continue; auto it=neighbours[cindex[leader]].begin(); //cout << "x sum min " << x << ' ' << sum[leader] << ' ' << (*it).first << '\n'; if (sum[leader]>=(*it).first) continue; possible[x]=false; q.push(x); while (!q.empty()) { int y=q.front(); q.pop(); for (auto t : adj[y]) if (a[t]<=a[x] && possible[t]) { possible[t]=false; q.push(t); } } } } for (int i=0; i<n; i++) cout << possible[i]; /*auto br=brute(); bool flop=false; for (int i=0; i<n; i++) if (possible[i]!=br[i]) flop=true; if (flop) { cout << "FLOP\n"; cout << n << ' ' << m << '\n'; for (int i=0; i<n; i++) cout << a[i] << ' '; cout << '\n'; for (auto edge : used) cout << edge.first << ' ' << edge.second << '\n'; for (int i=0; i<n; i++) cout << possible[i]; cout << '\n'; for (int i=0; i<n; i++) cout << br[i]; cout << '\n'; break; }*/ } return 0; } /*#include <bits/stdc++.h> using namespace std; const int MAXN=2e5, INF=2e9; int n, m; int a[MAXN]; vector<int> adj[MAXN]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i=0; i<n; i++) cin >> a[i]; for (int i=0; i<m; i++) { int x, y; cin >> x >> y; adj[x-1].push_back(y-1); adj[y-1].push_back(x-1); } set<int> values; for (int i=0; i<n; i++) values.insert(-a[i]); bool possible[n]={false}; queue<int> q; for (auto kt : values) { int k=-kt; bool visited[n]={false}; for (int i=0; i<n; i++) { if (a[i]!=k || visited[i]) continue; visited[i]=true; long long sum=a[i]; q.push(i); vector<int> nodes; nodes.push_back(i); int minsum=INF; while (!q.empty()) { int x=q.front(); q.pop(); for (auto y : adj[x]) { if (a[y]<=k && !visited[y]) { visited[y]=true; sum=sum+a[y]; q.push(y); if (a[y]==k) nodes.push_back(y); } if (a[y]>k && possible[y]) minsum=min(minsum, a[y]); } } if (minsum>sum && k!=-(*values.begin())) continue; for (auto x : nodes) possible[x]=true; } } for (int i=0; i<n; i++) cout << possible[i]; return 0; }*/ /*#include <bits/stdc++.h> using namespace std; const int MAXN=300000; int n, m; int a[MAXN]; vector<int> adj[MAXN]; long long prefix[MAXN]; bool compare(int x, int y) { return a[x]>a[y]; } long long sum(int l, int r) { if (l==0) return prefix[r]; return prefix[r]-prefix[l-1]; } vector<bool> brute() { vector<bool> possible(n, 0); for (int i=0; i<n; i++) { priority_queue<pair<int, int> > pq; pq.push({-a[i], i}); long long sum=0; bool visited[n]={false}; while (!pq.empty()) { int x=pq.top().second; pq.pop(); if (x!=i && sum<a[x]) continue; if (visited[x]) continue; visited[x]=true; sum=sum+a[x]; for (auto y : adj[x]) if (!visited[y]) pq.push({-a[y], y}); } if (*min_element(visited, visited+n)==1) possible[i]=true; } return possible; } int main() { //ios_base::sync_with_stdio(0); //cin.tie(0); srand(time(0)); int tc=0; //cin >> tc; //while (true) { tc=tc+1; cout << "tc " << tc << '\n'; n=rand()%100+1, m=0; for (int i=0; i<n; i++) a[i]=rand()%100000+1; //for (int i=0; i<n; i++) // cout << a[i] << ' '; //cout << '\n'; cin >> n >> m; for (int i=0; i<n; i++) cin >> a[i]; for (int i=0; i<n; i++) adj[i].clear(); for (int i=0; i<m; i++) { int x, y; cin >> x >> y; adj[x-1].push_back(y-1); adj[y-1].push_back(x-1); } int sorted[n]; for (int i=0; i<n; i++) sorted[i]=i; sort(sorted, sorted+n, compare); int possible[n]={false}; possible[sorted[0]]=true; set<int> larger; larger.insert(sorted[0]); prefix[0]=a[0]; for (int i=1; i<=n; i++) prefix[i]=prefix[i-1]+a[i]; for (int i=1; i<n; i++) { int x=sorted[i]; int l=-1, r=n; auto it=larger.lower_bound(x); if (it!=larger.end()) r=*it; if (it!=larger.begin()) { it--; l=*it; } if (l!=-1 && possible[l] && sum(l+1, r-1)>=a[l]) possible[x]=true; if (r!=n && possible[r] && sum(l+1, r-1)>=a[r]) possible[x]=true; larger.insert(x); } for (int i=0; i<n; i++) cout << possible[i]; auto br=brute(); bool flop=false; for (int i=0; i<n; i++) if (possible[i]!=br[i]) flop=true; if (flop) { cout << "FLOP\n"; cout << n << '\n'; for (int i=0; i<n; i++) cout << a[i] << ' '; cout << '\n'; for (int i=0; i<n; i++) cout << possible[i]; cout << '\n'; for (int i=0; i<n; i++) cout << br[i]; cout << '\n'; break; } } return 0; }*/

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:82:9: warning: unused variable 'tc' [-Wunused-variable]
   82 |     int tc=0;
      |         ^~
#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...