#include <bits/stdc++.h>
#define se second
#define fs first
#define mp make_pair
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const int N = 2e5 + 7;
const int Mod = 998244353;
const int szBL = 916;
const int INF = 1e9;
const int BASE = 137;
int n, m;
vector<int> ke[N];
int a[N];
bool Ans[N];
int larger[N];
pair<int,int> b[N];
struct Disjoin_set {
int lab[N], sz[N];
ll tot[N];
vector<int> vec[N];
set<pair<int,int>> Sadj[N];///greater val
void init (int n) {
rep (i, 1, n) {
lab[i] = i, sz[i] = 1, tot[i] = a[i];
vec[i] = {i};
iter (&id, ke[i]) {
Sadj[i].insert(mp(a[id], id));
}
}
}
int Find (int u) {
return u == lab[u] ? u : lab[u] = Find(lab[u]);
}
void Join (int u, int v) { /// u wanna combine, not v
u = Find(u);
v = Find(v);
if (u == v) return;
if (sz[u] < sz[v]) swap(u, v);
lab[v] = u;
sz[u] += sz[v];
iter (&id, vec[v]) {
iter (&idto, ke[id]) {
Sadj[u].insert(mp(a[idto], idto));
}
vec[u].push_back(id);
}
tot[u] += tot[v];
vector<int> ().swap(vec[v]);
}
int Find_Larger (int u) {
int idx = u;
u = Find(u);
auto it = Sadj[u].lower_bound(mp(a[idx] + 1, -INF));
if (it == Sadj[u].end()) return -1;
else return it->se;
}
}DSU;
struct Disjoin_set2 {
int lab[N], sz[N];
ll tot[N];
struct Data {
int labu, labv, szu, szv;
ll totu, totv;
};
stack<Data> op;
void init (int n) {
rep (i, 1, n) {
lab[i] = i, sz[i] = 1, tot[i] = a[i];
}
}
int Find (int u) {
return u == lab[u] ? u : Find(lab[u]);
}
void Join (int u, int v) { /// u wanna combine, not v
u = Find(u);
v = Find(v);
op.push({lab[u], lab[v], sz[u], sz[v], tot[u], tot[v]});
if (u == v) return;
if (sz[u] < sz[v]) swap(u, v);
lab[v] = u;
sz[u] += sz[v];
tot[u] += tot[v];
}
void roll_back() {
Data cur = op.top();
op.pop();
int u = cur.labu, v = cur.labv;
lab[u] = cur.labu;
lab[v] = cur.labv;
sz[u] = cur.szu;
sz[v] = cur.szv;
tot[u] = cur.totu;
tot[v] = cur.totv;
}
}DSU2;
void solution () {
cin >> n >> m;
rep (i, 1, n) {
cin >> a[i];
b[i].fs = a[i];
b[i].se = i;
}
rep (i, 1, m) {
int u, v;
cin >> u >> v;
ke[u].push_back(v);
ke[v].push_back(u);
}
DSU.init(n);
DSU2.init(n);
sort (b + 1, b + 1 + n);
rep (i, 1, n) {
static vector<int> vec; vec.clear();
while (b[i].fs == b[i + 1].fs) vec.push_back(b[i++].se);
vec.push_back(b[i].se);
iter (&idx, vec) {
iter (&to, ke[idx]) {
if (a[idx] >= a[to]) {
DSU.Join (idx, to);
DSU2.Join (idx, to);
}
}
}
iter (&idx, vec) {
larger[idx] = DSU.Find_Larger(idx);
}
}
reb (i, n, 1) {
static vector<int> vec; vec.clear();
while (b[i].fs == b[i - 1].fs) vec.push_back(b[i--].se);
vec.push_back(b[i].se);
iter (&id, vec) {
// cout << id<<": "<<DSU2.tot[DSU2.Find(id)]<<"\n";
if (larger[id] == -1 || (DSU2.tot[DSU2.Find(id)] >= a[larger[id]] && Ans[larger[id]] == 1)) {
Ans[id] = 1;
}
else Ans[id] = 0;
}
iter (&id, vec) iter (&to, ke[id]) {
if (a[id] >= a[to]) {
// cout << id
DSU2.roll_back();
}
}
}
// rep (i, 1, n) cout << i <<" "<<larger[i] <<"\n";
rep (i ,1, n) cout << Ans[i];
}
#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// file ("c");
int num_Test = 1;
// cin >> num_Test;
while (num_Test--)
solution();
}
/*
5 10
1 2
3 1
4 2
5 3
1 4
2 3
3 5
4 5
3 4
1 4
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
28504 KB |
Output is correct |
2 |
Correct |
4 ms |
28504 KB |
Output is correct |
3 |
Correct |
4 ms |
28504 KB |
Output is correct |
4 |
Correct |
6 ms |
29020 KB |
Output is correct |
5 |
Correct |
6 ms |
29276 KB |
Output is correct |
6 |
Correct |
7 ms |
29276 KB |
Output is correct |
7 |
Correct |
6 ms |
29020 KB |
Output is correct |
8 |
Correct |
6 ms |
29016 KB |
Output is correct |
9 |
Correct |
6 ms |
29020 KB |
Output is correct |
10 |
Correct |
7 ms |
29380 KB |
Output is correct |
11 |
Correct |
7 ms |
29276 KB |
Output is correct |
12 |
Correct |
7 ms |
29532 KB |
Output is correct |
13 |
Correct |
5 ms |
29276 KB |
Output is correct |
14 |
Correct |
7 ms |
29272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
28508 KB |
Output is correct |
2 |
Correct |
4 ms |
28608 KB |
Output is correct |
3 |
Correct |
198 ms |
82376 KB |
Output is correct |
4 |
Correct |
176 ms |
86784 KB |
Output is correct |
5 |
Correct |
515 ms |
106476 KB |
Output is correct |
6 |
Correct |
509 ms |
111516 KB |
Output is correct |
7 |
Correct |
500 ms |
110424 KB |
Output is correct |
8 |
Correct |
316 ms |
85704 KB |
Output is correct |
9 |
Correct |
536 ms |
142284 KB |
Output is correct |
10 |
Correct |
211 ms |
68292 KB |
Output is correct |
11 |
Correct |
246 ms |
77124 KB |
Output is correct |
12 |
Correct |
366 ms |
92364 KB |
Output is correct |
13 |
Correct |
194 ms |
85700 KB |
Output is correct |
14 |
Correct |
179 ms |
86984 KB |
Output is correct |
15 |
Correct |
178 ms |
77088 KB |
Output is correct |
16 |
Correct |
228 ms |
76488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
28504 KB |
Output is correct |
2 |
Correct |
785 ms |
126624 KB |
Output is correct |
3 |
Correct |
785 ms |
130912 KB |
Output is correct |
4 |
Correct |
248 ms |
90080 KB |
Output is correct |
5 |
Correct |
228 ms |
92016 KB |
Output is correct |
6 |
Correct |
759 ms |
130064 KB |
Output is correct |
7 |
Correct |
255 ms |
81600 KB |
Output is correct |
8 |
Correct |
199 ms |
81348 KB |
Output is correct |
9 |
Correct |
146 ms |
80308 KB |
Output is correct |
10 |
Correct |
216 ms |
86720 KB |
Output is correct |
11 |
Correct |
319 ms |
96340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
28504 KB |
Output is correct |
2 |
Correct |
589 ms |
102664 KB |
Output is correct |
3 |
Correct |
593 ms |
109164 KB |
Output is correct |
4 |
Correct |
671 ms |
116536 KB |
Output is correct |
5 |
Correct |
590 ms |
119052 KB |
Output is correct |
6 |
Correct |
466 ms |
107576 KB |
Output is correct |
7 |
Correct |
309 ms |
90948 KB |
Output is correct |
8 |
Correct |
160 ms |
84936 KB |
Output is correct |
9 |
Correct |
351 ms |
82160 KB |
Output is correct |
10 |
Correct |
629 ms |
124900 KB |
Output is correct |
11 |
Correct |
352 ms |
94296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
28504 KB |
Output is correct |
2 |
Correct |
4 ms |
28504 KB |
Output is correct |
3 |
Correct |
4 ms |
28504 KB |
Output is correct |
4 |
Correct |
6 ms |
29020 KB |
Output is correct |
5 |
Correct |
6 ms |
29276 KB |
Output is correct |
6 |
Correct |
7 ms |
29276 KB |
Output is correct |
7 |
Correct |
6 ms |
29020 KB |
Output is correct |
8 |
Correct |
6 ms |
29016 KB |
Output is correct |
9 |
Correct |
6 ms |
29020 KB |
Output is correct |
10 |
Correct |
7 ms |
29380 KB |
Output is correct |
11 |
Correct |
7 ms |
29276 KB |
Output is correct |
12 |
Correct |
7 ms |
29532 KB |
Output is correct |
13 |
Correct |
5 ms |
29276 KB |
Output is correct |
14 |
Correct |
7 ms |
29272 KB |
Output is correct |
15 |
Correct |
4 ms |
28508 KB |
Output is correct |
16 |
Correct |
4 ms |
28608 KB |
Output is correct |
17 |
Correct |
198 ms |
82376 KB |
Output is correct |
18 |
Correct |
176 ms |
86784 KB |
Output is correct |
19 |
Correct |
515 ms |
106476 KB |
Output is correct |
20 |
Correct |
509 ms |
111516 KB |
Output is correct |
21 |
Correct |
500 ms |
110424 KB |
Output is correct |
22 |
Correct |
316 ms |
85704 KB |
Output is correct |
23 |
Correct |
536 ms |
142284 KB |
Output is correct |
24 |
Correct |
211 ms |
68292 KB |
Output is correct |
25 |
Correct |
246 ms |
77124 KB |
Output is correct |
26 |
Correct |
366 ms |
92364 KB |
Output is correct |
27 |
Correct |
194 ms |
85700 KB |
Output is correct |
28 |
Correct |
179 ms |
86984 KB |
Output is correct |
29 |
Correct |
178 ms |
77088 KB |
Output is correct |
30 |
Correct |
228 ms |
76488 KB |
Output is correct |
31 |
Correct |
4 ms |
28504 KB |
Output is correct |
32 |
Correct |
785 ms |
126624 KB |
Output is correct |
33 |
Correct |
785 ms |
130912 KB |
Output is correct |
34 |
Correct |
248 ms |
90080 KB |
Output is correct |
35 |
Correct |
228 ms |
92016 KB |
Output is correct |
36 |
Correct |
759 ms |
130064 KB |
Output is correct |
37 |
Correct |
255 ms |
81600 KB |
Output is correct |
38 |
Correct |
199 ms |
81348 KB |
Output is correct |
39 |
Correct |
146 ms |
80308 KB |
Output is correct |
40 |
Correct |
216 ms |
86720 KB |
Output is correct |
41 |
Correct |
319 ms |
96340 KB |
Output is correct |
42 |
Correct |
4 ms |
28504 KB |
Output is correct |
43 |
Correct |
589 ms |
102664 KB |
Output is correct |
44 |
Correct |
593 ms |
109164 KB |
Output is correct |
45 |
Correct |
671 ms |
116536 KB |
Output is correct |
46 |
Correct |
590 ms |
119052 KB |
Output is correct |
47 |
Correct |
466 ms |
107576 KB |
Output is correct |
48 |
Correct |
309 ms |
90948 KB |
Output is correct |
49 |
Correct |
160 ms |
84936 KB |
Output is correct |
50 |
Correct |
351 ms |
82160 KB |
Output is correct |
51 |
Correct |
629 ms |
124900 KB |
Output is correct |
52 |
Correct |
352 ms |
94296 KB |
Output is correct |
53 |
Correct |
6 ms |
28764 KB |
Output is correct |
54 |
Correct |
4 ms |
28508 KB |
Output is correct |
55 |
Correct |
4 ms |
28604 KB |
Output is correct |
56 |
Correct |
7 ms |
29260 KB |
Output is correct |
57 |
Correct |
7 ms |
29388 KB |
Output is correct |
58 |
Correct |
7 ms |
29276 KB |
Output is correct |
59 |
Correct |
7 ms |
29020 KB |
Output is correct |
60 |
Correct |
7 ms |
29016 KB |
Output is correct |
61 |
Correct |
6 ms |
29020 KB |
Output is correct |
62 |
Correct |
7 ms |
29276 KB |
Output is correct |
63 |
Correct |
7 ms |
29272 KB |
Output is correct |
64 |
Correct |
8 ms |
29532 KB |
Output is correct |
65 |
Correct |
5 ms |
29136 KB |
Output is correct |
66 |
Correct |
6 ms |
29276 KB |
Output is correct |
67 |
Correct |
217 ms |
86772 KB |
Output is correct |
68 |
Correct |
189 ms |
89948 KB |
Output is correct |
69 |
Correct |
519 ms |
110868 KB |
Output is correct |
70 |
Correct |
561 ms |
116116 KB |
Output is correct |
71 |
Correct |
539 ms |
114776 KB |
Output is correct |
72 |
Correct |
371 ms |
90140 KB |
Output is correct |
73 |
Correct |
590 ms |
146728 KB |
Output is correct |
74 |
Correct |
293 ms |
71896 KB |
Output is correct |
75 |
Correct |
274 ms |
80424 KB |
Output is correct |
76 |
Correct |
476 ms |
95464 KB |
Output is correct |
77 |
Correct |
290 ms |
88640 KB |
Output is correct |
78 |
Correct |
251 ms |
90084 KB |
Output is correct |
79 |
Correct |
191 ms |
81512 KB |
Output is correct |
80 |
Correct |
143 ms |
80132 KB |
Output is correct |
81 |
Correct |
775 ms |
130992 KB |
Output is correct |
82 |
Correct |
771 ms |
130960 KB |
Output is correct |
83 |
Correct |
242 ms |
90172 KB |
Output is correct |
84 |
Correct |
223 ms |
92096 KB |
Output is correct |
85 |
Correct |
745 ms |
130112 KB |
Output is correct |
86 |
Correct |
228 ms |
81436 KB |
Output is correct |
87 |
Correct |
221 ms |
81308 KB |
Output is correct |
88 |
Correct |
206 ms |
86724 KB |
Output is correct |
89 |
Correct |
310 ms |
96340 KB |
Output is correct |
90 |
Correct |
559 ms |
104572 KB |
Output is correct |
91 |
Correct |
573 ms |
109144 KB |
Output is correct |
92 |
Correct |
636 ms |
116576 KB |
Output is correct |
93 |
Correct |
555 ms |
118984 KB |
Output is correct |
94 |
Correct |
454 ms |
107464 KB |
Output is correct |
95 |
Correct |
292 ms |
90692 KB |
Output is correct |
96 |
Correct |
156 ms |
84932 KB |
Output is correct |
97 |
Correct |
356 ms |
82144 KB |
Output is correct |
98 |
Correct |
617 ms |
124884 KB |
Output is correct |
99 |
Correct |
281 ms |
94296 KB |
Output is correct |
100 |
Correct |
122 ms |
58316 KB |
Output is correct |
101 |
Correct |
600 ms |
112600 KB |
Output is correct |
102 |
Correct |
452 ms |
99788 KB |
Output is correct |
103 |
Correct |
405 ms |
89280 KB |
Output is correct |
104 |
Correct |
514 ms |
99528 KB |
Output is correct |