# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
777994 | 2023-07-10T01:40:39 Z | jamezzz | Teleporters (IOI08_teleporters) | C++17 | 985 ms | 65536 KB |
#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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 304 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 308 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 304 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 596 KB | Output is correct |
2 | Correct | 6 ms | 1084 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 596 KB | Output is correct |
2 | Correct | 6 ms | 1072 KB | Output is correct |
3 | Correct | 13 ms | 1872 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 4160 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 1488 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 69 ms | 7204 KB | Output is correct |
2 | Correct | 198 ms | 17152 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 131 ms | 19760 KB | Output is correct |
2 | Correct | 370 ms | 30968 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 524 ms | 43308 KB | Output is correct |
2 | Correct | 693 ms | 35704 KB | Output is correct |
3 | Correct | 577 ms | 50388 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 907 ms | 53520 KB | Output is correct |
2 | Correct | 962 ms | 43524 KB | Output is correct |
3 | Correct | 677 ms | 59588 KB | Output is correct |
4 | Correct | 702 ms | 40824 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 952 ms | 65536 KB | Output is correct |
2 | Correct | 985 ms | 55356 KB | Output is correct |
3 | Correct | 421 ms | 65536 KB | Output is correct |
4 | Correct | 686 ms | 48664 KB | Output is correct |