QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#533474 | #5088. Two Choreographies | JanganLupaDaftarArkavidia# | WA | 74ms | 53716kb | C++17 | 6.8kb | 2024-08-25 23:53:43 | 2024-08-25 23:53:44 |
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 = 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;
}
Details
Tip: Click on the bar to expand more detailed information
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]