#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
#define pb push_back
#define popb pop_back
#define pp pop_back
#define pf push_front
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define ff first
#define ss second
///#define int ll
int nx[4] = {0,0,1,-1}, ny[4] = {1,-1,0,0};
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}
const int nax = 2e5 + 4;
int n, m;
ll s[nax];
vi adj[nax];
ll pref[nax];
void sub1()
{
string ans = "";
for(int i = 1; i<= n; i++)
ans += '1';
ll sum = 0ll;
for(int i = 1 ; i <= n ;i ++ )
sum += s[i];
for(int i = 1; i <= n; i++)
{
ll cur = s[i];
set<pll> pq;
for(auto e: adj[i])
pq.insert({s[e],e});
bool vis[n + 1];
memset(vis,false,sizeof(vis));
vis[i] = 1;
while(!pq.empty())
{
pll u = *(pq.begin());
pq.erase(pq.begin());
if(u.ff > cur)
{
ans[i - 1] = '0';
vis[u.ss] = 0;
break;
}
cur += u.ff;
vis[u.ss] = 1;
for(auto e: adj[u.ss])
{
if(vis[e])
continue;
vis[e] = 1;
pq.insert({s[e],e});
}
}
if(cur < sum)
ans[ i - 1] - '0';
}
cout << ans;
}
void solve()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> s[i];
for(int i = 1; i <= m; i ++)
{
int a, b;
cin >> a >> b;
adj[a].pb(b);
adj[b].pb(a);
}
/*if(n <= 2000 && m <= 2000)
{
sub1();
return ;
}
*/
for(int i = 1;i <= n ;i++)
pref[i] = pref[i - 1] + s[i];
int mint[n + 1];
int maxt[n + 1];
string ans = "";
for(int i = 1; i <= n; i++)
{
mint[i] = maxt[i] = i;
ans += '1';
}
for(int node = 1; node <= n; node++)
{
ll cur = s[node];
int i = node - 1, j= node + 1;
//cout << node << endl;
while(i > 0 || j <= n)
{
//i = mint[j - 1] - 1;
j = maxt[i + 1] + 1;
//cout << node << ' ' << i << ' ' << j << endl;
if(i >= 1)
{
//cout << i << endl;
if(s[i] <= cur)
{
maxt[i] = j - 1;
mint[j - 1] = i;
cur += s[i];
i --;
continue;
}
}
if(j <= n)
{
//cout << j << endl;
if(s[j] <= cur)
{
maxt[i + 1] = j;
mint[j] = i + 1;
cur += s[j];
j ++;
continue;
}
}
break;
}
//cout << node << ' ' << i << ' ' << j << endl;
ans[node - 1] = (char)((int)('0') + (i == 0 && j == n + 1));
}
cout << ans;
}
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tt = 1;
while(tt --)
solve();
}
Compilation message
island.cpp: In function 'void sub1()':
island.cpp:80:33: warning: value computed is not used [-Wunused-value]
80 | ans[ i - 1] - '0';
island.cpp: In function 'void solve()':
island.cpp:104:17: warning: variable 'mint' set but not used [-Wunused-but-set-variable]
104 | int mint[n + 1];
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
5076 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Execution timed out |
1091 ms |
16236 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Execution timed out |
1084 ms |
16244 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Execution timed out |
1093 ms |
16272 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
5076 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
