Submission #604053

#TimeUsernameProblemLanguageResultExecution timeMemory
604053Ahmadsm2005Stranded Far From Home (BOI22_island)C++17
0 / 100
320 ms40608 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int N,M,V[200001],X,Y,VIS[200001]; int R[200001],DSU[200001],SUM[200001]; vector<int>edges[200001]; set<int>DSU2[200001]; int FIND(int X){ if(DSU[X] == X)return X; return FIND(DSU[X]); } int32_t main() { cin.tie(0),iostream::sync_with_stdio(0); cin>>N>>M; vector<pair<int,int>>FF; for(int i = 0; i < N; i += 1){ cin>>V[i]; FF.push_back({V[i],i}); } for(int i = 0; i < N; i += 1)DSU2[i].insert(i),DSU[i] = i,SUM[i] = V[i],R[i] = 1; sort(FF.begin(),FF.end()); for(int i = 0; i < M; i += 1){ cin>>X>>Y; edges[X - 1].push_back(Y - 1),edges[Y - 1].push_back(X - 1); } for(int i = 0 ;i < N; i += 1){ int IDX = FF[i].second, WE = FF[i].first, F2 = FIND(IDX); //cout<<"lol"<<endl; for(int l = 0; l < edges[IDX].size();l++){ if(V[edges[IDX][l]] > WE)continue; int F1 = FIND(edges[IDX][l]); if(F1 == F2)continue; int S = SUM[F1]; //cout<<S<<' '<<WE<<endl; if(S < WE){ for(auto itr = DSU2[F1].begin();itr!=DSU2[F1].end();itr++){ R[*itr] = 0; } //DSU2[F1].clear(); } if(DSU2[F1].size() < DSU2[F2].size())swap(F1,F2); SUM[F1] += SUM[F2]; DSU[F2] = F1; SUM[F2] = 0; for(auto itr = DSU2[F2].begin(); itr != DSU2[F2].end();itr++) DSU2[F1].insert(*itr); DSU2[F2].clear(); } } for(int i = 0; i < N; i += 1)cout<<R[i]; }

Compilation message (stderr)

island.cpp: In function 'int32_t main()':
island.cpp:30:26: 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]
   30 |         for(int l = 0; l < edges[IDX].size();l++){
      |                        ~~^~~~~~~~~~~~~~~~~~~
#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...