oj.uz

Submission #1044270

# Submission time Handle Problem Language Result Execution time Memory
1044270 2024-08-05T08:29:14 Z 김은성(#11005) Parking (CEOI22_parking) C++17
50 / 100
 145 ms 38088 KB 
#include <bits/stdc++.h>
using namespace std;
bool ch[200009];
vector<pair<int, int> > graph[200009];
int b[200009], t[200009];
unordered_set<int> emp;
vector<int> color[200009];
vector<pair<int, int> > ans;
vector<int> comp, cols;
bool done[200009];
void dfs(int v){
	ch[v] = 1;
	cols.push_back(v);
	for(auto [e, u]: graph[v]){
		comp.push_back(e);
		if(!ch[u]){
			dfs(u);
		}
	}
}
void makemove(int occ, int e){
	//printf("from=%d to=%d\n", occ, e);
	ans.push_back(make_pair(occ, e));
	if(t[occ]){
		color[t[occ]].erase(find(color[t[occ]].begin(), color[t[occ]].end(), occ));
		color[b[occ]].push_back(occ);
		if(b[e]){
			t[e] = t[occ];
			t[occ] = 0;
		}
		else{
			b[e] = t[occ];
			t[occ] = 0;
			emp.erase(e);
			color[b[e]].push_back(e);
		}
	}
	else{
		color[b[occ]].erase(find(color[b[occ]].begin(), color[b[occ]].end(), occ));
		emp.insert(occ);
		if(b[e]){
			t[e] = b[occ];
			b[occ] = 0;
		}
		else{
			b[e] = b[occ];
			b[occ] = 0;
			emp.erase(e);
			color[b[e]].push_back(e);
		}
	}
}
int main(){
	int n, m, i, j, ans2 = 0;
	bool flag = 0;
	scanf("%d %d", &n, &m);
	//assert(m<=4);
	for(i=1; i<=m; i++){
		scanf("%d %d", &b[i], &t[i]);
		if(b[i] != t[i])
			flag = 1, ans2++;
		if(b[i] + t[i] == 0)
			emp.insert(i);
		if(t[i])
			color[t[i]].push_back(i);
		else if(b[i])
			color[b[i]].push_back(i);
	}
	if(n==m){
		if(flag)
			printf("-1\n");
		else
			printf("0\n");
		return 0;
	}
	queue<int> q;
	for(int c=1; c<=n; c++){
		if(color[c].size() >= 2){
			if(!t[color[c][0]] || !t[color[c][1]]){
				q.push(c);
			}
		}
	}
	while(!q.empty()){
		int c = q.front();
		q.pop();
		if(color[c].size() >= 2){
			if(!t[color[c][0]] || !t[color[c][1]]){
				if(!t[color[c][0]]){
					makemove(color[c][1], color[c][0]);
					done[c] = 1;
					int temp = b[color[c][1]];
					if(temp && !done[temp] && color[temp].size() >= 2){
						q.push(temp);
					}
				}
				else{
					makemove(color[c][0], color[c][1]);
					done[c] = 1;
					int temp = b[color[c][0]];
					if(temp && !done[temp] && color[temp].size() >= 2){
						q.push(temp);
					}
				}
			}
		}
	}
	vector<bool> tch(n+1);
	for(i=1; i<=m; i++){
		if(b[i] && t[i]){
			tch[b[i]] = 1;
			tch[t[i]] = 1;
		}
	}
	for(i=1; i<=n; i++){
		assert(tch[i]);
	}
	for(i=1; i<=m; i++){
		if(!b[i] || !t[i])
			continue;
		graph[b[i]].push_back(make_pair(i, t[i]));
		graph[t[i]].push_back(make_pair(i, b[i]));
	}
	for(i=1; i<=n; i++){
		assert(graph[i].size());
		if(done[i] || ch[i] || graph[i][0].second == i)
			continue;
		comp.clear();
		cols.clear();
		//printf("i=%d\n", i);
		dfs(i);
		sort(comp.begin(), comp.end());
		comp.erase(unique(comp.begin(), comp.end()), comp.end());
		deque<int> qa;
		for(int c: cols){
			if(color[c].size() >= 2){
				if(!t[color[c][0]] || !t[color[c][1]])
					qa.push_front(c);
				else
					qa.push_back(c);
			}
		}
		//printf("emp.size=%d\n", emp.size());
		if(qa.empty()){
			int occ = comp[0], e = *emp.begin();
			//printf("occ=%d e=%d\n", occ, e);
			makemove(occ, e);
			for(int c: cols){
				if(color[c].size() >= 2){
					if(!t[color[c][0]] || !t[color[c][1]])
						qa.push_front(c);
					else
						qa.push_back(c);
				}
			}
		}
		//printf("qa.size=%d\n", qa.size());
		while(!qa.empty()){
			//printf("qa.front=%d\n", qa.front());
			if(done[qa.front()]){
				qa.pop_front();
				continue;
			}
			int from = color[qa.front()][0], to = color[qa.front()][1];
			//printf("from=%d to=%d\n", from, to);
			if(t[to])
				swap(from, to);
			if(t[to]){
				if(emp.empty()){
					printf("-1\n");
					return 0;
				}
				int e = *emp.begin();
				//printf("from=%d to=%d e=%d\n", from, to, e);
				makemove(from, e);
				makemove(to, e);
			}
			else{
				makemove(from, to);
			}
			done[qa.front()] = 1;
			qa.pop_front();
			for(int c: {b[from], b[to]}){
				if(c && color[c].size() == 2){
					if(!t[color[c][0]] || !t[color[c][1]])
						qa.push_front(c);
					else
						qa.push_back(c);
				}
			}
		}
	}
	printf("%d\n", ans.size());
	for(auto [u, v]: ans){
		printf("%d %d\n", u, v);
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:193:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wformat=]
  193 |  printf("%d\n", ans.size());
      |          ~^     ~~~~~~~~~~
      |           |             |
      |           int           std::vector<std::pair<int, int> >::size_type {aka long unsigned int}
      |          %ld
Main.cpp:54:15: warning: unused variable 'j' [-Wunused-variable]
   54 |  int n, m, i, j, ans2 = 0;
      |               ^
Main.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |   scanf("%d %d", &b[i], &t[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11356 KB Output is correct
2 Correct 2 ms 11356 KB Output is correct
3 Correct 2 ms 11356 KB Output is correct
4 Correct 2 ms 11356 KB Output is correct
5 Correct 2 ms 11356 KB Output is correct
6 Correct 2 ms 11356 KB Output is correct
7 Correct 3 ms 11352 KB Output is correct
8 Correct 2 ms 11356 KB Output is correct
9 Correct 2 ms 11356 KB Output is correct
10 Correct 2 ms 11356 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 49 ms 38088 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11356 KB Output is correct
2 Correct 2 ms 11356 KB Output is correct
3 Correct 2 ms 11352 KB Output is correct
4 Correct 2 ms 11356 KB Output is correct
5 Correct 2 ms 11356 KB Output is correct
6 Correct 2 ms 11352 KB Output is correct
7 Correct 2 ms 11356 KB Output is correct
8 Correct 2 ms 11352 KB Output is correct
9 Correct 3 ms 11352 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11356 KB Output is correct
2 Correct 2 ms 11356 KB Output is correct
3 Correct 2 ms 11352 KB Output is correct
4 Correct 2 ms 11356 KB Output is correct
5 Correct 2 ms 11356 KB Output is correct
6 Correct 2 ms 11352 KB Output is correct
7 Correct 2 ms 11356 KB Output is correct
8 Correct 2 ms 11352 KB Output is correct
9 Correct 3 ms 11352 KB Output is correct
10 Correct 145 ms 29292 KB Output is correct
11 Correct 44 ms 17488 KB Output is correct
12 Correct 35 ms 17356 KB Output is correct
13 Correct 137 ms 28088 KB Output is correct
14 Correct 38 ms 16072 KB Output is correct
15 Correct 48 ms 22096 KB Output is correct
16 Correct 136 ms 29448 KB Output is correct
17 Correct 65 ms 22600 KB Output is correct
18 Correct 124 ms 28860 KB Output is correct

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 22872 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11356 KB Output is correct
2 Correct 2 ms 11356 KB Output is correct
3 Correct 2 ms 11356 KB Output is correct
4 Correct 2 ms 11356 KB Output is correct
5 Correct 2 ms 11356 KB Output is correct
6 Correct 2 ms 11356 KB Output is correct
7 Correct 3 ms 11352 KB Output is correct
8 Correct 2 ms 11356 KB Output is correct
9 Correct 2 ms 11356 KB Output is correct
10 Correct 2 ms 11356 KB Output is correct
11 Runtime error 49 ms 38088 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -