Submission #1104582

#TimeUsernameProblemLanguageResultExecution timeMemory
1104582simona1230Stranded Far From Home (BOI22_island)C++17
0 / 100
184 ms16980 KiB
#include <bits/stdc++.h> using namespace std; int n,m; int b[200001]; pair<int,int> a[200001]; vector<int> v[200001]; void read() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i].first; b[i]=a[i].first; a[i].second=i; } for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; v[x].push_back(y); v[y].push_back(x); } } pair<int,int> p[200001]; long long sz[200001]; pair<int,int> parent(int x) { if(x==p[x].first)return p[x]; pair<int,int> y=parent(p[x].first); y.second=max(y.second,p[x].second); return p[x]=y; } void unite(int i,int j) { pair<int,int> pi=parent(i); pair<int,int> pj=parent(j); if(pi.first==pj.first)return; //cout<<i<<" "<<j<<" "<<pi.first<<" "<<pj.first<<endl; i=pi.first; j=pj.first; if(sz[i]>sz[j]) { p[j].second=1; //cout<<i<<" > "<<j<<endl; } sz[i]+=sz[j]; p[j].first=i; } void solve() { for(int i=1;i<=n;i++) { p[i].first=i; sz[i]=a[i].first; } sort(a+1,a+n+1); for(int i=1;i<=n;i++) { int vr=a[i].second; //cout<<a[i].first<<" "<<vr<<"!"<<endl; for(int j=0;j<v[vr].size();j++) { int nb=v[vr][j]; if(b[nb]<b[vr]) unite(vr,nb); } for(int j=0;j<v[vr].size();j++) { int nb=v[vr][j]; if(b[nb]==b[vr]) unite(vr,nb); } } for(int i=1;i<=n;i++) { pair<int,int> p=parent(i); cout<<(1^p.second); } cout<<endl; } int main() { read(); solve(); return 0; }

Compilation message (stderr)

island.cpp: In function 'void solve()':
island.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for(int j=0;j<v[vr].size();j++)
      |                     ~^~~~~~~~~~~~~
island.cpp:77:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for(int j=0;j<v[vr].size();j++)
      |                     ~^~~~~~~~~~~~~
#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...