Submission #1370156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1370156		magentor	Teleporters (IOI08_teleporters)	C++20	100 / 100	370 ms	36036 KiB

teleporters

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define rep2(i, m ,n) for (int i = (m); i < (long long)(n); i++)
#define REP(i, n) for (long long i = 1; i < (long long)(n); i++)
typedef long long ll;
#define l(n) n.begin(),n.end()
#define YesNo(Q) Q==1?cout<<"Yes":cout<<"No"

struct dsu{
  vector<int> par,siz;
  void reset(int n){par.resize(n);siz.resize(n);rep(i,n){par[i]=-1;siz[i]=1;}}
  
  int leader(int x){
   if(par[x]==-1){return x;}
   else{return par[x] = leader(par[x]);} 
  }
  
  bool same(int x,int y){
   return leader(x)==leader(y); 
  }
  
  bool merge(int x,int y){
   x = leader(x);y=leader(y);
   if(x == y){return false;}
   if(siz[x] < siz[y]){swap(x,y);} 
   par[y] = x;
  siz[x] += siz[y];
  return true; 
  }
  
  
 
int size(int x){
 return siz[leader(x)]; 
}
 
};
int k = 2000005;
int t[2000004];

int main(){
 int n,m;cin>>n>>m;

 dsu d;d.reset(k);
 vector<bool> c(k-1,0);
 rep(i,k-1){
   t[i] = i+1;
 }
 d.merge(0,k-1);
 rep(i,n){
   int u,v;cin>>u>>v;
   t[u-1] = v;
   c[u-1]=true;
   t[v-1] = u;
   c[v-1]=true;
 }
 rep(i,k-1){
   d.merge(i,t[i]);
 }
 ll mt = 0;
 vector<int> mp(k,0);
 rep(i,k-1){
   if(c[i]==1){
     //cout << i << endl;
     if(!d.same(0,i)){mp[d.leader(i)]++;}
     else{mt++;}
   }
 }
 vector<int> y;
 rep(i,mp.size()){
   if(0<mp[i]){y.push_back(mp[i]);}
 }
 sort(l(y));reverse(l(y));

 rep(i,y.size()){
   if(0<m){
     m--;
     mt += y[i];
     mt += 2;
   }
 }
 if(0<m){
   mt += 4*(m/2)+(m%2);
 }
 cout << mt << endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5