Submission #777994

#TimeUsernameProblemLanguageResultExecution timeMemory
777994jamezzzTeleporters (IOI08_teleporters)C++17
100 / 100
985 ms65536 KiB
#include <bits/stdc++.h> using namespace std; #define sf scanf #define pf printf #define fi first #define se second #define pb push_back #define INF 1023456789 #define sz(x) ((int)x.size()) #define all(x) x.begin(),x.end() typedef pair<int,int> ii; #define maxn 1000005 int n,m,s[maxn],e[maxn],par[maxn<<2],sz[maxn<<2]; vector<ii> v; int fp(int i){ return par[i]==i?i:par[i]=fp(par[i]); } void join(int x,int y){ x=fp(x),y=fp(y); if(x==y)return; if(sz[x]<sz[y])swap(x,y); par[y]=x; sz[x]+=sz[y]; } int main(){ sf("%d%d",&n,&m); for(int i=0;i<2*(m+n);++i)par[i]=i,sz[i]=1; for(int i=0;i<n;++i){ sf("%d%d",&s[i],&e[i]); v.pb({s[i],2*i}); v.pb({e[i],2*i+1}); } sort(all(v)); int src=v[0].se; for(auto[x,i]:v){ int y=(i%2)?s[i>>1]:e[i>>1];//other endpoint int pos=lower_bound(all(v),ii(y+1,-1))-v.begin(); if(pos==sz(v))continue; int j=v[pos].se; join(i,j); } vector<int> s; for(int i=0;i<2*n;++i){ if(fp(i)==i&&fp(i)!=fp(src)){ s.pb(sz[i]); } } int ans=sz[fp(src)]; sort(all(s)); for(int i=0;i<m;++i){ if(!s.empty()){ ans+=2+s.back(); s.pop_back(); } else ans+=1,s.pb(1); } pf("%d\n",ans); }

Compilation message (stderr)

teleporters.cpp: In function 'int main()':
teleporters.cpp:32:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  sf("%d%d",&n,&m);
      |    ^
teleporters.cpp:35:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |   sf("%d%d",&s[i],&e[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...
#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...
#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...
#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...