Task: | Connect cities |
Sender: | joaquimballester |
Submission time: | 2024-09-05 17:19:04 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | WRONG ANSWER | 0.00 s | details |
#2 | WRONG ANSWER | 0.00 s | details |
#3 | WRONG ANSWER | 0.00 s | details |
#4 | WRONG ANSWER | 0.00 s | details |
#5 | WRONG ANSWER | 0.00 s | details |
#6 | TIME LIMIT EXCEEDED | -- | details |
#7 | TIME LIMIT EXCEEDED | -- | details |
#8 | TIME LIMIT EXCEEDED | -- | details |
#9 | TIME LIMIT EXCEEDED | -- | details |
#10 | TIME LIMIT EXCEEDED | -- | details |
#11 | TIME LIMIT EXCEEDED | -- | details |
#12 | WRONG ANSWER | 0.00 s | details |
Code
#include<iostream>#include<vector>#include<queue>using namespace std;int not_visited(const vector<bool> & visited){int n = visited.size();for(int i = 0;i < n; ++i){if(visited[i] == false)return i;}return -1;}void dfs(int s,vector<int> adj[],vector<bool> & visited, vector<pair<int,int>> &new_roads,int vist, int N ) {//if (visited[s]) return;if(visited[s] == true and vist == N) return;else if(visited[s] == true){visited[s] = true;int u = not_visited(visited);if(u == -1) return;new_roads.push_back({s,u});dfs(u,adj,visited,new_roads,vist,N);return;}else{++vist;visited[s] = true;/*cout<<"----------------------"<<endl;cout<<new_roads.size()<<endl;for(auto p: new_roads)cout<<p.first<<" "<<p.second<<endl;cout<<"----------------------"<<endl;*/if(adj[s].size()==0){int u = not_visited(visited);if(u == -1) return;new_roads.push_back({s,u});dfs(u,adj,visited,new_roads,vist,N);return;}// process node selse{for (auto u: adj[s]) {dfs(u,adj,visited,new_roads,vist,N);}}}}int main(){int n, m;cin >> n >> m;vector<int> adj[n];vector<bool> visited(n);int vist = 0;vector<pair<int,int>> new_roads;for(int i = 0; i < m; ++i){int a,b;cin >> a >> b;--a;--b;adj[a].push_back(b);adj[b].push_back(a);}int act = 0;dfs(act,adj,visited,new_roads,vist,n);cout<<new_roads.size()<<endl;for(auto p: new_roads)cout<<p.first+1<<" "<<p.second+1<<endl;}
Test details
Test 1
Verdict: WRONG ANSWER
input |
---|
10 10 2 5 5 6 1 4 6 8 ... |
correct output |
---|
2 1 2 2 7 |
user output |
---|
6 1 2 2 3 5 7 7 8 ... |
Test 2
Verdict: WRONG ANSWER
input |
---|
10 10 3 9 6 8 9 10 7 8 ... |
correct output |
---|
2 1 4 4 5 |
user output |
---|
4 9 2 8 4 4 5 5 10 |
Test 3
Verdict: WRONG ANSWER
input |
---|
10 10 7 9 1 7 1 3 3 4 ... |
correct output |
---|
0 |
user output |
---|
6 7 2 9 3 1 4 3 5 ... |
Test 4
Verdict: WRONG ANSWER
input |
---|
10 10 4 8 5 9 4 9 2 7 ... |
correct output |
---|
1 1 3 |
user output |
---|
5 5 2 2 3 3 4 4 6 ... |
Test 5
Verdict: WRONG ANSWER
input |
---|
10 10 4 9 2 4 7 10 1 8 ... |
correct output |
---|
0 |
user output |
---|
4 1 2 4 3 4 5 1 6 |
Test 6
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 200000 7233 22146 94937 96203 6133 10731 98737 99193 ... |
correct output |
---|
4785 1 2 2 3 3 4 4 5 ... |
user output |
---|
(empty) |
Test 7
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 200000 92950 93575 24401 88897 41796 99364 47106 50330 ... |
correct output |
---|
4868 1 2 2 7 7 9 9 15 ... |
user output |
---|
(empty) |
Test 8
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 200000 15637 76736 79169 98809 4382 86557 73383 77029 ... |
correct output |
---|
4683 1 9 9 20 20 27 27 28 ... |
user output |
---|
(empty) |
Test 9
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 200000 47932 66981 86401 99942 4353 27841 60492 67345 ... |
correct output |
---|
4807 1 6 6 7 7 11 11 12 ... |
user output |
---|
(empty) |
Test 10
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 200000 6554 44548 76413 98555 5447 59589 70166 74434 ... |
correct output |
---|
4786 1 2 2 18 18 21 21 27 ... |
user output |
---|
(empty) |
Test 11
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 1 1 2 |
correct output |
---|
99998 1 3 3 4 4 5 5 6 ... |
user output |
---|
(empty) |
Test 12
Verdict: WRONG ANSWER
input |
---|
10 9 2 5 5 6 1 4 6 8 ... |
correct output |
---|
2 1 2 2 7 |
user output |
---|
6 1 2 2 3 5 7 7 8 ... |