QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#533436#5088. Two ChoreographiesJanganLupaDaftarArkavidia#WA 0ms3624kbC++175.2kb2024-08-25 23:12:472024-08-25 23:12:47

Judging History

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

  • [2024-08-25 23:12:47]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3624kb
  • [2024-08-25 23:12:47]
  • 提交

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.first == 3 && !p.second.empty()) {
            ans1 = get_back_edge_cycle(p.second.back());
            ans2 = get_back_edge_cycle(p.second.back());
            swap(ans2[1], ans2[2]);

            break;
        }

        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: 0
Wrong Answer
time: 0ms
memory: 3624kb

input:

4
1 2
1 3
1 4
2 3
2 4

output:

3
4 2 1 
4 1 2 

result:

wrong answer Wrong output - Identical cycle.