QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#533436 | #5088. Two Choreographies | JanganLupaDaftarArkavidia# | WA | 0ms | 3624kb | C++17 | 5.2kb | 2024-08-25 23:12:47 | 2024-08-25 23:12:47 |
Judging History
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;
}
详细
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.