QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#506497#1190. Twin Trees Brosarnold518#WA 1ms4124kbC++174.6kb2024-08-05 18:13:522024-08-05 18:13:53

Judging History

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

  • [2024-08-05 18:13:53]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4124kb
  • [2024-08-05 18:13:52]
  • 提交

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'