QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #827810 | #9911. 路南柯 | Hanghang | 100 ✓ | 12ms | 3640kb | C++20 | 951b | 2024-12-23 10:14:48 | 2024-12-23 10:14:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=103;
int n,m,tim,a[N][N];
bool ban[N];
vector<int>ve[N],leaf[N];
void Leaf(int x)
{
reverse(leaf[x].begin(),leaf[x].end());
for(int v:leaf[x])a[m][++tim]=v;
}
void Dfs(int x,int fa)
{
a[m][++tim]=x;Leaf(x);
for(int y:ve[x])if(!ban[y]&&y!=fa)Dfs(y,x);
}
void Solve()
{
cin>>n;m=0;
for(int i=1;i<=n;i++)ban[i]=0,leaf[i].clear(),ve[i].clear();
for(int i=1,x,y;i<n;i++)cin>>x>>y,ve[x].push_back(y),ve[y].push_back(x);
for(int i=1;i<=n;i++)if(ve[i].size()==1)ban[i]=1;
for(int i=1;i<=n;i++)if(!ban[i])for(int j:ve[i])if(ban[j])leaf[i].push_back(j);
for(int i=1;i<=n;i++)if(!ban[i]&&ve[i].size()-leaf[i].size()==1)m++,tim=0,Dfs(i,0);
cout<<m<<endl;
for(int i=1;i<=m;i++,cout<<endl)for(int j=n;j;j--)cout<<a[i][j]<<" ";
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T;cin>>T;
while(T--)Solve();
return 0;
}
詳細信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 1ms
memory: 3612kb
input:
10 10 4 2 5 1 8 6 1 9 3 7 1 8 10 2 6 4 3 4 10 4 3 3 1 5 3 6 3 2 3 8 7 8 2 7 10 8 9 10 5 4 10 8 10 3 6 3 9 8 1 10 4 2 2 7 8 4 10 10 6 6 8 1 7 2 6 3 5 3 9 4 2 6 9 3 1 10 2 8 10 4 9 1 9 3 5 7 6 3 1 8 8 7 4 2 10 9 2 9 1 7 1 5 6 8 2 3 9 5 10 5 4 1 10 10 2 9 8 1 8 5 6 3 7 1 6 2 9 8 2 10 4 2 10 5 7 6 2 8 7...
output:
3 7 3 10 2 4 6 8 5 9 1 7 3 9 5 1 8 6 4 10 2 5 9 1 8 6 10 2 4 7 3 2 10 7 9 8 2 4 1 5 6 3 6 5 1 4 3 2 9 8 10 7 2 6 3 1 10 9 8 5 4 7 2 7 2 5 4 9 8 1 10 6 3 2 4 2 10 8 6 9 5 3 7 1 7 1 5 3 9 8 10 6 4 2 3 5 7 10 4 2 8 1 9 6 3 5 7 6 3 9 1 8 2 10 4 6 3 9 1 10 4 2 8 5 7 2 6 4 5 10 7 1 3 9 8 2 8 ...
result:
ok Answer correct!
Subtask #2:
score: 80
Accepted
Test #2:
score: 80
Accepted
time: 12ms
memory: 3640kb
input:
100 100 90 19 79 98 23 34 50 41 31 52 61 19 50 30 49 5 95 65 22 44 72 89 49 77 27 7 48 2 28 25 56 12 97 63 98 43 10 4 50 33 12 13 54 16 100 43 23 69 53 5 56 85 39 6 64 92 100 59 2 71 44 29 59 97 64 39 75 53 59 89 16 35 67 16 6 43 38 51 36 22 58 70 3 29 9 61 99 11 49 95 27 72 73 89 23 3 14 3 61 57 26...
output:
15 17 36 1 13 12 85 56 96 74 32 18 11 99 55 58 8 70 86 46 83 30 41 50 33 81 21 80 87 15 82 57 9 61 19 90 63 62 97 31 52 71 2 48 54 67 78 16 35 93 20 26 76 91 88 40 37 84 92 64 66 39 24 6 47 45 79 98 43 100 59 7 27 72 89 42 73 69 34 60 23 14 3 29 68 44 22 51 38 65 95 94 28 25 77 49 5 53 75 10 4 8 58...
result:
ok Answer correct!