Submission #852648

#	Time	Username	Problem	Language	Result	Execution time	Memory
852648		sunwukong123	Teleporters (IOI08_teleporters)	C++14	100 / 100	644 ms	65536 KiB

teleporters

#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 8000005;
const int inf=1000000500ll;

const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 
int n,m;
bool vis[MAXN];
vector<int>cycs;
int to[MAXN];
int SZ;
int init;
int cnter;
void dfs(int x, int head){
	if(vis[x]){
		cycs.push_back(SZ);
		SZ=0;
		return;
	}
	vis[x]=1;
	if(x==8*n+1){
		init=SZ;
		SZ=0;
		return;
	}
	if(to[x]!=-1){
		++SZ;
		dfs(to[x],head);
	} else{
		dfs(x+1,head);
	}
}
int32_t main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	memset(to,-1,sizeof to);
	vector<pi>in;
	vector<int>disc;
	for(int i=1;i<=n;i++){
		int a,b; cin >> a >> b;
		in.push_back({a,b});
		disc.push_back(a);
		disc.push_back(b);
	}
	sort(disc.begin(),disc.end());
	disc.resize(unique(disc.begin(),disc.end())-disc.begin());
	/*
	int idx=0;
	for(auto x:disc){
		mper[x]=2*(++idx);
	}*/
	for(auto x:in){
		//int a=mper[x.first];
		//int b=mper[x.second];
		int a=2*(lower_bound(disc.begin(),disc.end(),x.first)-disc.begin()+1);
		int b=2*(lower_bound(disc.begin(),disc.end(),x.second)-disc.begin()+1);
		to[a*2+1]=b*2;
		to[b*2-1]=2*(a+1);
	}
	
	for(int i=1;i<=8*n;i++){
		if(!vis[i])dfs(i,i);
	}
	sort(cycs.begin(),cycs.end(),greater<int>());

	int ans=init;

	if((int)cycs.size()>=m){
		for(int i=0;i<m;i++){
			ans+=2+cycs[i];
		}
		
	} else{
		for(int i=0;i<(int)cycs.size();i++){
			ans+=2+cycs[i];
		}
		int k=m-(int)cycs.size();
		for(int i=0;i<k;i++){
			if(i%2==0)ans+=1;
			else ans+=3;
		}
	}
	cout<<ans<<'\n';
}

• 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