Submission #1104429

#TimeUsernameProblemLanguageResultExecution timeMemory
1104429vivkostovStranded Far From Home (BOI22_island)C++14
0 / 100
131 ms32516 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } struct cell { int st,in; }; bool cmp(cell a1,cell a2) { return a1.st<a2.st; } int n,m,l,r,lead[200005],sz[200005],lamp[200005],st[200005],otg[200005]; vector<int>valid[200005],v[200005]; cell a[200005]; void prec() { for(int i=1;i<=n;i++) { lead[i]=i; sz[i]=1; st[i]=a[i].st; valid[i].push_back(i); } } int get_lead(int beg) { if(lead[beg]==beg)return beg; return get_lead(lead[beg]); } void ad(int a,int b) { a=get_lead(a); b=get_lead(b); if(a==b)return; if(sz[a]<sz[b])swap(a,b); lead[b]=lead[a]; sz[a]+=sz[b]; st[a]+=st[b]; for(int i=0;i<valid[b].size();i++) { valid[a].push_back(valid[b][i]); } } void rem(int in,int tresh) { in=get_lead(in); if(st[in]<tresh) { valid[in].clear(); } } void add(int a,int tresh) { lamp[a]=1; for(int i=0;i<v[a].size();i++) { if(lamp[v[a][i]]) { rem(v[a][i],tresh); ad(a,v[a][i]); } } } void read() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i].st; a[i].in=i; } for(int i=1;i<=m;i++) { cin>>l>>r; v[l].push_back(r); v[r].push_back(l); } prec(); sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++) { add(a[i].in,a[i].st); } int f=get_lead(1); for(int i=0;i<valid[f].size();i++) { otg[valid[f][i]]=1; } for(int i=1;i<=n;i++) { cout<<otg[i]; } cout<<endl; } int main() { speed(); read(); return 0; }

Compilation message (stderr)

island.cpp: In function 'void ad(int, int)':
island.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=0;i<valid[b].size();i++)
      |                 ~^~~~~~~~~~~~~~~~
island.cpp: In function 'void add(int, int)':
island.cpp:61:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i=0;i<v[a].size();i++)
      |                 ~^~~~~~~~~~~~
island.cpp: In function 'void read()':
island.cpp:91:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int i=0;i<valid[f].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...