QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#533438 | #5088. Two Choreographies | JanganLupaDaftarArkavidia# | WA | 82ms | 22700kb | C++17 | 5.0kb | 2024-08-25 23:19:26 | 2024-08-25 23:19:26 |
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.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: 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]