Submission #1050535

#TimeUsernameProblemLanguageResultExecution timeMemory
1050535sofijavelkovskaStranded Far From Home (BOI22_island)C++17
10 / 100
1098 ms14356 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN=2e5; 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; /*vector<bool> possible(n, 0); for (int i=0; i<n; i++) { long long sum=a[i]; int l=i, r=i; while (true) { if (l>0 && sum>=a[l-1]) { sum=sum+a[l-1]; l=l-1; } else if (r<n-1 && sum>=a[r+1]) { sum=sum+a[r+1]; r=r+1; } else break; } if (l==0 && r==n-1) possible[i]=true; } return possible;*/ } 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; x=x-1; y=y-1; adj[x].push_back(y); adj[y].push_back(x); } auto br=brute(); for (int i=0; i<n; i++) cout << br[i]; return 0; srand(time(0)); int tc=0; //cin >> tc; while (true) { tc=tc+1; cout << "tc " << tc << '\n'; n=rand()%20+1, m=0; for (int i=0; i<n; i++) a[i]=rand()%20+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-1; i++) { adj[i].push_back(i+1); adj[i+1].push_back(i); } for (int i=0; i<m; i++) { int x, y; cin >> x >> y; } 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); } 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:159:14: warning: variable 'flop' set but not used [-Wunused-but-set-variable]
  159 |         bool flop=false;
      |              ^~~~
#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...