#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);
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<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;
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
island.cpp: In function 'int main()':
island.cpp:85:9: warning: unused variable 'tc' [-Wunused-variable]
85 | int tc=0;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
6748 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Runtime error |
183 ms |
49876 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
198 ms |
24636 KB |
Output is correct |
| 3 |
Runtime error |
235 ms |
49752 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 2 |
Incorrect |
171 ms |
24816 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
6748 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
