7540 | 2024. 01. 09 13:45:42 | adam | Elágazás nélküli úton levő települések (50 pont) | cpp17 | Futási hiba 33/50 | 86ms | 63132 KiB |
#include <bits/stdc++.h>
using namespace std;
int main()
{
int village_count = 0;
int road_count = 0;
cin >> village_count;
cin >> road_count;
vector<vector<int>> village_tree(village_count, vector<int>(0, 0));
for (int i = 0; i < road_count; i++)
{
int village_id = 0;
int village_to = 0;
cin >> village_id;
cin >> village_to;
village_tree[village_id - 1].push_back(village_to - 1);
village_tree[village_to - 1].push_back(village_id - 1);
}
vector<int> accessible(0, 0);
for (int i = 0; i < village_count; i++)
{
if (village_tree[i].size() != 1)
continue;
bool ended = false;
int previous = i;
int check = village_tree[i][0];
while (!ended)
{
accessible.push_back(check);
if (village_tree[check].size() > 2)
{
ended = true;
}
else
{
if (village_tree[check].size() == 1)
ended = true;
else if (village_tree[check][0] == previous)
check = village_tree[check][1];
else
check = village_tree[check][0];
previous = check;
}
}
}
sort(accessible.begin(), accessible.end());
vector<int> accessible2;
accessible2.push_back(accessible[0]);
for (int i = 1; i < accessible.size(); i++) {
if (accessible[i-1] != accessible[i])
accessible2.push_back(accessible[i]);
}
cout << accessible2.size() << "\n";
for (int v : accessible2)
{
cout << v+1 << " ";
}
cout << "\n";
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 33/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1808 KiB | |||
2 | Elfogadva | 0/0 | 28ms | 3928 KiB | |||
3 | Elfogadva | 2/2 | 3ms | 2276 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2424 KiB | |||
5 | Futási hiba | 0/2 | 3ms | 2772 KiB | |||
6 | Elfogadva | 2/2 | 3ms | 3084 KiB | |||
7 | Elfogadva | 2/2 | 3ms | 3080 KiB | |||
8 | Elfogadva | 2/2 | 4ms | 3240 KiB | |||
9 | Elfogadva | 2/2 | 7ms | 3576 KiB | |||
10 | Elfogadva | 2/2 | 8ms | 3952 KiB | |||
11 | Elfogadva | 2/2 | 14ms | 4336 KiB | |||
12 | Elfogadva | 2/2 | 16ms | 4584 KiB | |||
13 | Hibás válasz | 0/3 | 4ms | 3644 KiB | |||
14 | Futási hiba | 0/3 | 86ms | 63132 KiB | |||
15 | Hibás válasz | 0/3 | 6ms | 4364 KiB | |||
16 | Futási hiba | 0/3 | 86ms | 62912 KiB | |||
17 | Hibás válasz | 0/3 | 14ms | 5004 KiB | |||
18 | Elfogadva | 3/3 | 14ms | 4900 KiB | |||
19 | Elfogadva | 3/3 | 17ms | 5352 KiB | |||
20 | Elfogadva | 3/3 | 28ms | 5808 KiB | |||
21 | Elfogadva | 3/3 | 28ms | 6080 KiB | |||
22 | Elfogadva | 3/3 | 29ms | 6080 KiB |