Submission #603515

#TimeUsernameProblemLanguageResultExecution timeMemory
603515almothana05Stranded Far From Home (BOI22_island)C++14
20 / 100
337 ms33872 KiB
#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)

island.cpp: In function 'long long int dfs(long long int)':
island.cpp:10:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(long long i = 0 ; i < gr[x].size() ; i++){
      |                           ~~^~~~~~~~~~~~~~
island.cpp: In function 'int main()':
island.cpp:35:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             for(long long j = 0 ; j < gr[i].size() ; j++){
      |                                   ~~^~~~~~~~~~~~~~
island.cpp:56:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             for(long long i = 0 ; i < gr[jet].size() ; i++){
      |                                   ~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...