Submission #448069

#	Time	Username	Problem	Language	Result	Execution time	Memory
448069		mosiashvililuka	Teleporters (IOI08_teleporters)	C++14	100 / 100	524 ms	65536 KiB

teleporters

#include<bits/stdc++.h>
using namespace std;
const int N=2000009;
int a,b,c,d,e,i,j,ii,jj,zx,xc,pi,fx[N],f[N],pas,bo[N],zm[N],li;
pair <int, int> P[N],p[N];
int l[N];
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>b;
	for(i=1; i<=a; i++){
		cin>>P[i].first>>P[i].second;
		pi++;p[pi].first=P[i].first;p[pi].second=P[i].second;
		pi++;p[pi].first=P[i].second;p[pi].second=P[i].first;
	}
	sort(p+1,p+pi+1);
	zx=1;
	fx[0]=zx;
	for(i=1; i<=pi; i++){
		zx++;
		fx[p[i].first]=zx;
	}
	for(i=1; i<=pi; i++){
		f[i]=fx[p[i].second];
	}
	pas=0;
	for(i=1; i<=pi; i++){
		if(bo[i]!=0) continue;
		c=i;
		while(bo[c]==0&&c!=0){
			bo[c]=1;c=f[c];zm[i]++;
		}
		if(i==1){
			pas=zm[i]-1;
		}else{
			li++;
			l[li]=zm[i];
		}
	}
	sort(l+1,l+li+1);
	while(b>0&&li>0){
		pas+=l[li]+2;b--;li--;
	}
	if(b%2==0){
		pas+=b*2;
	}else{
		pas+=b*2-1;
	}
	cout<<pas;
	return 0;
}

• 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