QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#533474#5088. Two ChoreographiesJanganLupaDaftarArkavidia#WA 74ms53716kbC++176.8kb2024-08-25 23:53:432024-08-25 23:53:44

Judging History

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

  • [2024-08-25 23:53:44]
  • 评测
  • 测评结果:WA
  • 用时:74ms
  • 内存:53716kb
  • [2024-08-25 23:53:43]
  • 提交

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 = 1e5+5;

// time DFS process LCA
const int LOG = 20;
vector<int> adj[maxn];
int lift[maxn][LOG];
int par[maxn] = {};
bool vis[maxn] = {};
int depth[maxn] = {};
int starttime[maxn];
int endtime[maxn];
int timer[2*maxn];
int TIME = 0;

void dfs(int node, int prev = 1){
    par[node] = prev;
    vis[node] = 1;
    depth[node] = depth[prev] + 1;
    lift[node][0] = prev;
    timer[node] = TIME;
    starttime[node] = TIME++;
    for(int i=1;i<LOG;i++)
        lift[node][i] = lift[lift[node][i - 1]][i - 1];
    for(auto nxt:adj[node]) {
        if (vis[nxt]) continue;
        dfs(nxt, node);
    }
    timer[node] = TIME;
    endtime[node] = TIME++;
}

bool isancestor(int a, int b){
    return starttime[a] <= starttime[b] && endtime[a] >= endtime[b];
}

int binlift(int a, int k) {
    for (int i=0;i<LOG;i++) {
        if(k & (1 << i)) {
            a = lift[a][i];
        }
    }
    return a;
}

int lca(int a, int b){
    if(isancestor(a, b))return a;
    if(isancestor(b, a))return b;
    for (int i=LOG-1;i>=0;i--) {
        if(!isancestor(lift[a][i], b)) a = lift[a][i];
    }
    return lift[a][0];
}

int dist(int a, int b){ // O(log(n))
    return depth[a] + depth[b] - 2*depth[lca(a,b)];
}


int32_t main() {
    fastIO

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

    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);
    }

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

    vpii back_edges;
    vector<int> radj[n + 1];
    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);
            radj[e.first].push_back(e.second);
        }
    }

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

        vi path1, path2;
        int _lca = lca(u, v);
        while (u != _lca) {
            path1.push_back(u);
            u = par[u];
        }
        reversevec(path1);

        path2.push_back(v);
        while (v != u) {
            v = par[v];
            path2.push_back(v);
        }

        vi cycle;
        fors(x, path1) {
            cycle.push_back(x);
        }
        fors(x, path2) {
            cycle.push_back(x);
        }

        if (point != 0) {
            cycle.push_back(point);
        }
        
        return cycle;
    };

    vi ans1;
    vi ans2;
    map<int, vector<pair<pii, int>>> cycle_size;
    fors(e, back_edges) {
        int len = dist(e.first, e.second) + 1;
        cycle_size[len].push_back(mp(e, 0));

        if (cycle_size[len].size() == 2) {
            ans1 = get_back_edge_cycle(cycle_size[len][0].first, cycle_size[len][0].second);
            ans2 = get_back_edge_cycle(cycle_size[len][1].first, cycle_size[len][1].second);
        }
        if (!ans1.empty()) {
            break;
        }
    }

    range(i,1,n + 1) {
        int rsz = radj[i].size();
        range(u,0,rsz) {
            range(v,u + 1, rsz) {
                int uu = radj[i][u];
                int vv = radj[i][v];
                int len = dist(uu, vv) + 2;
                cycle_size[len].push_back(mp(mp(uu, vv), i));

                if (cycle_size[len].size() == 2) {
                    ans1 = get_back_edge_cycle(cycle_size[len][0].first, cycle_size[len][0].second);
                    ans2 = get_back_edge_cycle(cycle_size[len][1].first, cycle_size[len][1].second);
                }
                if (!ans1.empty()) {
                    break;
                }
            }
            if (!ans1.empty()) {
                break;
            }
        }
        if (!ans1.empty()) {
            break;
        }
    }

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


    return 0;
}









