QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#472886 | #8838. Jesse's Job | ivaziva | RE | 49ms | 6688kb | C++17 | 1.6kb | 2024-07-11 20:05:46 | 2024-07-11 20:05:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100010
long long n;
long long p[MAXN];
bool pos[MAXN];
vector<long long> nodes[MAXN];
long long brkomp;
void dfs(long long node)
{
pos[node]=true;
nodes[brkomp].push_back(node);
if (pos[p[node]]==false) dfs(p[node]);
}
int main()
{
long long t;cin>>t;
for (long long tt=0;tt<t;tt++)
{
cin>>n;
for (long long i=1;i<=n;i++) cin>>p[i];
brkomp=0;
for (long long i=1;i<=n;i++)
{
if (pos[i]) continue;
brkomp++;dfs(i);
}
if (brkomp>1)
{
cout<<n<<endl;
cout<<nodes[1].size()<<endl;
for (long long i=0;i<nodes[1].size();i++) cout<<nodes[1][i]<<" ";
cout<<endl;
for (long long i=1;i<=n;i++) pos[i]=false;
for (long long i=1;i<=brkomp;i++) nodes[i].clear();
continue;
}
cout<<n-2<<endl;
for (long long i=1;i<=n;i++) pos[i]=false;
long long tren;
for (long long i=1;i<=n;i++)
{
if (p[i]!=1) continue;
tren=i;break;
}
vector<long long> ans;
while (pos[tren]==false)
{
ans.push_back(tren);
pos[tren]=true;
if (p[tren]==1) tren=2;
else if (p[tren]==2) tren=1;
else tren=p[tren];
}
cout<<ans.size()<<endl;
for (long long i=0;i<ans.size();i++) cout<<ans[i]<<" ";
cout<<endl;
for (long long i=1;i<=n;i++) pos[i]=false;
nodes[1].clear();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6688kb
input:
3 2 2 1 4 2 1 4 3 6 3 5 4 2 6 1
output:
0 1 2 4 2 1 2 4 3 6 2 5
result:
ok Correct (3 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 5964kb
input:
872 6 1 5 2 6 3 4 6 5 2 1 3 4 6 4 2 1 3 4 6 2 3 1 4 5 6 6 4 5 1 6 2 3 6 6 2 3 1 4 5 5 2 1 3 4 5 6 1 2 6 4 3 5 4 2 1 4 3 6 1 6 4 2 5 3 6 6 1 3 5 4 2 6 2 1 4 5 6 3 6 3 4 1 5 6 2 6 4 1 5 3 2 6 6 5 2 1 6 3 4 6 4 1 6 2 5 3 6 5 1 3 6 2 4 6 6 2 5 4 3 1 6 6 2 5 3 1 4 6 5 2 4 1 3 6 6 6 1 3 2 4 5 6 2 3 4 6 5 ...
output:
6 1 1 6 4 1 5 4 3 4 2 1 2 6 3 1 2 3 6 4 1 4 6 3 6 4 1 6 5 4 5 2 1 2 6 1 1 4 2 1 2 6 1 1 6 3 1 6 2 6 2 1 2 6 2 1 3 6 5 1 4 3 5 2 6 3 1 5 3 6 3 1 4 2 6 3 1 5 2 6 2 1 6 6 5 1 6 4 3 5 6 4 1 5 3 4 6 5 1 6 5 4 2 6 5 1 2 3 4 6 6 5 1 5 3 2 6 6 2 1 4 4 4 6 2 3 5 6 2 1 3 6 1 1 6 1 1...
result:
ok Correct (872 test cases)
Test #3:
score: 0
Accepted
time: 49ms
memory: 5992kb
input:
46232 7 2 1 7 5 3 6 4 7 5 6 2 4 7 1 3 4 3 4 2 1 7 4 5 1 6 3 7 2 8 4 2 6 5 1 7 3 8 8 3 4 8 7 1 2 5 6 7 6 2 4 3 7 5 1 8 8 1 3 2 7 5 4 6 8 6 5 4 2 1 3 8 7 8 8 3 5 6 2 7 4 1 8 7 3 6 1 8 5 4 2 8 2 3 4 5 8 6 7 1 8 5 8 2 4 7 3 6 1 8 3 4 8 2 7 6 1 5 8 2 8 3 5 7 6 1 4 8 8 4 5 7 6 1 3 2 8 5 2 6 3 4 8 1 7 8 2 ...
output:
7 2 1 2 7 6 1 5 7 3 2 6 2 2 4 2 5 3 3 2 5 8 3 1 4 5 6 4 5 2 4 7 7 4 1 6 5 7 8 7 1 8 6 5 7 4 2 8 6 1 6 3 4 2 5 8 2 1 8 8 3 1 7 4 8 6 1 2 3 4 5 8 8 7 1 5 7 6 3 2 8 8 5 1 3 8 5 7 8 6 1 2 8 4 5 7 6 6 6 2 4 7 3 5 8 7 1 5 4 3 6 8 7 8 6 1 2 4 7 6 8 6 3 3 2 8 7 1 1 8 7 1 2 6 8 4 3 5 4 4...
result:
ok Correct (46232 test cases)
Test #4:
score: -100
Runtime Error
input:
1 999995 992870 210969 579550 405695 249895 436695 476463 929789 907510 311379 340877 491996 59204 996443 681309 483046 760005 905577 711115 275827 697004 450345 678866 276460 310113 542672 27 914370 232581 624905 590395 136666 628293 731656 670994 184745 662928 389422 848680 447853 325275 979617 82...