알고리즘은 BCC를 사용한다. 모른다면 다른블로그를 참고하도록 하여라. 그래서 1. 리프 노드의 개수를 가지고 센트로이드 점을 잡는다. 2. BCC를 만든다. 3. 문제의 정답을 잘 출력한다. 이렇게 하면 된다. 풀이는 별로 필요 없고 코드가 중요하지 않는가. 코드를 보여주겠다. #include using namespace std; typedef long long ll; typedef pair pi; int n,m,k,co,root,d[100005],sz[100005],c[100005],inbcc[100005],it[100005]; vector tv[100005],v[100005],bridge[100005]; vector nobridge; vector bcc; stack S; set leaf[100005..
이 글에서는 적당한 존댓말과 적당한 반말을 섞은 말투를 할 거다. 일단 노답 문제다. 정해가 뭔진 모르겟지만 걍 노답 문제다. 섭테 2까지는 1에서는 'E', 나머지는 'O'를 출력하라고 하면 충분히 가능하다. ㅔ케헤케헤헤켘헤헤ㅔㅔ케ㅔ헤헿ㅎ헿ㅎ헤ㅣ히히헤힣키ㅣ헤히히킿히히히켛헿 이제부터가 시작이다. 저의 풀이의 경우에는 1. 1~10억까지 답을 구하라고 돌려놓는다. 2. 출력으로 E가 나오는 구간을 출력하라고 한다. 3. 그대로 배열에 박아 넣어서 숫자가 입력 받을때 마다 그 구간안에 포함되는지 보고 포함되면 'E', 아니면 'O'를 출력하도록 한다. 아 배고파 이제 코드를 보자. #include using namespace std; typedef long long ll; char in[55]; int nu..
11차원이라고 겁먹지 말자. 그냥 [] 가 11개 있을 뿐이다. 이번글에서는 반말을 사용하겠다. ㅇㅋ? 자 보면 걍 부분합 배열 채워서 쓱-싹 하면 되는 문제잖아 그치? 근데 포함-배제의 원리를 사용하면 시간초과가 나! (아이고 안타까워라) 그래서 새로운 방법으로 부분합 배열을 채울꺼야! 2차원 배열이 있다고 생각해보면 위에서 아래로 부분합을 한번 하고 왼쪽에서 오른쪽으로 부분합을 한번해! 그러면 부분합 배열이 만들어 지거든? (와 개쩐다;;) 이제 그러면 포함-배제의 원리를 이용하여 부분합 배열을 채우면 O(2048N) 으로 시간초과가 나지만 이제 11차원(우엑;;)으로 늘려보면 11번의 뱡향으로 밀면 된다는 것을 알았다! 그래서 저 방법을 사용하면 O(11N) 으로 된다 이말이야! 짝짝짝짝짝 내가 코..