详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 8940kb

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: 2ms
memory: 8032kb

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: 11892kb

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:

5
3 6 5 2 1 
4 3 6 5 2 

result:

ok 

Test #4:

score: 0
Accepted
time: 1ms
memory: 6316kb

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:

4
4 2 16 1 
27 7 11 5 

result:

ok 

Test #5:

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

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:

23
121 36 106 11 175 123 158 25 35 163 176 119 109 48 50 82 95 97 153 31 34 39 7 
196 94 84 118 92 76 146 69 67 183 101 62 28 37 44 122 78 83 38 98 126 55 13 

result:

ok 

Test #6:

score: 0
Accepted
time: 5ms
memory: 11372kb

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:

614
7808 3307 6445 3284 7417 3677 7239 6183 2267 850 4887 6905 6539 7558 6593 1346 942 3792 5865 1940 3900 4758 4481 7974 7627 4721 5353 1766 5475 4445 5530 5763 5882 6699 4462 3350 3771 3875 7536 1957 4818 2946 3644 5564 2409 4299 2477 1172 1137 1036 3222 4063 4174 5817 1751 4030 597 7629 7661 4477...

result:

ok 

Test #7:

score: 0
Accepted
time: 64ms
memory: 40648kb

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:

4045
45364 8612 10269 39077 56838 11547 740 81325 24242 76373 71235 24822 21917 7383 48688 81029 44860 67365 35971 1987 15985 25682 79688 10709 28444 10769 41646 70805 25352 42720 4276 517 50484 19572 61947 40414 58270 58576 71065 22774 40113 73621 49715 19198 28375 39274 84149 17319 32101 34546 489...

result:

ok 

Test #8:

score: 0
Accepted
time: 74ms
memory: 40172kb

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:

10016
96049 82673 97040 43188 14753 14691 67307 28577 74085 75932 58049 80427 11065 39988 73440 84148 39999 68868 24880 81463 79785 69618 63600 16992 5035 42626 15182 53670 94450 35922 92976 40994 70927 80444 72714 39346 99773 30381 80285 72865 56578 33585 90052 83148 22299 55782 74351 72935 33119 1...

result:

ok 

Test #9:

score: 0
Accepted
time: 1ms
memory: 6576kb

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:

4
4 3 2 1 
5 4 3 7 

result:

ok 

Test #10:

score: 0
Accepted
time: 68ms
memory: 53716kb

input:

100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 5...

output:

11
11 10 9 8 7 6 5 4 3 2 1 
99996 99995 99994 99993 99992 99991 99990 99989 99988 99987 100000 

result:

ok 

Test #11:

score: 0
Accepted
time: 2ms
memory: 11472kb

input:

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

output:

4
4 3 2 1 
6 5 4 8 

result:

ok 

Test #12:

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

input:

9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
1 3
1 4
9 5
9 4
1 7
9 2
1 9

output:

3
3 2 1 
5 4 9 

result:

ok 

Test #13:

score: 0
Accepted
time: 2ms
memory: 11916kb

input:

10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 8
1 4
10 6
1 6
10 4
10 3
1 9
10 1

output:

4
4 3 2 1 
8 7 6 10 

result:

ok 

Test #14:

score: 0
Accepted
time: 3ms
memory: 11860kb

input:

1000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
...

output:

4
4 3 2 1 
994 993 992 1000 

result:

ok 

Test #15:

score: 0
Accepted
time: 8ms
memory: 12100kb

input:

9999
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
...

output:

3
9999 9998 9997 
9997 9996 9999 

result:

ok 

Test #16:

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

input:

10000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53...

output:

4
4 3 2 1 
9998 9997 9996 10000 

result:

ok 

Test #17:

score: 0
Accepted
time: 59ms
memory: 51852kb

input:

94753
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53...

output:

3
3 2 1 
94748 94747 94753 

result:

ok 

Test #18:

score: 0
Accepted
time: 64ms
memory: 53572kb

input:

99999
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53...

output:

3
3 2 1 
99996 99995 99999 

result:

ok 

Test #19:

score: -100
Wrong Answer
time: 1ms
memory: 6356kb

input:

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

output:

-1

result:

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