QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#533438#5088. Two ChoreographiesJanganLupaDaftarArkavidia#WA 82ms22700kbC++175.0kb2024-08-25 23:19:262024-08-25 23:19:26

Judging History

你现在查看的是最新测评结果

  • [2024-08-25 23:19:26]
  • 评测
  • 测评结果:WA
  • 用时:82ms
  • 内存:22700kb
  • [2024-08-25 23:19:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

// Define Template          Python++
// Data Structure and Algorithm
#pragma region
#define all(vec)            (vec).begin(),(vec).end()
#define sortvec(vec)        sort(all(vec));
#define minvec(vec)         *min_element(all(vec))
#define maxvec(vec)         *max_element(all(vec))
#define uma(var,val)        var=max(var,(val));
#define umi(var,val)        var=min(var,(val));
#define sumvec(vec)         accumulate(all(vec),0LL)
#define reversevec(vec)     reverse(all(vec));
#define range(i,s,e)        for(int i=s;i<e;i++)
#define range2(i,s,e)       for(int i=s;i>=e;i--)
#define fors(var,arr)       for(auto &var:arr)
// Input Output Manage
#define debug(x)            cout<<(#x)<<" : "<<(x)<<endl;
#define test                cout<<"test"<<endl;
#define fastIO              ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define floatprecision      cout<<fixed<<setprecision(6);
#define fileread            freopen("input.txt","r",stdin);
#define fileout             freopen("output.txt","w",stdout);
#define query               cin>>QUERY;while(QUERY--)
#define inputvec(vec,am)    vector<int> vec(am);fors(num,vec)cin>>num;
#define inputmat(mat,n,m)   vector<vector<int>> mat(n, vector<int>(m, 0));range(i,0,n)range(j,0,m)cin>>mat[i][j];
#define input(var)          int var;cin>>var;
#define input2(a,b)         int a,b;cin>>a>>b;
#define inputp(var)         pair<int,int> var;cin>>var.first>>var.second;
#define inputs(var)         string var;cin>>var;
#define print(var)          cout<<(var)<<endl;
#define prints(var)         cout<<(var)<<" ";
#define print2(var1,var2)   cout<<(var1)<<" "<<(var2)<<endl;
#define printp(paired)      cout<<(paired.first)<<" "<<(paired.second)<<endl;
#define printyes(cond)      cout<<((cond)?"YES":"NO")<<endl;
#define printarr(arr)       fors(num,arr){cout<<num<<" ";};cout<<endl;
#define endline             cout<<endl;
#pragma endregion
// Macro
#pragma region
#define ll    long long
#define pb    push_back
#define pq    priority_queue
#define mp    make_pair
#define vi    vector<int>
#define pii   pair<int,int>
#define vpii  vector<pii>
#define vvi   vector<vector<int>>
#define mii   map<int,int>
// Oneliner Function
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll sigma(ll num){return num*(num+1)/2;}
ll gcd(ll a, ll b){return (a==0?b:gcd(b%a,a));}
ll lcm(ll a, ll b){return (a*b)/gcd(a,b);}
ll binpow(ll a,ll b,ll m=INT64_MAX){ll r=1;a%=m;while(b){if(b&1)r=(r*a)%m;a=(a*a)%m;b>>=1;}return r;}
ll invmod(ll a,ll m){return gcd(a,m)==1?binpow(a,m-2,m):0;}
ll random(ll l){return rng()%(l+1);}
ll random(ll a,ll b){ll w=b-a;return a+random(w);}
#pragma endregion
// More Macro
#pragma region
#define i32   int32_t
#define int   long long
#define float long double
int QUERY;
#pragma endregion
// Constant
const int MOD = 1e9+7;
const int MOD2 = 998244353;
const long long INF = 1e18;
const int maxn = 2e5+5;



int32_t main() {
    fastIO

    input(n)
    int m = 2 * n - 3;

    vector<int> adj[n + 1];
    vpii edges(m);
    range(i,0,m) {
        input2(u, v)
        adj[u].push_back(v);
        adj[v].push_back(u);

        edges[i] = mp(u, v);
    }

    int depth[n + 1] = {};
    int par[n + 1] = {};
    bool vis[n + 1] = {};
    function<void(int, int)> dfs = [&](int node, int prev) {
        vis[node] = true;
        depth[node] = depth[prev] + 1;
        par[node] = prev;
        for(int nxt:adj[node]) {
            if(vis[nxt]) continue;
            dfs(nxt, node);
        }
    };

    range(i,1,n + 1) {
        if (!vis[i]) {
            dfs(i, 0);
        }
    }

    vpii back_edges;
    range(i,0,m) {
        pii e = edges[i];
        int d1 = depth[e.first];
        int d2 = depth[e.second];
        if (d1 < d2) {
            swap(e.first, e.second);
        }

        if (par[e.first] != e.second) {
            back_edges.push_back(e);
        }
    }
    
    // printarr(depth)
    // fors(e, back_edges) {
    //     printp(e)
    // }

    map<int, vector<pii>> cycle_size;
    fors(e, back_edges) {
        int d1 = depth[e.first];
        int d2 = depth[e.second];
        int len = d1 - d2 + 1;
        cycle_size[len].push_back(e);
    }

    // fors(p, cycle_size) {
    //     print2("size", p.first)
    //     fors(e, p.second) {
    //         printp(e)
    //     }
    //     endline
    // }

    auto get_back_edge_cycle = [&](pii edge) {
        int v = edge.first;
        int u = edge.second;

        vi cycle;
        cycle.push_back(v);
        while (v != u) {
            v = par[v];
            cycle.push_back(v);
        }
        
        return cycle;
    };

    vi ans1;
    vi ans2;
    fors(p, cycle_size) {
        if (p.second.size() >= 2) {
            ans1 = get_back_edge_cycle(p.second[0]);
            ans2 = get_back_edge_cycle(p.second[1]);
            
            break;
        }
    }

    if (ans1.size() == 0) {
        print(-1)
    } else {
        print(ans1.size())
        printarr(ans1)
        printarr(ans2)
    }
    


    return 0;
}









Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3612kb

input:

4
1 2
1 3
1 4
2 3
2 4

output:

3
3 2 1 
4 2 1 

result:

ok 

Test #2:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

5
1 2
1 3
1 4
1 5
2 3
2 5
3 4

output:

3
3 2 1 
5 2 1 

result:

ok 

Test #3:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

7
1 2
3 4
5 6
5 2
3 1
6 1
4 2
4 5
2 6
3 6
1 5

output:

3
6 5 2 
5 2 1 

result:

ok 

Test #4:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

40
1 16
1 40
2 4
2 16
2 36
3 25
3 38
4 1
4 13
5 11
5 27
6 4
7 5
7 11
8 10
8 14
8 24
9 34
10 20
12 35
13 2
14 10
14 20
15 18
15 28
15 31
16 6
16 13
17 5
17 11
17 27
18 9
19 1
19 4
19 16
20 24
21 12
21 33
21 35
22 38
23 12
23 21
25 28
25 31
25 34
25 38
26 14
26 20
27 7
27 11
28 3
28 31
29 16
29 19
30 ...

output:

3
40 16 1 
7 11 5 

result:

ok 

Test #5:

score: 0
Accepted
time: 0ms
memory: 3708kb

input:

201
1 7
1 114
1 119
2 49
2 93
4 197
5 139
6 1
6 27
7 39
7 121
8 127
9 130
9 145
11 106
11 136
11 193
12 2
12 116
13 55
13 69
13 105
13 187
13 196
14 144
14 177
15 127
15 134
15 145
15 155
15 184
15 199
16 96
16 177
17 20
21 100
22 68
22 71
22 81
22 142
23 148
23 190
24 12
24 81
24 89
25 158
25 159
2...

output:

3
193 136 11 
142 68 22 

result:

ok 

Test #6:

score: 0
Accepted
time: 4ms
memory: 4776kb

input:

8000
2 1508
2 3068
3 5268
3 5501
6 266
6 2737
6 3197
6 5863
6 6697
7 3492
9 427
9 794
9 3114
9 5509
10 2257
10 4348
11 1479
11 1957
11 2230
11 2500
11 3182
11 4399
11 5051
11 7727
12 7669
13 1403
13 5753
14 2871
14 6956
14 7959
15 6902
17 1630
17 3155
17 5950
18 7232
19 125
19 3280
19 5648
20 6879
2...

output:

3
3179 869 3227 
6000 2997 3258 

result:

ok 

Test #7:

score: 0
Accepted
time: 82ms
memory: 22700kb

input:

99999
1 11261
1 21544
2 9017
2 63063
2 97990
3 11995
3 42473
4 19846
5 38099
6 35872
6 80509
7 73231
8 12356
9 35384
10 45091
12 86727
13 4938
13 48917
14 62383
14 89846
15 28458
15 44277
15 51725
15 84522
16 93258
17 13934
17 42238
18 19000
19 11278
19 23672
19 61502
19 78791
20 85057
20 88080
21 2...

output:

3
1826 34232 565 
57847 39488 2391 

result:

ok 

Test #8:

score: 0
Accepted
time: 60ms
memory: 22492kb

input:

100000
1 68531
2 97359
4 68578
4 83098
4 98443
5 8053
5 30270
5 86617
6 7074
6 12266
6 69396
7 52675
7 78316
7 90757
7 92242
8 32677
8 41353
8 41457
8 74508
9 44234
10 4973
10 38390
10 96049
11 28007
11 68620
13 3016
14 36748
15 8147
15 25110
15 28489
15 72947
15 99347
16 70760
17 12774
17 68407
17 ...

output:

3
26167 237 324 
6949 482 61142 

result:

ok 

Test #9:

score: -100
Wrong Answer
time: 0ms
memory: 3608kb

input:

7
1 2
2 3
3 4
4 5
5 6
6 7
7 5
1 4
7 3
1 6
7 1

output:

-1

result:

wrong answer Integer -1 violates the range [3, 7]