| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1044236 |
2024-08-05T08:13:24 Z |
김은성(#11005) |
Parking (CEOI22_parking) |
C++17 |
|
14 ms |
22876 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);
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);
}
}
}
}
}
for(i=1; i<=m; i++){
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++){
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());
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);
}
}
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){
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:130:28: warning: comparison of integer expressions of different signedness: 'std::deque<int, std::allocator<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
130 | if(m-n == 1 && qa.size() > m-n){
| ~~~~~~~~~~^~~~~
Main.cpp:184: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=]
184 | 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]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11356 KB |
Output is correct |
| 2 |
Correct |
1 ms |
11352 KB |
Output is correct |
| 3 |
Correct |
2 ms |
11352 KB |
Output is correct |
| 4 |
Correct |
2 ms |
11352 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 |
11352 KB |
Output is correct |
| 8 |
Correct |
2 ms |
11608 KB |
Output is correct |
| 9 |
Correct |
2 ms |
11352 KB |
Output is correct |
| 10 |
Correct |
2 ms |
11352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
22872 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
22616 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
22616 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
22876 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11356 KB |
Output is correct |
| 2 |
Correct |
1 ms |
11352 KB |
Output is correct |
| 3 |
Correct |
2 ms |
11352 KB |
Output is correct |
| 4 |
Correct |
2 ms |
11352 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 |
11352 KB |
Output is correct |
| 8 |
Correct |
2 ms |
11608 KB |
Output is correct |
| 9 |
Correct |
2 ms |
11352 KB |
Output is correct |
| 10 |
Correct |
2 ms |
11352 KB |
Output is correct |
| 11 |
Runtime error |
12 ms |
22872 KB |
Execution killed with signal 6 |
| 12 |
Halted |
0 ms |
0 KB |
- |
