oj.uz

Submission #1044177

# Submission time Handle Problem Language Result Execution time Memory
1044177 2024-08-05T07:51:06 Z 김은성(#11005) Parking (CEOI22_parking) C++17
8 / 100
 93 ms 23632 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());
		queue<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;
		}
		else{
			ans2 += max(1, (int)qa.size());
			continue;
		}
		//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.front()]){
				qa.pop();
				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();
			for(int c: {b[from], b[to]}){
				if(c && color[c].size() == 2){
					qa.push(c);
				}
			}
		}
	}
	printf("%d\n", ans2);
	return 0;
	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::queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   91 |   if(m-n == 1 && qa.size() > m-n){
      |                  ~~~~~~~~~~^~~~~
Main.cpp:144: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=]
  144 |  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

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 11352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 22464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
5.0 / 25.0

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

Subtask #4
3.0 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 11352 KB Output is partially correct
2 Correct 3 ms 11608 KB Output is correct
3 Correct 2 ms 11352 KB Output is correct
4 Partially correct 2 ms 11356 KB Output is partially correct
5 Correct 3 ms 11356 KB Output is correct
6 Correct 3 ms 11356 KB Output is correct
7 Partially correct 2 ms 11352 KB Output is partially correct
8 Correct 2 ms 11356 KB Output is correct
9 Partially correct 2 ms 11352 KB Output is partially correct
10 Partially correct 80 ms 22132 KB Output is partially correct
11 Correct 40 ms 17500 KB Output is correct
12 Correct 45 ms 17440 KB Output is correct
13 Partially correct 75 ms 23632 KB Output is partially correct
14 Correct 64 ms 17644 KB Output is correct
15 Correct 45 ms 17496 KB Output is correct
16 Partially correct 93 ms 22492 KB Output is partially correct
17 Correct 69 ms 17404 KB Output is correct
18 Partially correct 85 ms 23276 KB Output is partially correct

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 11608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 11352 KB Output isn't correct
2 Halted 0 ms 0 KB -