#include <bits/stdc++.h>
#include <fstream>
using namespace std;
#define ll long long
#define vt vector
#define ar array
ifstream cinn ("in.txt");
ofstream coutt ("myout.txt");
const ll maxn = 200005;
ll weights[maxn];
ll n, m;
unordered_map<ll, vt<ll>> lines;
ll head[maxn];
unordered_set<ll> usedNodes;
unordered_set<ll> usedWeights;
vt<ll> weightsByOne;
vt<pair<ll, ll>> allWeights;
ll sizeOfWeightsSumInOneComponent[maxn];
// ll sizeOfComponent[maxn];
bool canWin[maxn];
ll weightsByOnePoll = 0;
unordered_set<int> allHeads;
pair<ll, bool> findPar(ll node){
if (head[node] != node) {
pair<ll, bool> mypair = findPar(head[node]);
head[node] = mypair.first;
canWin[node] = canWin[node] && mypair.second;
}
return {head[node], canWin[node]};
}
void checkIfFits(ll node){
ll parMy = findPar(node).first;
if (sizeOfWeightsSumInOneComponent[parMy] < weightsByOne[min((ll) weightsByOne.size() - 1, weightsByOnePoll + 1)]){
canWin[parMy] = false;
}
}
void process(ll node){
allHeads.insert(node);
usedNodes.insert(node);
for(ll j : lines[node]){
if (usedNodes.find(j) != usedNodes.end()){
ll parJ = findPar(j).first;
ll parMy = findPar(node).first;
if (parJ == parMy) continue;
if (weights[parMy] > weights[parJ]){
head[parJ] = parMy;
allHeads.erase(parJ);
// sizeOfComponent[parMy] += sizeOfComponent[parJ];
sizeOfWeightsSumInOneComponent[parMy] += sizeOfWeightsSumInOneComponent[parJ];
}else if (weights[parMy] == weights[parJ]) {
head[parMy] = parJ;
allHeads.erase(parMy);
// sizeOfComponent[parMy] += sizeOfComponent[parJ];
sizeOfWeightsSumInOneComponent[parJ] += sizeOfWeightsSumInOneComponent[parMy];
}
}
}
}
void solve(){
cin >> n >> m;
for (ll i = 0; i < n; i++){
ll w;
cin >> w;
weights[i + 1] = w;
if (usedWeights.find(w) == usedWeights.end()) {
usedWeights.insert(w);
weightsByOne.push_back(w);
}
allWeights.push_back({w, i + 1});
}
for (ll i = 0; i < m; i++){
ll a, b;
cin >> a >> b;
if (lines.find(a) == lines.end()) lines[a] = {};
if (lines.find(b) == lines.end()) lines[b] = {};
lines[a].push_back(b);
lines[b].push_back(a);
}
for (ll i = 0; i < n; i++){
head[i + 1] = i + 1;
sizeOfWeightsSumInOneComponent[i + 1] = weights[i + 1];
// sizeOfComponent[i + 1] = 1;
canWin[i + 1] = true;
}
sort(allWeights.begin(), allWeights.end());
sort(weightsByOne.begin(), weightsByOne.end());
for (ll i = 0; i < n; i++){
if (allWeights[i].first > weightsByOne[weightsByOnePoll]) {
unordered_set<int>::iterator it;
for (it = allHeads.begin(); it != allHeads.end(); it++){
checkIfFits(*it);
}
weightsByOnePoll++;
}
process(allWeights[i].second);
}
string res = "";
for (ll i = 1; i <= n; i++){
findPar(i);
}
for (ll i = 1; i <= n; i++)
res += canWin[i] ? "1" : "0";
cout << res << endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
ll testcases = 1;
// cin >> testcases;
while(testcases--){
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
6 ms |
724 KB |
Output is correct |
| 5 |
Correct |
8 ms |
724 KB |
Output is correct |
| 6 |
Correct |
2 ms |
596 KB |
Output is correct |
| 7 |
Correct |
5 ms |
704 KB |
Output is correct |
| 8 |
Correct |
4 ms |
724 KB |
Output is correct |
| 9 |
Correct |
2 ms |
716 KB |
Output is correct |
| 10 |
Correct |
9 ms |
824 KB |
Output is correct |
| 11 |
Correct |
10 ms |
724 KB |
Output is correct |
| 12 |
Correct |
8 ms |
744 KB |
Output is correct |
| 13 |
Correct |
3 ms |
624 KB |
Output is correct |
| 14 |
Correct |
3 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
299 ms |
47812 KB |
Output is correct |
| 4 |
Correct |
268 ms |
37264 KB |
Output is correct |
| 5 |
Execution timed out |
1080 ms |
38572 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Execution timed out |
1046 ms |
37960 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
433 ms |
38660 KB |
Output is correct |
| 3 |
Correct |
431 ms |
42964 KB |
Output is correct |
| 4 |
Correct |
479 ms |
43216 KB |
Output is correct |
| 5 |
Correct |
430 ms |
43092 KB |
Output is correct |
| 6 |
Correct |
380 ms |
41684 KB |
Output is correct |
| 7 |
Correct |
253 ms |
47608 KB |
Output is correct |
| 8 |
Correct |
135 ms |
41260 KB |
Output is correct |
| 9 |
Correct |
235 ms |
23460 KB |
Output is correct |
| 10 |
Correct |
369 ms |
41684 KB |
Output is correct |
| 11 |
Correct |
333 ms |
40820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
6 ms |
724 KB |
Output is correct |
| 5 |
Correct |
8 ms |
724 KB |
Output is correct |
| 6 |
Correct |
2 ms |
596 KB |
Output is correct |
| 7 |
Correct |
5 ms |
704 KB |
Output is correct |
| 8 |
Correct |
4 ms |
724 KB |
Output is correct |
| 9 |
Correct |
2 ms |
716 KB |
Output is correct |
| 10 |
Correct |
9 ms |
824 KB |
Output is correct |
| 11 |
Correct |
10 ms |
724 KB |
Output is correct |
| 12 |
Correct |
8 ms |
744 KB |
Output is correct |
| 13 |
Correct |
3 ms |
624 KB |
Output is correct |
| 14 |
Correct |
3 ms |
724 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
299 ms |
47812 KB |
Output is correct |
| 18 |
Correct |
268 ms |
37264 KB |
Output is correct |
| 19 |
Execution timed out |
1080 ms |
38572 KB |
Time limit exceeded |
| 20 |
Halted |
0 ms |
0 KB |
- |
