QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#506497 | #1190. Twin Trees Bros | arnold518# | WA | 1ms | 4124kb | C++17 | 4.6kb | 2024-08-05 18:13:52 | 2024-08-05 18:13:53 |
Judging History
answer
#include <bits/stdc++.h>
#define ff first
#define ss second;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
struct Point
{
ll x, y, z;
};
Point operator + (const Point &p, const Point &q) { return {p.x+q.x, p.y+q.y, p.z+q.z}; }
Point operator - (const Point &p, const Point &q) { return {p.x-q.x, p.y-q.y, p.z-q.z}; }
ll operator * (const Point &p, const Point &q) { return p.x*q.x+p.y*q.y+p.z*q.z; }
Point operator / (const Point &p, const Point &q) { return Point{p.y*q.z-p.z*q.y, p.z*q.x-p.x*q.z, p.x*q.y-p.y*q.x}; }
ll mag(const Point &p) { return p*p; }
const int MAXN = 200;
struct Frac
{
ll u, d;
bool operator == (Frac ot) { return u*ot.d == ot.u*d; }
};
int N;
struct Tree
{
Point A[MAXN+10];
pii E[MAXN+10];
vector<int> adj[MAXN+10];
vector<int> cen;
void input()
{
for(int i=1; i<=N; i++) scanf("%lld%lld%lld", &A[i].x, &A[i].y, &A[i].z);
for(int i=1; i<N; i++)
{
scanf("%d%d", &E[i].first, &E[i].second);
if(E[i].first>N) E[i].first-=N;
if(E[i].second>N) E[i].second-=N;
if(E[i].first>E[i].second) swap(E[i].first, E[i].second);
adj[E[i].first].push_back(E[i].second);
adj[E[i].second].push_back(E[i].first);
}
getsz(1, 1);
int c=getcen(1, 1);
getsz(c, c);
cen.push_back(c);
for(auto nxt : adj[c]) if(sz[nxt]*2==N) cen.push_back(nxt);
sort(E+1, E+N);
}
int sz[MAXN+10];
void getsz(int now, int bef)
{
sz[now]=1;
for(int nxt : adj[now])
{
if(nxt==bef) continue;
getsz(nxt, now);
sz[now]+=sz[nxt];
}
}
int getcen(int now, int bef)
{
for(int nxt : adj[now])
{
if(nxt==bef) continue;
if(sz[nxt]>N/2) return getcen(nxt, now);
}
return now;
}
void translate(int now)
{
Point p=A[now];
for(int i=1; i<=N; i++) A[i]=A[i]-p;
}
vector<array<ll, 5>> f(int pp, int qq)
{
Point p=A[pp], q=A[qq];
vector<array<ll, 5>> ret;
for(int i=1; i<=N; i++)
{
Point r=A[i];
ll t=(p/q)*r;
ret.push_back(array<ll, 5>{r*p, r*q, r*r, (t>0)-(t<0), i});
}
sort(ret.begin(), ret.end());
return ret;
}
}A, B;
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
scanf("%d", &N);
A.input();
B.input();
int ans=0;
for(auto ca : A.cen) for(auto cb : B.cen)
{
A.translate(ca);
B.translate(cb);
int pa, qa=-1;
if(ca==1) pa=2;
else pa=1;
for(int i=1; i<=N; i++)
{
if(i==ca || i==pa) continue;
Point p=A.A[i]/A.A[pa];
if(p.x!=0 || p.y!=0 || p.z!=0)
{
qa=i;
break;
}
}
if(qa==-1) qa=pa;
// printf("%d %d %d\n", ca, pa, qa);
for(int pb=1; pb<=N; pb++)
{
if(pb==cb) continue;
Frac K = Frac{mag(A.A[pa]), mag(B.A[pb])};
for(int qb=1; qb<=N; qb++)
{
if(qb==cb || (pa!=qa && qb==pb)) continue;
if(!(K==Frac{mag(A.A[qa]), mag(B.A[qb])})) continue;
if(!(K==Frac{A.A[pa]*A.A[qa], B.A[pb]*B.A[qb]})) continue;
// printf("%d %d %d / %d %d %d\n", ca, pa, qa, cb, pb, qb);
auto VA=A.f(pa, qa), VB=B.f(pb, qb);
bool flag=true;
vector<int> P(N+1);
for(int i=0; i<N; i++)
{
// for(int j=0; j<5; j++) printf("%lld ", VA[i][j]); printf(" : A %d\n", i);
// for(int j=0; j<5; j++) printf("%lld ", VB[i][j]); printf(" : B %d\n", i);
for(int j=0; j<3; j++) if(!(K==Frac{VA[i][j], VB[i][j]})) flag=false;
if(VA[i][3]!=VB[i][3]) flag=false;
P[VA[i][4]]=VB[i][4];
}
if(flag)
{
for(int i=1; i<N; i++)
{
auto [u, v] = A.E[i];
int u2=P[u], v2=P[v];
if(u2>v2) swap(u2, v2);
if(!binary_search(B.E, B.E+N, pii{u2, v2})) flag=false;
}
if(flag) ans++;
}
}
}
}
printf("%d\n", ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4124kb
input:
3 0 0 0 1 0 0 3 0 0 1 2 2 3 0 0 0 0 2 2 0 3 3 4 5 5 6
output:
1
result:
ok answer is '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4076kb
input:
4 1 0 0 2 0 0 2 1 0 2 -1 0 1 2 2 3 2 4 0 1 1 0 0 0 0 2 0 0 0 2 5 6 5 7 5 8
output:
2
result:
ok answer is '2'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
3 0 0 0 1 0 0 3 0 0 1 2 2 3 0 0 0 0 2 2 0 3 3 4 5 5 6
output:
1
result:
ok answer is '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
7 5 3 1 5 5 3 5 1 -1 7 5 3 3 5 3 7 1 -1 3 1 -1 1 2 1 3 1 4 1 5 1 6 1 7 13 23 24 10 20 30 10 20 36 10 20 24 13 23 36 7 17 36 7 17 24 8 9 9 10 9 11 9 12 9 13 9 14
output:
4
result:
ok answer is '4'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
7 5 3 1 5 5 3 5 1 -1 7 5 3 3 5 3 7 1 -1 3 1 -1 1 2 1 3 1 4 1 5 1 6 1 7 13 23 24 13 23 36 10 20 30 10 20 36 10 20 24 7 17 36 7 17 24 8 9 9 10 10 11 10 12 10 13 10 14
output:
0
result:
ok answer is '0'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
7 5 3 1 5 5 3 5 1 -1 7 5 3 3 5 3 7 1 -1 3 1 -1 1 2 1 3 1 4 1 5 1 6 1 7 13 23 24 10 20 30 10 20 36 10 20 24 13 23 37 7 17 36 7 17 24 8 9 9 10 9 11 9 12 9 13 9 14
output:
0
result:
ok answer is '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
9 134 234 164 185 285 198 134 234 232 185 285 266 134 234 300 185 285 334 134 234 368 185 285 402 134 234 436 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 50 30 278 184 164 680 -84 -104 680 318 298 278 -218 -238 278 452 432 680 -352 -372 680 586 566 278 -486 -506 278 10 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18
output:
2
result:
ok answer is '2'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
9 185 285 198 134 234 436 185 285 266 185 285 402 134 234 232 134 234 300 134 234 368 134 234 164 185 285 334 1 8 1 5 2 4 3 5 3 6 4 7 6 9 7 9 318 298 278 452 432 680 184 164 680 -218 -238 278 -352 -372 680 586 566 278 -486 -506 278 -84 -104 680 50 30 278 10 12 10 11 11 15 12 18 13 17 13 14 14 16 17 18
output:
2
result:
ok answer is '2'
Test #9:
score: 0
Accepted
time: 0ms
memory: 4108kb
input:
9 185 285 198 134 234 436 185 285 266 185 285 402 134 234 232 134 234 300 134 234 368 134 234 164 185 285 334 1 8 1 5 2 6 3 5 3 6 4 7 6 9 7 9 318 298 278 452 432 680 184 164 680 -218 -238 278 -352 -372 680 586 566 278 -486 -506 278 -84 -104 680 50 30 278 10 12 10 11 11 15 12 18 13 17 13 14 14 16 17 18
output:
0
result:
ok answer is '0'
Test #10:
score: 0
Accepted
time: 0ms
memory: 4104kb
input:
9 185 285 198 134 235 436 185 285 266 185 285 402 134 234 232 134 234 300 134 234 368 134 234 164 185 285 334 1 8 1 5 2 4 3 5 3 6 4 7 6 9 7 9 318 298 278 452 432 680 184 164 680 -218 -238 278 -352 -372 680 586 566 278 -486 -506 278 -84 -104 680 50 30 278 10 12 10 11 11 15 12 18 13 17 13 14 14 16 17 18
output:
0
result:
ok answer is '0'
Test #11:
score: 0
Accepted
time: 0ms
memory: 4108kb
input:
7 -220 520 720 60 240 440 200 100 300 620 -320 -120 -80 380 580 480 -180 20 340 -40 160 1 3 1 7 1 6 1 4 2 3 3 5 230 210 370 50 30 10 170 150 250 -10 -30 -110 -130 -150 -350 110 90 130 -70 -90 -230 8 11 8 9 8 14 8 12 9 10 9 13
output:
1
result:
ok answer is '1'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
7 -220 520 720 60 240 440 200 100 300 620 -320 -120 -80 380 580 480 -180 20 340 -40 160 1 3 1 7 1 6 2 3 3 5 4 5 230 210 370 50 30 10 170 150 250 -10 -30 -110 -130 -150 -350 110 90 130 -70 -90 -230 8 11 8 9 8 14 8 12 9 10 9 13
output:
0
result:
ok answer is '0'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
7 -220 520 720 60 240 440 200 100 300 620 -320 -120 -80 380 580 480 -180 20 341 -40 161 1 3 1 7 1 6 1 4 2 3 3 5 230 210 370 50 30 10 170 150 250 -10 -30 -110 -130 -150 -350 110 90 130 -70 -90 -230 8 11 8 9 8 14 8 12 9 10 9 13
output:
0
result:
ok answer is '0'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
12 -356 -256 92 -356 -256 -12 -356 -256 612 -252 -152 612 -252 -152 508 -252 -152 92 -356 -256 508 -252 -152 196 -252 -152 -12 -252 -152 404 -356 -256 404 -356 -256 196 1 4 2 4 3 11 4 5 4 12 5 11 6 12 7 11 8 12 9 12 10 11 602 582 194 234 214 562 418 398 562 -134 -154 562 234 214 194 -134 -154 194 -3...
output:
1
result:
ok answer is '1'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
12 -356 -256 92 -356 -256 -12 -356 -256 612 -252 -152 612 -252 -152 508 -252 -152 92 -356 -256 508 -252 -152 196 -252 -152 -12 -252 -152 404 -356 -256 404 -356 -256 196 1 4 2 4 3 11 4 5 4 12 5 11 6 7 7 11 8 12 9 12 10 11 602 582 194 234 214 562 418 398 562 -134 -154 562 234 214 194 -134 -154 194 -31...
output:
0
result:
ok answer is '0'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
12 -356 -256 92 -356 -256 -12 -356 -256 612 -252 -152 612 -252 -152 508 -252 -152 93 -356 -256 508 -252 -152 196 -252 -152 -12 -252 -152 404 -356 -256 404 -356 -256 196 1 4 2 4 3 11 4 5 4 12 5 11 6 12 7 11 8 12 9 12 10 11 418 398 562 -502 -522 562 -134 -154 194 234 214 562 -502 -522 194 602 582 562 ...
output:
0
result:
ok answer is '0'
Test #17:
score: -100
Wrong Answer
time: 0ms
memory: 3916kb
input:
4 -500 -400 360 -500 -400 240 100 200 240 100 200 360 1 2 2 4 3 4 890 114 94 -790 114 94 890 -54 -74 -790 -54 -74 5 8 5 7 6 8
output:
4
result:
wrong answer expected '2', found '4'