#include <bits/stdc++.h>
using namespace std;
#define paiu return
#define moment 0;
#define int long long
#define double long double
#define ll long long
#define forr(i,x) for (int i=0; i<x; i++)
#define forn(i,x) for (int i=0; i<x; i++)
#define vi(a,n) vector<int> a(n,0)
//cringe define
#define vii(a,n) vi(a,n); forr(i,n) cin>>a[i];
vector<int> ___makeprefsum(vector<int>&a) {
int n=a.size();
vi(pr,n+1);
forn(i,n) pr[i+1]=pr[i]+a[i];
return pr;
}
#define prefsum(pr,a) vector<int> pr=___makeprefsum(a);
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb(x) push_back(x)
#define pf pop_front();
#define last(c) c[c.size()-1]
#define f first
#define s second
#define pi pair<int, int>
#define mp(x,y) make_pair(x, y)
const ll mod = 1000000007;
const double ppi = acos(0) * 2;
const int maxn = 1e5+1;
const int inf = INT_MAX;
const ll linf = LLONG_MAX;
const ll mmod = 998244353;
vector<int> a;
vector<vector<int>> adj(2e5);
auto cmp = [](int i, int j) { return a[i]<=a[j]; };
void subtask1(int n, int m) {
string ans(n,'1');
forn(i,n) {
set<int,decltype(cmp)> s(cmp);
int cnt=a[i];
bitset<2000> vis; vis.set(i,1); //cout<<i+1<<"->";
for (auto v:adj[i]) { s.insert(v); vis.set(v,1); }
while (!s.empty()) {
auto it=s.begin();
int u=*it;
//cout<<u+1<<"->";
if (a[u]>cnt) {ans[i]='0'; break;}
cnt+=a[u];
vis.set(u,1);
s.erase(it);
for (auto v:adj[u]) if (!vis[v]) { s.insert(v); vis.set(v,1); }
}
//cout<<'\n';
}
cout<<ans<<'\n';
}
void dfs(vector<vector<int>>&adj, vector<int>&vis, vector<int>&d, int v) {
if (vis[v]) return;
vis[v]=1;
d[v]+=a[v]; //cout<<v<<' '<<d[v]<<' '<<a[v]<<'\n';
for (auto u:adj[v]) {
dfs(adj,vis,d,u);
if (u>v) d[v]+=d[u];
}
}
void ver(vector<vector<int>>&adj, vector<int>&vis, vector<int>&d, vector<int>&up, int v) {
if (vis[v]) return;
vis[v]=1;
for (auto u:adj[v]) {
if (u<v) continue;
if (d[u]>=a[v]) {
up[u]=1;
ver(adj,vis,d,up,u);
}
}
}
void subtask2(int n, int m) {
vector<int> up(n,0);
vector<int> d(n,0), vis(n,0);
dfs(adj,vis,d,0);
//forn(i,n) cout<<d[i]<<' '; cout<<'\n';
up[0]=1;
vis.assign(n,0);
ver(adj,vis,d,up,0);
forn(i,n) cout<<up[i]; cout<<'\n';
}
int n; // array size
vector<int> t;
int merge(int i, int j) {
if (a[i]<=a[j]) return i;
else return j;
}
void build(int _n) { // build the tree
a.push_back(linf);
n=_n;
for (int i = n - 1; i > 0; --i) t[i] = merge ( t[i<<1] , t[i<<1|1] );
}
void modify(int p, int value) { // set value at position p
for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = merge( t[p] , t[p^1] );
}
void subtask3(int n, int m) {
string ans(n,'1');
set<int> left;
forn(i,n) left.insert(i);
t.assign(2*n+100,n);
forn(i,n) t[n+i]=i;
build(n);
int unvis=n;
vector<int> d(n,0), vis(n,0);
forn(i,n) d[i]=a[i];
while (unvis) {
int u=t[1]; --unvis;
if (u==n) break;
if (left.find(u)!=left.end()) left.erase(left.find(u));
vector<int> path = {u};
auto it1=left.lower_bound(u), it2=left.upper_bound(u);
d.push_back(linf);
int l=n,r=n;
if (it1!=left.begin()) {--it1;
l=*it1;
}
if (it2!=left.end()) {
r=*it2;
}
while (l!=n || r!=n) {
int v;
if (d[l]<=d[r]) v=l;
else v=r;
if (a[u]>a[l] && a[u]>a[r]) break;
else if (a[u]>a[v]) v = (v==l)?r:l;
if (v==n) {
for (auto x:path) { modify(x,n); }
//--unvis;
break;
}
if (d[u]>=a[v]) {
left.erase(left.find(v));
if (v<u) {
auto it1=left.lower_bound(u);
if (it1!=left.begin()) {
--it1;
l=*it1;
} else l=n;
} else {
auto it2=left.upper_bound(u);
if (it2!=left.end()) {
r=*it2;
} else r=n;
}
--unvis;
} else {
for (auto x:path) { ans[x]='0'; modify(x,n); }
d[v]+=d[u];
break;
}
d[v]+=d[u];
u=v;
path.pb(v);
}
}
cout<<ans;
}
void solve() {
int n,m; cin>>n>>m;
vii(b,n); a=b;
int _p3=1, _p2=1;
vector<int> lesscnt(n,0);
forn(i,m) {
int u,v; cin>>u>>v;
--u, --v;
if (u>v) swap(u,v);
adj[u].pb(v);
adj[v].pb(u);
_p3&=(abs(u-v)==1);
lesscnt[max(u,v)]++;
}
forn(i,n) _p2&=(i==0 || (lesscnt[i]==1));
if (n<=2000 && m<=2000) {
//subtask1(n,m);
//return;
}
forn(i,n-1) _p2&=(a[i]>=a[i+1]);
if (_p2) {
//subtask2(n,m);
//return;
}
if (_p3) {
subtask3(n,m);
return;
}
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
paiu moment
}
Compilation message
island.cpp: In function 'void subtask2(long long int, long long int)':
island.cpp:12:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
12 | #define forn(i,x) for (int i=0; i<x; i++)
| ^~~
island.cpp:105:5: note: in expansion of macro 'forn'
105 | forn(i,n) cout<<up[i]; cout<<'\n';
| ^~~~
island.cpp:105:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
105 | forn(i,n) cout<<up[i]; cout<<'\n';
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 2 |
Execution timed out |
1086 ms |
429976 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
141 ms |
16944 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
