글 읽기 - 이 문제를 한 번 트리 표현 하고, LCA로 풀어볼려고 했는데요.

cokcjswo 7년 전 0

왜 계속 틀릴까요?

- 0번 노드는 맨바깥 캔버스 또한 하나의 노드로서 '루트로' 생각했습니다. (즉, 어느 노드에도 포함되지 않는 노드는 여기에 포함되죠)

- poham (a,b)는 a가 b를 포함하는지 확인하는 함수 입니다

- maketree는 한 노드가 다른 노드를 포함하는데 그 사이에 어떤 노드도 없을 때, 즉, 자식 관계를 설정할 때 썼습니다. (트리에서 바로 밑 레이어에 속하는지 !)

- makeutil은 depth 와 parent를 설정하기 위한 함수입니다.

- lca는 n이 매우 작아 간략하게 작성했습니다

이 풀이로도 테스트 케이스는 맞습니다.... ㅜ...

하다가 다른 풀이를 떠올려서 그건 짧은 코드로 맞았는데, 이건 왜 틀릴까요? 흠...

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define INF 0x3f3f3f3f3f3f3f3f
#define pb push_back
using namespace std;

int t,n;
long long inity,initx,endy,endx;
long long planet[55][3];
int  depth[55], parent[55];
vector<vector<int> > link;

//a poham b
bool poham (int a, int b) {
    long long x=planet[a][0] - planet[b][0], y=planet[a][1] - planet[b][1], r1=planet[a][2], r2=planet[b][2]; 
    return (r1>r2) && (y*y + x*x < r1*r1);
}

void makeTree() {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(poham(i,j) && i != j) {
                bool no = false;
                for(int l=1;l<=n;l++) {
                    if(poham(i,l) && poham(l,j) && i!=l && l!=j) {
                        no = true;
                        break;
                    }
                }
                if(!no) 
                    link[i].push_back(j);
            }
        }
    }

    //for finding node just under the 'root'
    for(int i=1;i<=n;i++) {
        bool no = false;
        for(int j=1;j<=n;j++) 
            if(poham(j,i) && i!=j)
                no = true;
        
        if(!no) 
            link[0].push_back(i);
    }
}

void makeUtil(int pos) {
    for(int i=0;i<link[pos].size();i++) {
        if(depth[link[pos][i]] == -1) {
            parent[link[pos][i]] = pos;
            depth[link[pos][i]] = depth[pos] + 1;
            // printf("depth %d : %d\n",link[pos][i], depth[pos]+1);
            makeUtil(link[pos][i]);
        }            
    }
}

// for n size 50... so used very simple lca

int LCA(int pa, int pb) {
    if(pa == pb)
        return pa;
    if(depth[pa] < depth[pb])
        swap(pa,pb);

    while(depth[pa] != depth[pb])
        pa=parent[pa];

    while(parent[pa] != parent[pb]) {
        pa=parent[pa];
        pb=parent[pb];
    }
    return parent[pa];
}

int getParent(long long x, long long y) {
    for(int i=0;i<=n;i++) {
        long long cx = planet[i][0] - x, cy = planet[i][1] - y, cr = planet[i][2];
        if(cx * cx + cy * cy <= cr * cr) {
            bool no = false;
            for(int j=0;j<=n;j++) {
                long long dx = planet[j][0] - x, dy = planet[j][1] - y, dr = planet[j][2];
                if(i!=j && planet[j][2] < planet[i][2] && (dx*dx + dy*dy <= dr * dr))
                    no = true;
            }
            if(!no)
                return i;
        }
    }
}


int main () {
    scanf("%d",&t);
    while(t--) {
        memset(planet,-1,sizeof(planet));
        memset(parent,-1,sizeof(parent));
        memset(depth,-1,sizeof(depth));
        scanf("%lld%lld%lld%lld%d",&initx,&inity,&endx,&endy,&n);
        for(int i=1;i<=n;i++)
            scanf("%lld%lld%lld",&planet[i][0],&planet[i][1],&planet[i][2]);
        planet[0][0] = planet[0][1] = 0;
        planet[0][2] = INF;

        link = vector<vector<int> > (n+10,vector<int> ());

        makeTree();
        depth[0] = 0;
        makeUtil(0);

        int pa = getParent(initx,inity), pb = getParent(endx,endy);
        int lca = LCA(pa,pb);
        printf("%d\n",depth[pa] - depth[lca] + depth[pb] - depth[lca]);
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이 문제를 한 번 트리 표현 하고, LCA로 풀어볼려고 했는데요.

cokcjswo 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말