# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
603515 | almothana05 | Stranded Far From Home (BOI22_island) | C++14 | 337 ms | 33872 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
queue<long long>q;
priority_queue<pair<long long, long long> >pri;
vector<long long>gr[200100];
long long num[200010] , sub[200010] ,vis[200100] , erg[200100];
long long dfs(long long x){
vis[x] = 1;
for(long long i = 0 ; i < gr[x].size() ; i++){
long long kind = gr[x][i];
if(vis[kind] == 0){
sub[x] += dfs(kind);
}
}
return sub[x];
}
int main(){
long long menge , numm = 0, nummer , ed;
cin >> menge >> ed;
for(long long i = 0 ;i < menge ; i++){
cin >> numm;
num[i + 1] = numm;
sub[i + 1] = num[i + 1];
}
for(long long i = 0 ; i< ed ; i++){
cin >> numm >> nummer;
gr[numm].push_back(nummer);
gr[nummer].push_back(numm);
}
if(menge > 2000){
dfs(1);
erg[1] = 1;
for(long long i = 1 ; i <=menge ; i++){
for(long long j = 0 ; j < gr[i].size() ; j++){
long long kind = gr[i][j];
if(kind < i && erg[kind] == 1 && sub[i] >= num[kind]){
erg[i] = 1;
}
}
}
for(long long i = 1; i <= menge ; i++){
cout << erg[i];
}
return 0;
}
for(long long i = 1 ; i <= menge ; i++){
long long fl = 1;
long long cmp = 0;
vis[i] = 1;
q.push(i);
while(q.size()){
long long jet = q.front();
q.pop();
cmp += num[jet];
for(long long i = 0 ; i < gr[jet].size() ; i++){
long long kind = gr[jet][i];
pri.push({-num[kind] , kind });
}
while(pri.size() && -pri.top().first <= cmp){
if(vis[pri.top().second] == 0){
vis[pri.top().second] = 1;
q.push(pri.top().second);
}
pri.pop();
}
}
while(pri.size()){
pri.pop();
}
for(long long j = 1 ; j <=menge ; j++){
if(vis[j] == 0){
fl = 0;
}
vis[j] = 0;
}
cout << fl ;
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |