oj.uz

답안 #1044180

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1044180 2024-08-05T07:53:11 Z 김은성(#11005) Parking (CEOI22_parking) C++17
40 / 100
 153 ms 29376 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];
			t[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);
	for(i=1; i<=m; i++){
		scanf("%d %d", &b[i], &t[i]);
		graph[b[i]].push_back(make_pair(i, t[i]));
		graph[t[i]].push_back(make_pair(i, b[i]));
		if(b[i] != t[i])
			flag = 1, ans2++;
		if(b[i] + t[i] == 0)
			emp.insert(i);
	}
	if(n==m){
		if(flag)
			printf("-1\n");
		else
			printf("0\n");
		return 0;
	}
	for(i=1; i<=n; i++){
		if(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());
		stack<int> qa;
		for(int v: comp){
			color[t[v]].push_back(v);
			//printf("t[v]=%d v=%d\n", t[v], v);
		}
		for(int c: cols){
			if(color[c].size() >= 2)
				qa.push(c);
		}
		if(m-n == 1 && qa.size() > m-n){
			printf("-1\n");
			return 0;
		}
		//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)
					qa.push(c);
			}
		}
		//printf("qa.size=%d\n", qa.size());
		while(!qa.empty()){
			//printf("qa.front=%d\n", qa.front());
			if(done[qa.top()]){
				qa.pop();
				continue;
			}
			int from = color[qa.top()][0], to = color[qa.top()][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.top()] = 1;
			qa.pop();
			for(int c: {b[from], b[to]}){
				if(c && color[c].size() == 2){
					qa.push(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:91:28: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   91 |   if(m-n == 1 && qa.size() > m-n){
      |                  ~~~~~~~~~~^~~~~
Main.cpp:138: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=]
  138 |  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:58:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |   scanf("%d %d", &b[i], &t[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 22872 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 74 ms 22752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 11356 KB Output is correct
2 Correct 2 ms 11352 KB Output is correct
3 Correct 2 ms 11352 KB Output is correct
4 Correct 3 ms 11356 KB Output is correct
5 Correct 3 ms 11352 KB Output is correct
6 Correct 2 ms 11352 KB Output is correct
7 Correct 2 ms 11352 KB Output is correct
8 Correct 3 ms 11356 KB Output is correct
9 Correct 2 ms 11356 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 11356 KB Output is correct
2 Correct 2 ms 11352 KB Output is correct
3 Correct 2 ms 11352 KB Output is correct
4 Correct 3 ms 11356 KB Output is correct
5 Correct 3 ms 11352 KB Output is correct
6 Correct 2 ms 11352 KB Output is correct
7 Correct 2 ms 11352 KB Output is correct
8 Correct 3 ms 11356 KB Output is correct
9 Correct 2 ms 11356 KB Output is correct
10 Correct 115 ms 29124 KB Output is correct
11 Correct 41 ms 17232 KB Output is correct
12 Correct 42 ms 17344 KB Output is correct
13 Correct 106 ms 28096 KB Output is correct
14 Correct 77 ms 17452 KB Output is correct
15 Correct 46 ms 17488 KB Output is correct
16 Correct 153 ms 29376 KB Output is correct
17 Correct 80 ms 17552 KB Output is correct
18 Correct 117 ms 28864 KB Output is correct

Subtask #5
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 11356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 22872 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -