oj.uz

Submission #852648

# Submission time Handle Problem Language Result Execution time Memory
852648 2023-09-22T10:02:00 Z sunwukong123 Teleporters (IOI08_teleporters) C++14
100 / 100
 644 ms 65536 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 35416 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 35416 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 35448 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 35416 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35416 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 35416 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 35416 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 35416 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35416 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 35416 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 35416 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35416 KB Output is correct
2 Correct 8 ms 35672 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35416 KB Output is correct
2 Correct 9 ms 35672 KB Output is correct
3 Correct 17 ms 36052 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 35672 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 35936 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 37992 KB Output is correct
2 Correct 189 ms 47928 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 39528 KB Output is correct
2 Correct 266 ms 51624 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 64132 KB Output is correct
2 Correct 465 ms 65536 KB Output is correct
3 Correct 465 ms 65536 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 65536 KB Output is correct
2 Correct 620 ms 65536 KB Output is correct
3 Correct 599 ms 65536 KB Output is correct
4 Correct 571 ms 65536 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 65536 KB Output is correct
2 Correct 633 ms 65536 KB Output is correct
3 Correct 349 ms 65536 KB Output is correct
4 Correct 584 ms 65536 KB Output is correct