Jekyll2020-08-07T06:58:04+00:00https://justicehui.github.io/rss/JusticeHui가 PS하는 블로그Let's solve problem with JusticeHui!JusticeHuiUCPC 2020 출제 후기2020-08-02T00:38:00+00:002020-08-02T00:38:00+00:00https://justicehui.github.io/review/2020/08/02/ucpc-2020-review<p>UCPC 2020이 어제(8월 1일) 성공적으로 개최되었습니다.<br /> 저는 Call for Tasks를 통해 문제를 출제하였고, 문제 출제와 관련된 후기와 풀이를 정리하고자 합니다.</p> <h3 id="서론">서론</h3> <p>대학생이 아니라서 대회에 참가하지 못하는 아쉬움을 달래기 위해 <a href="http://ucpc.me/tasks/">Call for Tasks</a>를 통해 문제를 출제했습니다.</p> <p>제가 출제한 문제는 <a href="https://www.acmicpc.net/problem/19552">본선 K. 데이터 제작</a>입니다.<br /> 문제는 간단합니다.</p> <blockquote> <p>정점 $N$개, 간선 $M$개, 면이 $K+1$개인 평면 그래프를 만드는 문제</p> </blockquote> <p>평면 그래프를 단순히 만들기만 하면 재미가 없으니까 좌표 범위 제한을 빡세게 줬습니다.</p> <p>대회에서는 5팀, Open Contest에서는 0팀이 풀었습니다ㅠㅠ</p> <h3 id="출제-계기">출제 계기</h3> <p>지난 겨울에 동아리 프로젝트를 할 때 성능 테스트를 위해 평면 그래프 데이터가 필요한 적이 있었습니다. 그 당시에 저는 평면 그래프를 이쁘게 만들 방법이 딱히 떠오르지 않았고, 그래서 결국 점을 랜덤하게 찍고 들로네 삼각분할을 했었습니다.<br /> 그때부터 이 문제를 생각하고 있었고, 결국 UCPC에 출제했습니다.</p> <p>위에서 언급했듯이 평면 그래프를 그냥 만들기만 하면 문제가 너무 쉽고 재미도 없습니다. Call for Tasks 제출 당시에는 좌표 범위 제한을 2000으로 줬는데 검수 도중 좌표를 1부터 79까지만 쓰는 풀이가 나와서 문제가 더 어려워졌습니다.</p> <h3 id="구데기인가">구데기인가?</h3> <p>저는 Constructive 문제를 혐오합니다.</p> <p>그래서 그런지 제 문제가 구데기라고 욕 먹고 채택이 되지 않을 것이라고 생각했고, 본선 문제로 채택되었다는 이메일을 받게 되어서 놀랐습니다.<br /> 대회 종료 후에도 주변의 평가가 꽤 좋았던 것으로 보아 구데기는 아닌 것 같네요.</p> <h3 id="문제-세팅">문제 세팅</h3> <p>당연히 데이터는 만들기 쉽습니다.</p> <ul> <li>generator에서는 정수 3개 찍고</li> <li>validator에서는 정수 3개 검증하고</li> <li>코너 케이스도 빽빽한 그래프랑 간선 얼마 없는 그래프만 몇 개 넣어주면 됩니다.</li> </ul> <p>checker에서는 문제에 나와있는 6개의 조건만 검사해주면 됩니다. $O(M^2)$ 정도에 Naive하게 하면 됩니다.</p> <p>제 절망적인 작문 실력때문에 디스크립션 작성이 제일 힘들었습니다. 도와주신 운영진 및 검수진분들 정말 감사합니다…</p> <h3 id="풀이">풀이</h3> <p>self loop와 multi edge가 없는 평면 그래프에서는 $V-E+F=C+1$이 성립합니다. $N=V,M=E,K=F-1$이므로 $N-M+K=C$가 성립합니다.<br /> $C = 1$이라면 열심히 Connected Graph를 만들어주면 되고, $C \neq 1$이라면 $C-1$개의 정점을 제외한 나머지 정점들로 Connected Graph를 만든 뒤 $C-1$개의 정점을 다른 곳에 뿌려주면 됩니다.</p> <p>self loop와 multi edge가 없는 평면 그래프에서는 $E \leq 3V-6$이 성립합니다. 그리고 등호는 모든 Face가 삼각형일 때 성립합니다. Connected Graph를 만드는 것은 $3000$개의 정점과 $9000-6$개의 간선으로 이루어진 그래프를 만든 뒤, 정점과 간선을 적절히 지우는 것으로 구현할 수 있습니다.<br /> 즉, 적당히 큰 삼각형을 만들고 삼각형 내부에 $3000-3$개의 점을 더 찍고, 삼각형으로 다 쪼개주면 됩니다.</p> <h4 id="범위-제한--2000">범위 제한 = 2000</h4> <p>원래는 범위 제한이 2000이였습니다. 이 경우에는 아래 그림처럼 작은 삼각형을 하나 만든 뒤, 하나씩 확장하는 방식으로 구현해주면 됩니다. 점 3개 당 범위가 2씩 늘어나기 때문에 2000 이내에 모든 점을 넣을 수 있습니다.</p> <p><img src="/img/vef2000.png" alt="" /></p> <h4 id="범위-제한--79">범위 제한 = 79</h4> <p>$(1, 1), (1, 79), (29, 2)$에 점을 찍어서 큰 삼각형을 만들어줍시다.</p> <ul> <li>$y = 78$인 점은 1개</li> <li>$y = 77$인 점은 2개</li> <li>$y = 76$인 점은 3개</li> <li>…</li> <li>$y = i$인 점은 79-i개</li> </ul> <p>의 점을 삼각형 내부에 넣어줄 수 있고, 점의 최대 개수는 $\frac{78 \times 79}{2}+3 = 3084$로 3000개의 점을 넣기에 충분합니다.<br /> 간선은 아래 그림처럼 넣어주면 됩니다.</p> <p><img src="/img/vef79.png" alt="" /></p> <p>점 3000개 찍고 보로노이(or 들로네 삼각분할)를 돌린 팀도 있었습니다.</p> <h3 id="난이도">난이도</h3> <p>풀이 방송을 보시면 아시겠지만, 저는 처음에 <strong>Gold 1</strong>을 예상했습니다. 검수진분들은 <strong>Diamond 4~5</strong>라는 의견을 내셨고, 8월 2일 오전 1시 26분 기준 solved.ac 난이도는 <strong>Diamond 3</strong>입니다.</p> <p>역시 출제자의 난이도 의견은 믿을게 못 됩니다.</p> <h3 id="기타">기타</h3> <p>이번 UCPC 운영을 지켜보면서 대회 운영이나 문제 세팅, 출제와 관련해서 많은 것을 배웠습니다. 나중에 제가 직접 대회를 운영하게 된다면, 이번 UCPC의 기억을 되살려 원활하게 잘 운영을 할 수 있도록 노력해야겠습니다. (아직은 전대프연 회장 할 생각 없습니다ㅡㅡ)</p>JusticeHuiUCPC 2020이 어제(8월 1일) 성공적으로 개최되었습니다. 저는 Call for Tasks를 통해 문제를 출제하였고, 문제 출제와 관련된 후기와 풀이를 정리하고자 합니다.백준15315 태풍의 아들 KDH2020-07-12T04:31:00+00:002020-07-12T04:31:00+00:00https://justicehui.github.io/ps/2020/07/12/BOJ15315<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/15315</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>Centroid</li> <li>FFT</li> </ul> <h3 id="풀이">풀이</h3> <p>경로의 길이를 $d$라고 했을 때, 해당 경로의 교통량의 기댓값은 $d \times (1-\frac{a}{b})^{d+1}$입니다.<br /> <strong>cnt[k] = 길이가 k인 경로의 개수</strong> 로 정의한 다음 cnt[k]를 잘 구해주면 문제를 쉽게 풀 수 있습니다.</p> <p>cnt배열을 구하는 것은 Centroid와 FFT로 할 수 있습니다.<br /> <a href="/ps/2020/07/12/BOJ14176/">BOJ14176 트리와 소수</a> 문제의 <a href="/ps/2020/07/12/BOJ14176/">풀이</a>를 참고하시면 됩니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#pragma GCC target ("avx,avx2,fma") #include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="k">const</span> <span class="n">ll</span> <span class="n">mod</span> <span class="o">=</span> <span class="mf">1e9</span><span class="o">+</span><span class="mi">7</span><span class="p">;</span> <span class="k">const</span> <span class="kt">double</span> <span class="n">pi</span> <span class="o">=</span> <span class="n">acos</span><span class="p">(</span><span class="o">-</span><span class="mi">1</span><span class="p">);</span> <span class="n">ll</span> <span class="nf">pw</span><span class="p">(</span><span class="n">ll</span> <span class="n">a</span><span class="p">,</span> <span class="n">ll</span> <span class="n">b</span><span class="p">){</span> <span class="n">ll</span> <span class="n">ret</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">b</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">b</span> <span class="o">&amp;</span> <span class="mi">1</span><span class="p">)</span> <span class="n">ret</span> <span class="o">=</span> <span class="n">ret</span> <span class="o">*</span> <span class="n">a</span> <span class="o">%</span> <span class="n">mod</span><span class="p">;</span> <span class="n">b</span> <span class="o">&gt;&gt;=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">a</span> <span class="o">=</span> <span class="n">a</span> <span class="o">*</span> <span class="n">a</span> <span class="o">%</span> <span class="n">mod</span><span class="p">;</span> <span class="p">}</span> <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> <span class="p">}</span> <span class="c1">// FFT</span> <span class="cp">#include &lt;smmintrin.h&gt; #include &lt;immintrin.h&gt; </span><span class="n">__m256d</span> <span class="nf">mult</span><span class="p">(</span><span class="n">__m256d</span> <span class="n">a</span><span class="p">,</span> <span class="n">__m256d</span> <span class="n">b</span><span class="p">){</span> <span class="n">__m256d</span> <span class="n">c</span> <span class="o">=</span> <span class="n">_mm256_movedup_pd</span><span class="p">(</span><span class="n">a</span><span class="p">);</span> <span class="n">__m256d</span> <span class="n">d</span> <span class="o">=</span> <span class="n">_mm256_shuffle_pd</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="mi">15</span><span class="p">);</span> <span class="n">__m256d</span> <span class="n">cb</span> <span class="o">=</span> <span class="n">_mm256_mul_pd</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">b</span><span class="p">);</span> <span class="n">__m256d</span> <span class="n">db</span> <span class="o">=</span> <span class="n">_mm256_mul_pd</span><span class="p">(</span><span class="n">d</span><span class="p">,</span> <span class="n">b</span><span class="p">);</span> <span class="n">__m256d</span> <span class="n">e</span> <span class="o">=</span> <span class="n">_mm256_shuffle_pd</span><span class="p">(</span><span class="n">db</span><span class="p">,</span> <span class="n">db</span><span class="p">,</span> <span class="mi">5</span><span class="p">);</span> <span class="n">__m256d</span> <span class="n">r</span> <span class="o">=</span> <span class="n">_mm256_addsub_pd</span><span class="p">(</span><span class="n">cb</span><span class="p">,</span> <span class="n">e</span><span class="p">);</span> <span class="k">return</span> <span class="n">r</span><span class="p">;</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">hell_joseon_fft</span><span class="p">(</span><span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">__m128d</span> <span class="n">a</span><span class="p">[],</span> <span class="kt">bool</span> <span class="n">inv</span> <span class="o">=</span> <span class="nb">false</span><span class="p">){</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">){</span> <span class="kt">int</span> <span class="n">bit</span> <span class="o">=</span> <span class="n">n</span><span class="o">&gt;&gt;</span><span class="mi">1</span><span class="p">;</span> <span class="k">for</span><span class="p">(;</span><span class="n">j</span><span class="o">&gt;=</span><span class="n">bit</span><span class="p">;</span><span class="n">bit</span><span class="o">&gt;&gt;=</span><span class="mi">1</span><span class="p">)</span> <span class="n">j</span> <span class="o">-=</span> <span class="n">bit</span><span class="p">;</span> <span class="n">j</span> <span class="o">+=</span> <span class="n">bit</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span><span class="o">&lt;</span><span class="n">j</span><span class="p">)</span> <span class="n">swap</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="p">]);</span> <span class="p">}</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">len</span><span class="o">=</span><span class="mi">2</span><span class="p">;</span> <span class="n">len</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">len</span><span class="o">&lt;&lt;=</span><span class="mi">1</span><span class="p">){</span> <span class="kt">double</span> <span class="n">ang</span> <span class="o">=</span> <span class="mi">2</span><span class="o">*</span><span class="n">pi</span><span class="o">/</span><span class="n">len</span><span class="o">*</span><span class="p">(</span><span class="n">inv</span><span class="o">?-</span><span class="mi">1</span><span class="o">:</span><span class="mi">1</span><span class="p">);</span> <span class="n">__m256d</span> <span class="n">wlen</span><span class="p">;</span> <span class="n">wlen</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="n">cos</span><span class="p">(</span><span class="n">ang</span><span class="p">),</span> <span class="n">wlen</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="n">sin</span><span class="p">(</span><span class="n">ang</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span> <span class="o">+=</span> <span class="n">len</span><span class="p">){</span> <span class="n">__m256d</span> <span class="n">w</span><span class="p">;</span> <span class="n">w</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">w</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;</span><span class="n">len</span><span class="o">/</span><span class="mi">2</span><span class="p">;</span> <span class="o">++</span><span class="n">j</span><span class="p">){</span> <span class="n">w</span> <span class="o">=</span> <span class="n">_mm256_permute2f128_pd</span><span class="p">(</span><span class="n">w</span><span class="p">,</span> <span class="n">w</span><span class="p">,</span> <span class="mi">0</span><span class="p">);</span> <span class="n">wlen</span> <span class="o">=</span> <span class="n">_mm256_insertf128_pd</span><span class="p">(</span><span class="n">wlen</span><span class="p">,</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="n">j</span><span class="o">+</span><span class="n">len</span><span class="o">/</span><span class="mi">2</span><span class="p">],</span> <span class="mi">1</span><span class="p">);</span> <span class="n">w</span> <span class="o">=</span> <span class="n">mult</span><span class="p">(</span><span class="n">w</span><span class="p">,</span> <span class="n">wlen</span><span class="p">);</span> <span class="n">__m128d</span> <span class="n">vw</span> <span class="o">=</span> <span class="n">_mm256_extractf128_pd</span><span class="p">(</span><span class="n">w</span><span class="p">,</span> <span class="mi">1</span><span class="p">);</span> <span class="n">__m128d</span> <span class="n">u</span> <span class="o">=</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="n">j</span><span class="p">];</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">_mm_add_pd</span><span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">vw</span><span class="p">);</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="n">j</span><span class="o">+</span><span class="n">len</span><span class="o">/</span><span class="mi">2</span><span class="p">]</span> <span class="o">=</span> <span class="n">_mm_sub_pd</span><span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">vw</span><span class="p">);</span> <span class="p">}</span> <span class="p">}</span> <span class="p">}</span> <span class="k">if</span><span class="p">(</span><span class="n">inv</span><span class="p">){</span> <span class="n">__m128d</span> <span class="n">inv</span><span class="p">;</span> <span class="n">inv</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="n">inv</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="mf">1.0</span><span class="o">/</span><span class="n">n</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">_mm_mul_pd</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">inv</span><span class="p">);</span> <span class="p">}</span> <span class="p">}</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">ll</span><span class="o">&gt;</span> <span class="n">multiply</span><span class="p">(</span><span class="n">vector</span><span class="o">&lt;</span><span class="n">ll</span><span class="o">&gt;&amp;</span> <span class="n">v</span><span class="p">,</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">ll</span><span class="o">&gt;&amp;</span> <span class="n">w</span><span class="p">){</span> <span class="kt">int</span> <span class="n">n</span> <span class="o">=</span> <span class="mi">2</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">n</span> <span class="o">&lt;</span> <span class="n">v</span><span class="p">.</span><span class="n">size</span><span class="p">()</span><span class="o">+</span><span class="n">w</span><span class="p">.</span><span class="n">size</span><span class="p">())</span> <span class="n">n</span><span class="o">&lt;&lt;=</span><span class="mi">1</span><span class="p">;</span> <span class="n">__m128d</span><span class="o">*</span> <span class="n">fv</span> <span class="o">=</span> <span class="k">new</span> <span class="n">__m128d</span><span class="p">[</span><span class="n">n</span><span class="p">];</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="n">fv</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="n">fv</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">v</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="n">fv</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="n">v</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">w</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="n">fv</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="n">w</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="n">hell_joseon_fft</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">fv</span><span class="p">);</span> <span class="c1">// (a+bi) is stored in FFT</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span> <span class="o">+=</span> <span class="mi">2</span><span class="p">){</span> <span class="n">__m256d</span> <span class="n">a</span><span class="p">;</span> <span class="n">a</span> <span class="o">=</span> <span class="n">_mm256_insertf128_pd</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">fv</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="mi">0</span><span class="p">);</span> <span class="n">a</span> <span class="o">=</span> <span class="n">_mm256_insertf128_pd</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">fv</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">],</span> <span class="mi">1</span><span class="p">);</span> <span class="n">a</span> <span class="o">=</span> <span class="n">mult</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">a</span><span class="p">);</span> <span class="n">fv</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">_mm256_extractf128_pd</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="mi">0</span><span class="p">);</span> <span class="n">fv</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="n">_mm256_extractf128_pd</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="mi">1</span><span class="p">);</span> <span class="p">}</span> <span class="n">hell_joseon_fft</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">fv</span><span class="p">,</span> <span class="mi">1</span><span class="p">);</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">ll</span><span class="o">&gt;</span> <span class="n">ret</span><span class="p">(</span><span class="n">n</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="n">ret</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="p">(</span><span class="n">ll</span><span class="p">)</span><span class="n">round</span><span class="p">(</span><span class="n">fv</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="mi">1</span><span class="p">]</span><span class="o">/</span><span class="mi">2</span><span class="p">);</span> <span class="k">delete</span><span class="p">[]</span> <span class="n">fv</span><span class="p">;</span> <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> <span class="p">}</span> <span class="n">ll</span> <span class="n">n</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">g</span><span class="p">[</span><span class="mi">202020</span><span class="p">];</span> <span class="kt">int</span> <span class="n">sz</span><span class="p">[</span><span class="mi">202020</span><span class="p">],</span> <span class="n">use</span><span class="p">[</span><span class="mi">202020</span><span class="p">];</span> <span class="n">ll</span> <span class="n">cnt</span><span class="p">[</span><span class="mi">202020</span><span class="p">];</span> <span class="c1">// Centroid</span> <span class="kt">int</span> <span class="nf">getSize</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">p</span><span class="p">){</span> <span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="n">v</span><span class="p">])</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">!=</span> <span class="n">p</span> <span class="o">&amp;&amp;</span> <span class="o">!</span><span class="n">use</span><span class="p">[</span><span class="n">i</span><span class="p">]){</span> <span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">+=</span> <span class="n">getSize</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">v</span><span class="p">);</span> <span class="p">}</span> <span class="k">return</span> <span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">];</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">getCent</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">p</span><span class="p">,</span> <span class="kt">int</span> <span class="n">s</span><span class="p">){</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="n">v</span><span class="p">])</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">!=</span> <span class="n">p</span> <span class="o">&amp;&amp;</span> <span class="o">!</span><span class="n">use</span><span class="p">[</span><span class="n">i</span><span class="p">]){</span> <span class="k">if</span><span class="p">(</span><span class="n">sz</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&gt;</span> <span class="n">s</span><span class="o">/</span><span class="mi">2</span><span class="p">)</span> <span class="k">return</span> <span class="n">getCent</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">s</span><span class="p">);</span> <span class="p">}</span> <span class="k">return</span> <span class="n">v</span><span class="p">;</span> <span class="p">}</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">ll</span><span class="o">&gt;</span> <span class="n">subtree</span><span class="p">,</span> <span class="n">acc</span><span class="p">;</span> <span class="kt">int</span> <span class="n">depth</span><span class="p">;</span> <span class="kt">void</span> <span class="nf">update_sub</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">p</span><span class="p">,</span> <span class="kt">int</span> <span class="n">d</span><span class="p">){</span> <span class="n">depth</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">depth</span><span class="p">,</span> <span class="n">d</span><span class="p">);</span> <span class="n">subtree</span><span class="p">[</span><span class="n">d</span><span class="p">]</span><span class="o">++</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="n">v</span><span class="p">])</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">!=</span> <span class="n">p</span> <span class="o">&amp;&amp;</span> <span class="o">!</span><span class="n">use</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">update_sub</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">d</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">calc</span><span class="p">(){</span> <span class="k">auto</span> <span class="n">t</span> <span class="o">=</span> <span class="n">multiply</span><span class="p">(</span><span class="n">subtree</span><span class="p">,</span> <span class="n">acc</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">t</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cnt</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+=</span> <span class="n">t</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">solve</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">){</span> <span class="kt">int</span> <span class="n">cent</span> <span class="o">=</span> <span class="n">getCent</span><span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="n">getSize</span><span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">));</span> <span class="n">getSize</span><span class="p">(</span><span class="n">cent</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">);</span> <span class="n">use</span><span class="p">[</span><span class="n">cent</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">acc</span><span class="p">.</span><span class="n">resize</span><span class="p">(</span><span class="mi">1</span><span class="p">);</span> <span class="n">acc</span><span class="p">.</span><span class="n">reserve</span><span class="p">(</span><span class="n">sz</span><span class="p">[</span><span class="n">cent</span><span class="p">]</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span> <span class="n">acc</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">sort</span><span class="p">(</span><span class="n">all</span><span class="p">(</span><span class="n">g</span><span class="p">[</span><span class="n">cent</span><span class="p">]),</span> <span class="p">[</span><span class="o">&amp;</span><span class="p">](</span><span class="kt">int</span> <span class="n">a</span><span class="p">,</span> <span class="kt">int</span> <span class="n">b</span><span class="p">){</span> <span class="k">return</span> <span class="n">sz</span><span class="p">[</span><span class="n">a</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">sz</span><span class="p">[</span><span class="n">b</span><span class="p">];</span> <span class="p">});</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="n">cent</span><span class="p">])</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">use</span><span class="p">[</span><span class="n">i</span><span class="p">]){</span> <span class="n">depth</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">subtree</span><span class="p">.</span><span class="n">clear</span><span class="p">();</span> <span class="n">subtree</span><span class="p">.</span><span class="n">resize</span><span class="p">(</span><span class="n">sz</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span> <span class="n">update_sub</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">cent</span><span class="p">,</span> <span class="mi">1</span><span class="p">);</span> <span class="n">calc</span><span class="p">();</span> <span class="k">if</span><span class="p">(</span><span class="n">acc</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">&lt;=</span> <span class="n">depth</span><span class="p">)</span> <span class="n">acc</span><span class="p">.</span><span class="n">resize</span><span class="p">(</span><span class="n">depth</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">depth</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="n">acc</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">+=</span> <span class="n">subtree</span><span class="p">[</span><span class="n">j</span><span class="p">];</span> <span class="p">}</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="n">cent</span><span class="p">])</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">use</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">solve</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span> <span class="o">&gt;&gt;</span> <span class="n">a</span> <span class="o">&gt;&gt;</span> <span class="n">b</span><span class="p">;</span> <span class="n">a</span> <span class="o">=</span> <span class="n">b</span> <span class="o">-</span> <span class="n">a</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="n">e</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">s</span> <span class="o">&gt;&gt;</span> <span class="n">e</span><span class="p">;</span> <span class="n">g</span><span class="p">[</span><span class="n">s</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">e</span><span class="p">);</span> <span class="n">g</span><span class="p">[</span><span class="n">e</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">s</span><span class="p">);</span> <span class="p">}</span> <span class="n">solve</span><span class="p">(</span><span class="mi">1</span><span class="p">);</span> <span class="n">ll</span> <span class="n">ans</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="n">ll</span> <span class="n">t</span> <span class="o">=</span> <span class="mi">1LL</span> <span class="o">*</span> <span class="n">i</span> <span class="o">*</span> <span class="n">cnt</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">%</span> <span class="n">mod</span><span class="p">;</span> <span class="n">ll</span> <span class="n">aa</span> <span class="o">=</span> <span class="n">pw</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span> <span class="n">ll</span> <span class="n">tt</span> <span class="o">=</span> <span class="n">pw</span><span class="p">(</span><span class="n">b</span><span class="p">,</span> <span class="n">n</span><span class="o">-</span><span class="n">i</span><span class="p">);</span> <span class="n">aa</span> <span class="o">=</span> <span class="n">aa</span> <span class="o">*</span> <span class="n">tt</span> <span class="o">%</span> <span class="n">mod</span><span class="p">;</span> <span class="n">t</span> <span class="o">=</span> <span class="n">t</span> <span class="o">*</span> <span class="n">aa</span> <span class="o">%</span> <span class="n">mod</span><span class="p">;</span> <span class="n">ans</span> <span class="o">=</span> <span class="p">(</span><span class="n">ans</span> <span class="o">+</span> <span class="n">t</span><span class="p">)</span> <span class="o">%</span> <span class="n">mod</span><span class="p">;</span> <span class="p">}</span> <span class="n">ans</span> <span class="o">=</span> <span class="n">ans</span> <span class="o">*</span> <span class="n">pw</span><span class="p">(</span><span class="n">pw</span><span class="p">(</span><span class="n">b</span><span class="p">,</span> <span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">),</span> <span class="n">mod</span><span class="o">-</span><span class="mi">2</span><span class="p">)</span> <span class="o">%</span> <span class="n">mod</span><span class="p">;</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">ans</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/15315백준14176 트리와 소수2020-07-12T04:16:00+00:002020-07-12T04:16:00+00:00https://justicehui.github.io/ps/2020/07/12/BOJ14176<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/14176</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>Centroid Decomposition</li> <li>FFT</li> </ul> <h3 id="풀이">풀이</h3> <p><strong>cnt[k] = 길이가 k인 경로의 개수</strong> 라고 정의합시다.<br /> cnt[1]부터 cnt[N-1]까지 모두 구해주면 문제를 풀 수 있습니다.</p> <p>$O(N^2)$가지의 경로를 모두 고려해야 하기 때문에 센트로이드를 생각할 수 있습니다.</p> <p>centroid $C$를 지나는 모든 경로들을 고려해봅시다.<br /> 어떤 경로가 $C$를 지난다는 것은, $C$를 제거했을 때 나눠지는 서브트리 $T_1, T_2, \ldots , T_x$가 있을 때 서로 다른 서브트리 $T_i, T_j$에서 정점을 하나씩 선택해서 이은 경로를 의미합니다.</p> <p>$T_i$에 있는 정점 중 센트로이드 $C$와 거리가 $k$만큼 떨어진 정점의 개수를 <strong>subtree[i][k]</strong> 라고 합시다.<br /> $T_i$에 있는 정점 하나와 $T_j$에 있는 정점 하나를 이어서 만든 길이가 $k$인 경로의 개수는 <strong>subtree[i][a] × subtree[j][k-a]</strong> 로 계산할 수 있습니다. 그러므로 두 개의 서브트리를 선택해서 모든 경로의 길이를 고려해주는 것은 convolusion의 형태로 나타낼 수 있고, 이는 FFT로 계산해줄 수 있습니다.</p> <p>즉, $T_1$부터 $T_x$ 까지 모두 보면서 (subtree[1] + subtree[2] + … + subtree[i-1])과 subtree[i]를 곱한 결과를 cnt에 누적시켜주면 됩니다.</p> <p>Centroid Decomposition과 FFT를 열심히 구현하면 풀리는 문제입니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">prime</span><span class="p">;</span> <span class="kt">bool</span> <span class="n">isp</span><span class="p">[</span><span class="mi">101010</span><span class="p">];</span> <span class="kt">void</span> <span class="nf">sieve</span><span class="p">(</span><span class="kt">int</span> <span class="n">n</span><span class="o">=</span><span class="mi">100000</span><span class="p">){</span> <span class="n">memset</span><span class="p">(</span><span class="n">isp</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">isp</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">2</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">isp</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">prime</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">j</span> <span class="o">:</span> <span class="n">prime</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span><span class="o">*</span><span class="n">j</span> <span class="o">&gt;</span> <span class="n">n</span><span class="p">)</span> <span class="k">break</span><span class="p">;</span> <span class="n">isp</span><span class="p">[</span><span class="n">i</span><span class="o">*</span><span class="n">j</span><span class="p">]</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span><span class="o">%</span><span class="n">j</span><span class="o">==</span><span class="mi">0</span><span class="p">)</span> <span class="k">break</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="p">}</span> <span class="c1">// FFT</span> <span class="k">typedef</span> <span class="n">complex</span><span class="o">&lt;</span><span class="kt">double</span><span class="o">&gt;</span> <span class="n">cpx</span><span class="p">;</span> <span class="kt">void</span> <span class="nf">fft</span><span class="p">(</span><span class="n">vector</span><span class="o">&lt;</span><span class="n">cpx</span><span class="o">&gt;</span> <span class="o">&amp;</span><span class="n">a</span><span class="p">,</span> <span class="kt">bool</span> <span class="n">inv</span><span class="p">){</span> <span class="kt">int</span> <span class="n">n</span> <span class="o">=</span> <span class="n">a</span><span class="p">.</span><span class="n">size</span><span class="p">(),</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">cpx</span><span class="o">&gt;</span> <span class="n">roots</span><span class="p">(</span><span class="n">n</span><span class="o">/</span><span class="mi">2</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="kt">int</span> <span class="n">bit</span> <span class="o">=</span> <span class="p">(</span><span class="n">n</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="p">);</span> <span class="k">while</span><span class="p">(</span><span class="n">j</span> <span class="o">&gt;=</span> <span class="n">bit</span><span class="p">)</span> <span class="n">j</span> <span class="o">-=</span> <span class="n">bit</span><span class="p">,</span> <span class="n">bit</span> <span class="o">&gt;&gt;=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">j</span> <span class="o">+=</span> <span class="n">bit</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">&lt;</span> <span class="n">j</span><span class="p">)</span> <span class="n">swap</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="p">]);</span> <span class="p">}</span> <span class="kt">double</span> <span class="n">ang</span> <span class="o">=</span> <span class="mi">2</span> <span class="o">*</span> <span class="n">acos</span><span class="p">(</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="o">/</span> <span class="n">n</span> <span class="o">*</span> <span class="p">(</span><span class="n">inv</span> <span class="o">?</span> <span class="o">-</span><span class="mi">1</span> <span class="o">:</span> <span class="mi">1</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="o">/</span><span class="mi">2</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">roots</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">cpx</span><span class="p">(</span><span class="n">cos</span><span class="p">(</span><span class="n">ang</span> <span class="o">*</span> <span class="n">i</span><span class="p">),</span> <span class="n">sin</span><span class="p">(</span><span class="n">ang</span> <span class="o">*</span> <span class="n">i</span><span class="p">));</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">2</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;&lt;=</span><span class="mi">1</span><span class="p">){</span> <span class="kt">int</span> <span class="n">step</span> <span class="o">=</span> <span class="n">n</span> <span class="o">/</span> <span class="n">i</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">j</span><span class="o">+=</span><span class="n">i</span><span class="p">)</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">k</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">k</span><span class="o">&lt;</span><span class="n">i</span><span class="o">/</span><span class="mi">2</span><span class="p">;</span> <span class="n">k</span><span class="o">++</span><span class="p">){</span> <span class="n">cpx</span> <span class="n">u</span> <span class="o">=</span> <span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="n">k</span><span class="p">],</span> <span class="n">v</span> <span class="o">=</span> <span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="n">k</span><span class="o">+</span><span class="n">i</span><span class="o">/</span><span class="mi">2</span><span class="p">]</span> <span class="o">*</span> <span class="n">roots</span><span class="p">[</span><span class="n">step</span> <span class="o">*</span> <span class="n">k</span><span class="p">];</span> <span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="n">k</span><span class="p">]</span> <span class="o">=</span> <span class="n">u</span><span class="o">+</span><span class="n">v</span><span class="p">;</span> <span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="n">k</span><span class="o">+</span><span class="n">i</span><span class="o">/</span><span class="mi">2</span><span class="p">]</span> <span class="o">=</span> <span class="n">u</span><span class="o">-</span><span class="n">v</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="k">if</span><span class="p">(</span><span class="n">inv</span><span class="p">)</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">/=</span> <span class="n">n</span><span class="p">;</span> <span class="p">}</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">ll</span><span class="o">&gt;</span> <span class="n">multiply</span><span class="p">(</span><span class="n">vector</span><span class="o">&lt;</span><span class="n">ll</span><span class="o">&gt;</span> <span class="o">&amp;</span><span class="n">v</span><span class="p">,</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">ll</span><span class="o">&gt;</span> <span class="o">&amp;</span><span class="n">w</span><span class="p">){</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">cpx</span><span class="o">&gt;</span> <span class="n">fv</span><span class="p">(</span><span class="n">v</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span> <span class="n">v</span><span class="p">.</span><span class="n">end</span><span class="p">()),</span> <span class="n">fw</span><span class="p">(</span><span class="n">w</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span> <span class="n">w</span><span class="p">.</span><span class="n">end</span><span class="p">());</span> <span class="kt">int</span> <span class="n">n</span> <span class="o">=</span> <span class="mi">2</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">n</span> <span class="o">&lt;</span> <span class="n">v</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">+</span> <span class="n">w</span><span class="p">.</span><span class="n">size</span><span class="p">())</span> <span class="n">n</span> <span class="o">&lt;&lt;=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">fv</span><span class="p">.</span><span class="n">resize</span><span class="p">(</span><span class="n">n</span><span class="p">);</span> <span class="n">fw</span><span class="p">.</span><span class="n">resize</span><span class="p">(</span><span class="n">n</span><span class="p">);</span> <span class="n">fft</span><span class="p">(</span><span class="n">fv</span><span class="p">,</span> <span class="mi">0</span><span class="p">);</span> <span class="n">fft</span><span class="p">(</span><span class="n">fw</span><span class="p">,</span> <span class="mi">0</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">fv</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">*=</span> <span class="n">fw</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="n">fft</span><span class="p">(</span><span class="n">fv</span><span class="p">,</span> <span class="mi">1</span><span class="p">);</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">ll</span><span class="o">&gt;</span> <span class="n">ret</span><span class="p">(</span><span class="n">n</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">ret</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="p">(</span><span class="n">ll</span><span class="p">)</span><span class="n">round</span><span class="p">(</span><span class="n">fv</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">real</span><span class="p">());</span> <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> <span class="p">}</span> <span class="n">ll</span> <span class="n">n</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">g</span><span class="p">[</span><span class="mi">101010</span><span class="p">];</span> <span class="kt">int</span> <span class="n">sz</span><span class="p">[</span><span class="mi">101010</span><span class="p">],</span> <span class="n">use</span><span class="p">[</span><span class="mi">101010</span><span class="p">];</span> <span class="n">ll</span> <span class="n">cnt</span><span class="p">[</span><span class="mi">101010</span><span class="p">];</span> <span class="c1">// Centroid</span> <span class="kt">int</span> <span class="nf">getSize</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">p</span><span class="p">){</span> <span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="n">v</span><span class="p">])</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">!=</span> <span class="n">p</span> <span class="o">&amp;&amp;</span> <span class="o">!</span><span class="n">use</span><span class="p">[</span><span class="n">i</span><span class="p">]){</span> <span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">+=</span> <span class="n">getSize</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">v</span><span class="p">);</span> <span class="p">}</span> <span class="k">return</span> <span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">];</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">getCent</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">p</span><span class="p">,</span> <span class="kt">int</span> <span class="n">s</span><span class="p">){</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="n">v</span><span class="p">])</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">!=</span> <span class="n">p</span> <span class="o">&amp;&amp;</span> <span class="o">!</span><span class="n">use</span><span class="p">[</span><span class="n">i</span><span class="p">]){</span> <span class="k">if</span><span class="p">(</span><span class="n">sz</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&gt;</span> <span class="n">s</span><span class="o">/</span><span class="mi">2</span><span class="p">)</span> <span class="k">return</span> <span class="n">getCent</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">s</span><span class="p">);</span> <span class="p">}</span> <span class="k">return</span> <span class="n">v</span><span class="p">;</span> <span class="p">}</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">ll</span><span class="o">&gt;</span> <span class="n">subtree</span><span class="p">,</span> <span class="n">acc</span><span class="p">;</span> <span class="kt">int</span> <span class="n">depth</span><span class="p">;</span> <span class="kt">void</span> <span class="nf">update_sub</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">p</span><span class="p">,</span> <span class="kt">int</span> <span class="n">d</span><span class="p">){</span> <span class="n">depth</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">depth</span><span class="p">,</span> <span class="n">d</span><span class="p">);</span> <span class="n">subtree</span><span class="p">[</span><span class="n">d</span><span class="p">]</span><span class="o">++</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="n">v</span><span class="p">])</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">!=</span> <span class="n">p</span> <span class="o">&amp;&amp;</span> <span class="o">!</span><span class="n">use</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">update_sub</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">d</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">calc</span><span class="p">(){</span> <span class="k">auto</span> <span class="n">t</span> <span class="o">=</span> <span class="n">multiply</span><span class="p">(</span><span class="n">subtree</span><span class="p">,</span> <span class="n">acc</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">t</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cnt</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+=</span> <span class="n">t</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">solve</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">){</span> <span class="kt">int</span> <span class="n">cent</span> <span class="o">=</span> <span class="n">getCent</span><span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="n">getSize</span><span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">));</span> <span class="n">getSize</span><span class="p">(</span><span class="n">cent</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">);</span> <span class="n">use</span><span class="p">[</span><span class="n">cent</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">acc</span><span class="p">.</span><span class="n">resize</span><span class="p">(</span><span class="mi">1</span><span class="p">);</span> <span class="n">acc</span><span class="p">.</span><span class="n">reserve</span><span class="p">(</span><span class="n">sz</span><span class="p">[</span><span class="n">cent</span><span class="p">]</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span> <span class="n">acc</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">sort</span><span class="p">(</span><span class="n">all</span><span class="p">(</span><span class="n">g</span><span class="p">[</span><span class="n">cent</span><span class="p">]),</span> <span class="p">[</span><span class="o">&amp;</span><span class="p">](</span><span class="kt">int</span> <span class="n">a</span><span class="p">,</span> <span class="kt">int</span> <span class="n">b</span><span class="p">){</span> <span class="k">return</span> <span class="n">sz</span><span class="p">[</span><span class="n">a</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">sz</span><span class="p">[</span><span class="n">b</span><span class="p">];</span> <span class="p">});</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="n">cent</span><span class="p">])</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">use</span><span class="p">[</span><span class="n">i</span><span class="p">]){</span> <span class="n">depth</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">subtree</span><span class="p">.</span><span class="n">clear</span><span class="p">();</span> <span class="n">subtree</span><span class="p">.</span><span class="n">resize</span><span class="p">(</span><span class="n">sz</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span> <span class="n">update_sub</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">cent</span><span class="p">,</span> <span class="mi">1</span><span class="p">);</span> <span class="n">calc</span><span class="p">();</span> <span class="k">if</span><span class="p">(</span><span class="n">acc</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">&lt;=</span> <span class="n">depth</span><span class="p">)</span> <span class="n">acc</span><span class="p">.</span><span class="n">resize</span><span class="p">(</span><span class="n">depth</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">depth</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="n">acc</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">+=</span> <span class="n">subtree</span><span class="p">[</span><span class="n">j</span><span class="p">];</span> <span class="p">}</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="n">cent</span><span class="p">])</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">use</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">solve</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="n">e</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">s</span> <span class="o">&gt;&gt;</span> <span class="n">e</span><span class="p">;</span> <span class="n">g</span><span class="p">[</span><span class="n">s</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">e</span><span class="p">);</span> <span class="n">g</span><span class="p">[</span><span class="n">e</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">s</span><span class="p">);</span> <span class="p">}</span> <span class="n">solve</span><span class="p">(</span><span class="mi">1</span><span class="p">);</span> <span class="n">sieve</span><span class="p">();</span> <span class="n">ll</span> <span class="n">sum</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">prime</span><span class="p">)</span> <span class="n">sum</span> <span class="o">+=</span> <span class="n">cnt</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">fixed</span><span class="p">;</span> <span class="n">cout</span><span class="p">.</span><span class="n">precision</span><span class="p">(</span><span class="mi">10</span><span class="p">);</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="mf">1.0</span> <span class="o">*</span> <span class="n">sum</span> <span class="o">/</span> <span class="p">(</span><span class="n">n</span><span class="o">*</span><span class="p">(</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span><span class="o">/</span><span class="mi">2</span><span class="p">);</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/14176백준2544 격자판2020-07-11T04:10:00+00:002020-07-11T04:10:00+00:00https://justicehui.github.io/koi/2020/07/11/BOJ2544<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/2544</li> </ul> <h3 id="문제-출처">문제 출처</h3> <ul> <li>2007 KOI 고등부 3번</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>이분 매칭</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(NM \sqrt {NM} \log 500\,000)$</li> </ul> <h3 id="풀이">풀이</h3> <p>가장 큰 수를 X 이하로 만들 수 있는지 판별해봅시다.</p> <p>가장 큰 수를 X 이하로 만들기 위해서는 X보다 큰 모든 칸을 선택해서 제거해야 합니다.<br /> 각 행과 열을 정점으로 잡고, X보다 큰 칸에서 만나는 행과 열을 간선으로 이어준 이분 그래프를 생각해봅시다. 이분 그래프의 최소 정점 덮개를 구하면 되므로 이분 매칭을 해줄 수 있습니다. 최소 정점 덮개의 크기가 K 이하인지 판별해주면 됩니다.</p> <p>파라메트릭 서치를 통해 정답이 되는 X를 구했다면, 정답을 역추적 해야합니다.<br /> 최소 정점 덮개를 역추적하면 K 이하인 집합이 나오긴 하겠지만, 정확히 K가 아닐 수 있습니다. 이런 경우에는 X를 포함하지 않는 행과 열을 적절히 추가해서 K개로 만들어주면 됩니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">k</span><span class="p">;</span> <span class="kt">int</span> <span class="n">a</span><span class="p">[</span><span class="mi">333</span><span class="p">][</span><span class="mi">333</span><span class="p">];</span> <span class="k">namespace</span> <span class="n">Bipartite</span><span class="p">{</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">g</span><span class="p">[</span><span class="mi">333</span><span class="p">];</span> <span class="kt">int</span> <span class="n">dst</span><span class="p">[</span><span class="mi">333</span><span class="p">],</span> <span class="n">l</span><span class="p">[</span><span class="mi">333</span><span class="p">],</span> <span class="n">r</span><span class="p">[</span><span class="mi">333</span><span class="p">],</span> <span class="n">chk</span><span class="p">[</span><span class="mi">333</span><span class="p">];</span> <span class="kt">void</span> <span class="n">clear</span><span class="p">(){</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="mi">333</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">g</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">clear</span><span class="p">();</span> <span class="p">}</span> <span class="kt">void</span> <span class="n">addEdge</span><span class="p">(</span><span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="kt">int</span> <span class="n">e</span><span class="p">){</span> <span class="n">g</span><span class="p">[</span><span class="n">s</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">e</span><span class="p">);</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">bfs</span><span class="p">(){</span> <span class="n">queue</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">q</span><span class="p">;</span> <span class="kt">int</span> <span class="n">ret</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">memset</span><span class="p">(</span><span class="n">dst</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">dst</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">l</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span> <span class="o">&amp;&amp;</span> <span class="o">!</span><span class="n">dst</span><span class="p">[</span><span class="n">i</span><span class="p">]){</span> <span class="n">q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="n">dst</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="k">while</span><span class="p">(</span><span class="o">!</span><span class="n">q</span><span class="p">.</span><span class="n">empty</span><span class="p">()){</span> <span class="kt">int</span> <span class="n">v</span> <span class="o">=</span> <span class="n">q</span><span class="p">.</span><span class="n">front</span><span class="p">();</span> <span class="n">q</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="n">v</span><span class="p">]){</span> <span class="k">if</span><span class="p">(</span><span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="n">ret</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">else</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">dst</span><span class="p">[</span><span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">]]){</span> <span class="n">dst</span><span class="p">[</span><span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span> <span class="o">=</span> <span class="n">dst</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="n">q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> <span class="p">}</span> <span class="p">}</span> <span class="p">}</span> <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">dfs</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">chk</span><span class="p">[</span><span class="n">v</span><span class="p">])</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="n">chk</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="n">v</span><span class="p">]){</span> <span class="k">if</span><span class="p">(</span><span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span> <span class="o">||</span> <span class="o">!</span><span class="n">chk</span><span class="p">[</span><span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span> <span class="o">&amp;&amp;</span> <span class="n">dst</span><span class="p">[</span><span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span> <span class="o">==</span> <span class="n">dst</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">+</span> <span class="mi">1</span> <span class="o">&amp;&amp;</span> <span class="n">dfs</span><span class="p">(</span><span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">])){</span> <span class="n">l</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span> <span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">v</span><span class="p">;</span> <span class="k">return</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">match</span><span class="p">(){</span> <span class="n">memset</span><span class="p">(</span><span class="n">l</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">l</span><span class="p">);</span> <span class="n">memset</span><span class="p">(</span><span class="n">r</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">r</span><span class="p">);</span> <span class="kt">int</span> <span class="n">ret</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">bfs</span><span class="p">()){</span> <span class="n">memset</span><span class="p">(</span><span class="n">chk</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">chk</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">l</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span> <span class="o">&amp;&amp;</span> <span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="p">))</span> <span class="n">ret</span><span class="o">++</span><span class="p">;</span> <span class="p">}</span> <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">track</span><span class="p">[</span><span class="mi">666</span><span class="p">];</span> <span class="kt">void</span> <span class="n">rdfs</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">track</span><span class="p">[</span><span class="n">v</span><span class="p">])</span> <span class="k">return</span><span class="p">;</span> <span class="n">track</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="n">v</span><span class="p">]){</span> <span class="n">track</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">rdfs</span><span class="p">(</span><span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> <span class="p">}</span> <span class="p">}</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">getCover</span><span class="p">(){</span> <span class="n">match</span><span class="p">();</span> <span class="n">memset</span><span class="p">(</span><span class="n">track</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">track</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">l</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="n">rdfs</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">ret</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">track</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">ret</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="o">+</span><span class="n">m</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">track</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">ret</span><span class="p">.</span><span class="n">emplace_back</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="k">using</span> <span class="k">namespace</span> <span class="n">Bipartite</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">tracking</span><span class="p">(</span><span class="kt">int</span> <span class="n">ans</span><span class="p">){</span> <span class="kt">int</span> <span class="n">mxi</span><span class="p">[</span><span class="mi">333</span><span class="p">]</span> <span class="o">=</span> <span class="p">{</span><span class="mi">0</span><span class="p">},</span> <span class="n">mxj</span><span class="p">[</span><span class="mi">333</span><span class="p">]</span> <span class="o">=</span> <span class="p">{</span><span class="mi">0</span><span class="p">};</span> <span class="n">clear</span><span class="p">();</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">&gt;</span> <span class="n">ans</span><span class="p">)</span> <span class="n">addEdge</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">);</span> <span class="k">auto</span> <span class="n">ret</span> <span class="o">=</span> <span class="n">getCover</span><span class="p">();</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">){</span> <span class="n">mxi</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">mxi</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]);</span> <span class="n">mxj</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">mxj</span><span class="p">[</span><span class="n">j</span><span class="p">],</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]);</span> <span class="p">}</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">mxi</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;=</span> <span class="n">ans</span> <span class="o">&amp;&amp;</span> <span class="n">track</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&amp;&amp;</span> <span class="n">ret</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">&lt;</span> <span class="n">k</span><span class="p">)</span> <span class="n">ret</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">mxj</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">&lt;=</span> <span class="n">ans</span> <span class="o">&amp;&amp;</span> <span class="o">!</span><span class="n">track</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="n">n</span><span class="p">]</span> <span class="o">&amp;&amp;</span> <span class="n">ret</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">&lt;</span> <span class="n">k</span><span class="p">)</span> <span class="n">ret</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">j</span><span class="o">+</span><span class="n">n</span><span class="p">);</span> <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">f</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">){</span> <span class="n">clear</span><span class="p">();</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">&gt;</span> <span class="n">x</span><span class="p">)</span> <span class="n">addEdge</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">);</span> <span class="k">return</span> <span class="n">match</span><span class="p">();</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span> <span class="o">&gt;&gt;</span> <span class="n">m</span> <span class="o">&gt;&gt;</span> <span class="n">k</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">];</span> <span class="kt">int</span> <span class="n">l</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">r</span> <span class="o">=</span> <span class="mi">505050</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">l</span> <span class="o">&lt;</span> <span class="n">r</span><span class="p">){</span> <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="n">l</span> <span class="o">+</span> <span class="n">r</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">f</span><span class="p">(</span><span class="n">m</span><span class="p">)</span> <span class="o">&lt;=</span> <span class="n">k</span><span class="p">)</span> <span class="n">r</span> <span class="o">=</span> <span class="n">m</span><span class="p">;</span> <span class="k">else</span> <span class="n">l</span> <span class="o">=</span> <span class="n">m</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">r</span> <span class="o">&lt;&lt;</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="k">auto</span> <span class="n">t</span> <span class="o">=</span> <span class="n">tracking</span><span class="p">(</span><span class="n">r</span><span class="p">);</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">t</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">&lt;=</span> <span class="n">n</span><span class="p">)</span> <span class="n">a</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="k">else</span> <span class="n">b</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="p">}</span> <span class="n">assert</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">==</span> <span class="n">k</span><span class="p">);</span> <span class="n">sort</span><span class="p">(</span><span class="n">all</span><span class="p">(</span><span class="n">a</span><span class="p">));</span> <span class="n">sort</span><span class="p">(</span><span class="n">all</span><span class="p">(</span><span class="n">b</span><span class="p">));</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">a</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">&lt;&lt;</span> <span class="s">" "</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">a</span><span class="p">)</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">i</span> <span class="o">&lt;&lt;</span> <span class="s">" "</span><span class="p">;</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">b</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">&lt;&lt;</span> <span class="s">" "</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">b</span><span class="p">)</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">i</span><span class="o">-</span><span class="n">n</span> <span class="o">&lt;&lt;</span> <span class="s">" "</span><span class="p">;</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/2544백준1376 민식 우선 탐색2020-07-10T04:06:00+00:002020-07-10T04:06:00+00:00https://justicehui.github.io/ps/2020/07/10/BOJ1376<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/1376</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>세그먼트 트리</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(N log N)$</li> </ul> <h3 id="풀이">풀이</h3> <p>각 정점마다, 인접한 정점 중 아직 방문하지 않은 정점을 세그먼트 트리로 관리해줍시다.<br /> 갈 수 있는 정점의 개수, 갈 수 있는 정점 중 번호가 가장 작은 정점, 중간값인 정점을 모두 구해줄 수 있습니다.</p> <p>현재 구간에 있는 원소의 개수, K번째 원소를 찾는 쿼리와 임의의 원소를 제거하는 쿼리를 지원하는 세그먼트 트리를 열심히 구현해주면 됩니다.<br /> Self Loop와 Multi Edge에 대한 예외처리가 필요합니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="k">typedef</span> <span class="n">pair</span><span class="o">&lt;</span><span class="kt">int</span><span class="p">,</span> <span class="kt">int</span><span class="o">&gt;</span> <span class="n">p</span><span class="p">;</span> <span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">p</span><span class="o">&gt;</span> <span class="n">edge</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">g</span><span class="p">[</span><span class="mi">101010</span><span class="p">];</span> <span class="k">struct</span> <span class="nc">Seg</span><span class="p">{</span> <span class="kt">int</span> <span class="n">cnt</span><span class="p">,</span> <span class="n">sz</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">tree</span><span class="p">,</span> <span class="n">mx</span><span class="p">;</span> <span class="kt">void</span> <span class="n">init</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">){</span> <span class="n">sz</span> <span class="o">=</span> <span class="mi">2</span><span class="p">;</span> <span class="n">cnt</span> <span class="o">=</span> <span class="n">g</span><span class="p">[</span><span class="n">v</span><span class="p">].</span><span class="n">size</span><span class="p">();</span> <span class="k">while</span><span class="p">(</span><span class="n">sz</span> <span class="o">&lt;</span> <span class="n">cnt</span><span class="o">*</span><span class="mi">2</span><span class="p">)</span> <span class="n">sz</span> <span class="o">&lt;&lt;=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">tree</span><span class="p">.</span><span class="n">resize</span><span class="p">(</span><span class="n">sz</span><span class="p">);</span> <span class="n">mx</span><span class="p">.</span><span class="n">resize</span><span class="p">(</span><span class="n">sz</span><span class="p">);</span> <span class="n">sz</span> <span class="o">&gt;&gt;=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">cnt</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">tree</span><span class="p">[</span><span class="n">i</span><span class="o">|</span><span class="n">sz</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">,</span> <span class="n">mx</span><span class="p">[</span><span class="n">i</span><span class="o">|</span><span class="n">sz</span><span class="p">]</span> <span class="o">=</span> <span class="n">g</span><span class="p">[</span><span class="n">v</span><span class="p">][</span><span class="n">i</span><span class="p">];</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">sz</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">){</span> <span class="n">tree</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">tree</span><span class="p">[</span><span class="n">i</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">tree</span><span class="p">[</span><span class="n">i</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span> <span class="o">|</span> <span class="mi">1</span><span class="p">];</span> <span class="n">mx</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">mx</span><span class="p">[</span><span class="n">i</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span><span class="p">],</span> <span class="n">mx</span><span class="p">[</span><span class="n">i</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span> <span class="o">|</span> <span class="mi">1</span><span class="p">]);</span> <span class="p">}</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">even</span><span class="p">(){</span> <span class="kt">int</span> <span class="n">node</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">node</span> <span class="o">&lt;</span> <span class="n">sz</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">tree</span><span class="p">[</span><span class="n">node</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span><span class="p">])</span> <span class="n">node</span> <span class="o">=</span> <span class="n">node</span> <span class="o">*</span> <span class="mi">2</span><span class="p">;</span> <span class="k">else</span> <span class="n">node</span> <span class="o">=</span> <span class="n">node</span> <span class="o">*</span> <span class="mi">2</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="k">return</span> <span class="n">mx</span><span class="p">[</span><span class="n">node</span><span class="p">];</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">odd</span><span class="p">(){</span> <span class="kt">int</span> <span class="n">node</span> <span class="o">=</span> <span class="mi">1</span><span class="p">,</span> <span class="n">k</span> <span class="o">=</span> <span class="p">(</span><span class="n">tree</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">node</span> <span class="o">&lt;</span> <span class="n">sz</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">tree</span><span class="p">[</span><span class="n">node</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span><span class="p">]</span> <span class="o">&gt;=</span> <span class="n">k</span><span class="p">)</span> <span class="n">node</span> <span class="o">=</span> <span class="n">node</span> <span class="o">*</span> <span class="mi">2</span><span class="p">;</span> <span class="k">else</span> <span class="n">k</span> <span class="o">-=</span> <span class="n">tree</span><span class="p">[</span><span class="n">node</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span><span class="p">],</span> <span class="n">node</span> <span class="o">=</span> <span class="n">node</span> <span class="o">*</span> <span class="mi">2</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="k">return</span> <span class="n">mx</span><span class="p">[</span><span class="n">node</span><span class="p">];</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">query</span><span class="p">(){</span> <span class="k">if</span><span class="p">(</span><span class="n">tree</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">&amp;</span> <span class="mi">1</span><span class="p">)</span> <span class="k">return</span> <span class="n">odd</span><span class="p">();</span> <span class="k">return</span> <span class="n">even</span><span class="p">();</span> <span class="p">}</span> <span class="kt">void</span> <span class="n">erase</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">){</span> <span class="kt">int</span> <span class="n">node</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">node</span> <span class="o">&lt;</span> <span class="n">sz</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">mx</span><span class="p">[</span><span class="n">node</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span><span class="p">]</span> <span class="o">&gt;=</span> <span class="n">x</span><span class="p">)</span> <span class="n">node</span> <span class="o">=</span> <span class="n">node</span> <span class="o">*</span> <span class="mi">2</span><span class="p">;</span> <span class="k">else</span> <span class="n">node</span> <span class="o">=</span> <span class="n">node</span> <span class="o">*</span> <span class="mi">2</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="k">if</span><span class="p">(</span><span class="n">mx</span><span class="p">[</span><span class="n">node</span><span class="p">]</span> <span class="o">!=</span> <span class="n">x</span><span class="p">)</span> <span class="k">return</span><span class="p">;</span> <span class="n">x</span> <span class="o">=</span> <span class="n">node</span><span class="p">;</span> <span class="n">tree</span><span class="p">[</span><span class="n">x</span><span class="p">]</span> <span class="o">=</span> <span class="n">mx</span><span class="p">[</span><span class="n">x</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;&gt;=</span> <span class="mi">1</span><span class="p">){</span> <span class="n">tree</span><span class="p">[</span><span class="n">x</span><span class="p">]</span> <span class="o">=</span> <span class="n">tree</span><span class="p">[</span><span class="n">x</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">tree</span><span class="p">[</span><span class="n">x</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span> <span class="o">|</span> <span class="mi">1</span><span class="p">];</span> <span class="n">mx</span><span class="p">[</span><span class="n">x</span><span class="p">]</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">mx</span><span class="p">[</span><span class="n">x</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span><span class="p">],</span> <span class="n">mx</span><span class="p">[</span><span class="n">x</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span> <span class="o">|</span> <span class="mi">1</span><span class="p">]);</span> <span class="p">}</span> <span class="p">}</span> <span class="p">}</span> <span class="n">seg</span><span class="p">[</span><span class="mi">101010</span><span class="p">];</span> <span class="kt">int</span> <span class="n">chk</span><span class="p">[</span><span class="mi">101010</span><span class="p">];</span> <span class="kt">void</span> <span class="nf">dfs</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">){</span> <span class="n">chk</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">v</span> <span class="o">&lt;&lt;</span> <span class="s">" "</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="mi">1</span><span class="p">){</span> <span class="kt">int</span> <span class="n">t</span> <span class="o">=</span> <span class="n">seg</span><span class="p">[</span><span class="n">v</span><span class="p">].</span><span class="n">query</span><span class="p">();</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">t</span><span class="p">)</span> <span class="k">break</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="n">t</span><span class="p">])</span> <span class="n">seg</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">erase</span><span class="p">(</span><span class="n">t</span><span class="p">);</span> <span class="n">dfs</span><span class="p">(</span><span class="n">t</span><span class="p">);</span> <span class="p">}</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span> <span class="o">&gt;&gt;</span> <span class="n">m</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">m</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="n">e</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">s</span> <span class="o">&gt;&gt;</span> <span class="n">e</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">s</span> <span class="o">==</span> <span class="n">e</span><span class="p">)</span> <span class="k">continue</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">s</span> <span class="o">&gt;</span> <span class="n">e</span><span class="p">)</span> <span class="n">swap</span><span class="p">(</span><span class="n">s</span><span class="p">,</span> <span class="n">e</span><span class="p">);</span> <span class="n">edge</span><span class="p">.</span><span class="n">emplace_back</span><span class="p">(</span><span class="n">s</span><span class="p">,</span> <span class="n">e</span><span class="p">);</span> <span class="p">}</span> <span class="n">compress</span><span class="p">(</span><span class="n">edge</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">edge</span><span class="p">)</span> <span class="n">g</span><span class="p">[</span><span class="n">i</span><span class="p">.</span><span class="n">x</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">i</span><span class="p">.</span><span class="n">y</span><span class="p">),</span> <span class="n">g</span><span class="p">[</span><span class="n">i</span><span class="p">.</span><span class="n">y</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">i</span><span class="p">.</span><span class="n">x</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">sort</span><span class="p">(</span><span class="n">all</span><span class="p">(</span><span class="n">g</span><span class="p">[</span><span class="n">i</span><span class="p">]));</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">seg</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">init</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span> <span class="n">seg</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">erase</span><span class="p">(</span><span class="mi">1</span><span class="p">);</span> <span class="n">dfs</span><span class="p">(</span><span class="mi">1</span><span class="p">);</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/1376백준16122 Unary2020-07-09T04:03:00+00:002020-07-09T04:03:00+00:00https://justicehui.github.io/ps/2020/07/09/BOJ16122<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/16122</li> </ul> <h3 id="풀이">풀이</h3> <p>0부터 시작해서 각 상태에 NOT 혹은 MINUS 연산을 적용시켰을 때 값이 어떻게 변하는지 트리로 그려보면, 이항 계수 꼴이 나온다는 것을 알 수 있습니다.<br /> nCr를 998244353으로 나눈 나머지를 빠르게 구해주면 되는데, 998244353은 소수이므로 페르마의 소정리를 이용해서 빠르게 구해줄 수 있습니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="k">const</span> <span class="n">ll</span> <span class="n">mod</span> <span class="o">=</span> <span class="mi">998244353</span><span class="p">;</span> <span class="n">ll</span> <span class="n">fac</span><span class="p">[</span><span class="mi">1010101</span><span class="p">]</span> <span class="o">=</span> <span class="p">{</span><span class="mi">1</span><span class="p">};</span> <span class="n">ll</span> <span class="n">l</span><span class="p">[</span><span class="mi">303030</span><span class="p">],</span> <span class="n">r</span><span class="p">[</span><span class="mi">303030</span><span class="p">];</span> <span class="n">ll</span> <span class="nf">pw</span><span class="p">(</span><span class="n">ll</span> <span class="n">a</span><span class="p">,</span> <span class="n">ll</span> <span class="n">b</span><span class="p">){</span> <span class="n">ll</span> <span class="n">ret</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">b</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">b</span> <span class="o">&amp;</span> <span class="mi">1</span><span class="p">)</span> <span class="n">ret</span> <span class="o">=</span> <span class="n">ret</span> <span class="o">*</span> <span class="n">a</span> <span class="o">%</span> <span class="n">mod</span><span class="p">;</span> <span class="n">b</span> <span class="o">&gt;&gt;=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">a</span> <span class="o">=</span> <span class="n">a</span> <span class="o">*</span> <span class="n">a</span> <span class="o">%</span> <span class="n">mod</span><span class="p">;</span> <span class="p">}</span> <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="mi">1010101</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">fac</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">fac</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">*</span> <span class="n">i</span> <span class="o">%</span> <span class="n">mod</span><span class="p">;</span> <span class="n">l</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="n">r</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="mi">303030</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="n">l</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">min</span><span class="p">({</span><span class="o">-</span><span class="n">l</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">],</span> <span class="o">-</span><span class="n">l</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="o">-</span><span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">],</span> <span class="o">-</span><span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span><span class="o">-</span><span class="mi">1</span><span class="p">});</span> <span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">max</span><span class="p">({</span><span class="o">-</span><span class="n">l</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">],</span> <span class="o">-</span><span class="n">l</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="o">-</span><span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">],</span> <span class="o">-</span><span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span><span class="o">-</span><span class="mi">1</span><span class="p">});</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span> <span class="o">&gt;&gt;</span> <span class="n">m</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">m</span> <span class="o">&lt;</span> <span class="n">l</span><span class="p">[</span><span class="n">n</span><span class="p">]</span> <span class="o">||</span> <span class="n">r</span><span class="p">[</span><span class="n">n</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">m</span><span class="p">){</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="mi">0</span><span class="p">;</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="p">}</span> <span class="n">m</span> <span class="o">-=</span> <span class="n">l</span><span class="p">[</span><span class="n">n</span><span class="p">];</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">fac</span><span class="p">[</span><span class="n">n</span><span class="p">]</span> <span class="o">*</span> <span class="n">pw</span><span class="p">(</span><span class="n">fac</span><span class="p">[</span><span class="n">m</span><span class="p">],</span> <span class="n">mod</span><span class="o">-</span><span class="mi">2</span><span class="p">)</span> <span class="o">%</span> <span class="n">mod</span> <span class="o">*</span> <span class="n">pw</span><span class="p">(</span><span class="n">fac</span><span class="p">[</span><span class="n">n</span><span class="o">-</span><span class="n">m</span><span class="p">],</span> <span class="n">mod</span><span class="o">-</span><span class="mi">2</span><span class="p">)</span> <span class="o">%</span> <span class="n">mod</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/16122백준16915 호텔 관리2020-07-06T03:59:00+00:002020-07-06T03:59:00+00:00https://justicehui.github.io/ps/2020/07/06/BOJ16915<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/16915</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>2-SAT</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(N+M)$</li> </ul> <h3 id="풀이">풀이</h3> <p>(A xor B) 형태의 boolean 식이 여러 개 주어지고, 결과를 True로 만드는 변수의 조합이 있는지 판단하는 문제입니다.<br /> (A xor B)는 (A or B) and (!A or !B) 이므로 2-SAT 문제로 바꿔서 풀 수 있습니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">g</span><span class="p">[</span><span class="mi">202020</span><span class="p">],</span> <span class="n">r</span><span class="p">[</span><span class="mi">202020</span><span class="p">],</span> <span class="n">dfn</span><span class="p">;</span> <span class="kt">int</span> <span class="n">chk</span><span class="p">[</span><span class="mi">202020</span><span class="p">],</span> <span class="n">pv</span><span class="p">;</span> <span class="kt">void</span> <span class="nf">dfs</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">){</span> <span class="n">chk</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="n">v</span><span class="p">])</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">chk</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="n">dfn</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">v</span><span class="p">);</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">rdfs</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">color</span><span class="p">){</span> <span class="n">chk</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">color</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">r</span><span class="p">[</span><span class="n">v</span><span class="p">])</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">chk</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">rdfs</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">color</span><span class="p">);</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">getSCC</span><span class="p">(){</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">chk</span><span class="p">[</span><span class="n">i</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span><span class="p">])</span> <span class="n">dfs</span><span class="p">(</span><span class="n">i</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">chk</span><span class="p">[</span><span class="n">i</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span> <span class="o">|</span> <span class="mi">1</span><span class="p">])</span> <span class="n">dfs</span><span class="p">(</span><span class="n">i</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span> <span class="o">|</span> <span class="mi">1</span><span class="p">);</span> <span class="p">}</span> <span class="n">reverse</span><span class="p">(</span><span class="n">all</span><span class="p">(</span><span class="n">dfn</span><span class="p">));</span> <span class="n">memset</span><span class="p">(</span><span class="n">chk</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">chk</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">dfn</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">chk</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">rdfs</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="o">++</span><span class="n">pv</span><span class="p">);</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">addEdge</span><span class="p">(</span><span class="kt">int</span> <span class="n">a</span><span class="p">,</span> <span class="kt">int</span> <span class="n">b</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">)</span> <span class="n">a</span> <span class="o">=</span> <span class="n">a</span> <span class="o">*</span> <span class="mi">2</span><span class="p">;</span> <span class="k">else</span> <span class="n">a</span> <span class="o">=</span> <span class="p">(</span><span class="o">-</span><span class="n">a</span><span class="p">)</span> <span class="o">*</span> <span class="mi">2</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">b</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">)</span> <span class="n">b</span> <span class="o">=</span> <span class="n">b</span> <span class="o">*</span> <span class="mi">2</span><span class="p">;</span> <span class="k">else</span> <span class="n">b</span> <span class="o">=</span> <span class="p">(</span><span class="o">-</span><span class="n">b</span><span class="p">)</span> <span class="o">*</span> <span class="mi">2</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="n">g</span><span class="p">[</span><span class="n">a</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">b</span><span class="p">);</span> <span class="n">r</span><span class="p">[</span><span class="n">b</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">a</span><span class="p">);</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">a</span><span class="p">[</span><span class="mi">101010</span><span class="p">];</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">t</span><span class="p">[</span><span class="mi">101010</span><span class="p">];</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span> <span class="o">&gt;&gt;</span> <span class="n">m</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="kt">int</span> <span class="n">cnt</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">cnt</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">cnt</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">){</span> <span class="kt">int</span> <span class="n">x</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">x</span><span class="p">;</span> <span class="n">t</span><span class="p">[</span><span class="n">x</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="p">}</span> <span class="p">}</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">t</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">empty</span><span class="p">()){</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]){</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="mi">0</span><span class="p">;</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="p">}</span> <span class="k">continue</span><span class="p">;</span> <span class="p">}</span> <span class="k">if</span><span class="p">(</span><span class="n">t</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">size</span><span class="p">()</span> <span class="o">==</span> <span class="mi">1</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">addEdge</span><span class="p">(</span><span class="n">t</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="mi">0</span><span class="p">],</span> <span class="o">-</span><span class="n">t</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="mi">0</span><span class="p">]);</span> <span class="k">else</span> <span class="n">addEdge</span><span class="p">(</span><span class="o">-</span><span class="n">t</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="mi">0</span><span class="p">],</span> <span class="n">t</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="mi">0</span><span class="p">]);</span> <span class="k">continue</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">a</span> <span class="o">=</span> <span class="n">t</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="mi">0</span><span class="p">],</span> <span class="n">b</span> <span class="o">=</span> <span class="n">t</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="mi">1</span><span class="p">];</span> <span class="k">if</span><span class="p">(</span><span class="o">::</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]){</span> <span class="n">addEdge</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">);</span> <span class="n">addEdge</span><span class="p">(</span><span class="o">-</span><span class="n">a</span><span class="p">,</span> <span class="o">-</span><span class="n">b</span><span class="p">);</span> <span class="n">addEdge</span><span class="p">(</span><span class="n">b</span><span class="p">,</span> <span class="n">a</span><span class="p">);</span> <span class="n">addEdge</span><span class="p">(</span><span class="o">-</span><span class="n">b</span><span class="p">,</span> <span class="o">-</span><span class="n">a</span><span class="p">);</span> <span class="p">}</span><span class="k">else</span><span class="p">{</span> <span class="n">addEdge</span><span class="p">(</span><span class="o">-</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">);</span> <span class="n">addEdge</span><span class="p">(</span><span class="o">-</span><span class="n">b</span><span class="p">,</span> <span class="n">a</span><span class="p">);</span> <span class="n">addEdge</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="o">-</span><span class="n">b</span><span class="p">);</span> <span class="n">addEdge</span><span class="p">(</span><span class="n">b</span><span class="p">,</span> <span class="o">-</span><span class="n">a</span><span class="p">);</span> <span class="p">}</span> <span class="p">}</span> <span class="n">getSCC</span><span class="p">();</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">chk</span><span class="p">[</span><span class="n">i</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span><span class="p">]</span> <span class="o">==</span> <span class="n">chk</span><span class="p">[</span><span class="n">i</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span> <span class="o">|</span> <span class="mi">1</span><span class="p">]){</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="mi">0</span><span class="p">;</span><span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/16915백준1444 숌언어2020-07-05T00:39:00+00:002020-07-05T00:39:00+00:00https://justicehui.github.io/ps/2020/07/05/BOJ1444<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/1444</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>이분 매칭</li> </ul> <h3 id="풀이">풀이</h3> <p>인접한 두 글자를 정점으로 잡고, 인접한 두 단어를 간선으로 이어줍시다.<br /> (소문자, 대문자), (대문자, 소문자)는 각각 서로 연결되지 않기 때문에 이분 그래프가 나오게 됩니다.</p> <p>최소 정점 덮개를 구하면 되므로 이분 매칭을 해주면 됩니다.<br /> 단, (s[0], s[1])과 (s[n-2], s[n-1])은 매칭할 때 무조건 포함되어야 합니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="n">string</span> <span class="n">s</span><span class="p">;</span> <span class="kt">int</span> <span class="n">n</span><span class="p">;</span> <span class="kt">int</span> <span class="nf">id</span><span class="p">(</span><span class="kt">char</span> <span class="n">a</span><span class="p">,</span> <span class="kt">char</span> <span class="n">b</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span> <span class="o">&lt;=</span> <span class="sc">'Z'</span><span class="p">)</span> <span class="k">return</span> <span class="p">(</span><span class="n">a</span> <span class="o">-</span> <span class="sc">'A'</span><span class="p">)</span> <span class="o">*</span> <span class="mi">26</span> <span class="o">+</span> <span class="p">(</span><span class="n">b</span> <span class="o">-</span> <span class="sc">'a'</span><span class="p">)</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="k">return</span> <span class="p">(</span><span class="n">a</span> <span class="o">-</span> <span class="sc">'a'</span><span class="p">)</span> <span class="o">*</span> <span class="mi">26</span> <span class="o">+</span> <span class="p">(</span><span class="n">b</span> <span class="o">-</span> <span class="sc">'A'</span><span class="p">)</span> <span class="o">+</span> <span class="mi">1</span> <span class="o">+</span> <span class="mi">26</span><span class="o">*</span><span class="mi">26</span><span class="p">;</span> <span class="p">}</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">g</span><span class="p">[</span><span class="mi">2020</span><span class="p">];</span> <span class="kt">int</span> <span class="n">par</span><span class="p">[</span><span class="mi">2020</span><span class="p">],</span> <span class="n">chk</span><span class="p">[</span><span class="mi">2020</span><span class="p">];</span> <span class="kt">int</span> <span class="nf">dfs</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">){</span> <span class="n">chk</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="n">v</span><span class="p">]){</span> <span class="k">if</span><span class="p">(</span><span class="n">chk</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="k">continue</span><span class="p">;</span> <span class="n">chk</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">par</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span> <span class="o">||</span> <span class="n">dfs</span><span class="p">(</span><span class="n">par</span><span class="p">[</span><span class="n">i</span><span class="p">])){</span> <span class="n">par</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">v</span><span class="p">;</span> <span class="k">return</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">s</span><span class="p">;</span> <span class="n">n</span> <span class="o">=</span> <span class="n">s</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> <span class="kt">int</span> <span class="n">st</span> <span class="o">=</span> <span class="n">id</span><span class="p">(</span><span class="n">s</span><span class="p">[</span><span class="mi">0</span><span class="p">],</span> <span class="n">s</span><span class="p">[</span><span class="mi">1</span><span class="p">]),</span> <span class="n">ed</span> <span class="o">=</span> <span class="n">id</span><span class="p">(</span><span class="n">s</span><span class="p">[</span><span class="n">n</span><span class="o">-</span><span class="mi">2</span><span class="p">],</span> <span class="n">s</span><span class="p">[</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">]);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="kt">int</span> <span class="n">a</span> <span class="o">=</span> <span class="n">id</span><span class="p">(</span><span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">],</span> <span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">]),</span> <span class="n">b</span> <span class="o">=</span> <span class="n">id</span><span class="p">(</span><span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">]);</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span> <span class="o">==</span> <span class="n">st</span> <span class="o">||</span> <span class="n">a</span> <span class="o">==</span> <span class="n">ed</span> <span class="o">||</span> <span class="n">b</span> <span class="o">==</span> <span class="n">st</span> <span class="o">||</span> <span class="n">b</span> <span class="o">==</span> <span class="n">ed</span><span class="p">)</span> <span class="k">continue</span><span class="p">;</span> <span class="n">g</span><span class="p">[</span><span class="n">a</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">b</span><span class="p">);</span> <span class="n">g</span><span class="p">[</span><span class="n">b</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">a</span><span class="p">);</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">ans</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">memset</span><span class="p">(</span><span class="n">par</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">par</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="mi">26</span><span class="o">*</span><span class="mi">26</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="n">memset</span><span class="p">(</span><span class="n">chk</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">chk</span><span class="p">);</span> <span class="n">ans</span> <span class="o">+=</span> <span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="p">}</span> <span class="k">if</span><span class="p">(</span><span class="n">st</span> <span class="o">==</span> <span class="n">ed</span><span class="p">)</span> <span class="n">ans</span><span class="o">++</span><span class="p">;</span> <span class="k">else</span> <span class="n">ans</span> <span class="o">+=</span> <span class="mi">2</span><span class="p">;</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">ans</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/1444백준5377 승혁이의 과외돌이네 집 탈출하기2020-07-04T00:37:00+00:002020-07-04T00:37:00+00:00https://justicehui.github.io/icpc/2020/07/04/BOJ5377<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/5377</li> </ul> <h3 id="문제-출처">문제 출처</h3> <ul> <li>2012 BAPC 예선 G번</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>Convex Hull</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(N \log N)$</li> </ul> <h3 id="풀이">풀이</h3> <p>악동들의 위치로 convex hull을 만들었을 때, 시작점이나 도착점이 convex hull 안에 있으면 탈출할 수 없습니다.<br /> 그렇지 않은 경우에는 악동들의 위치와 시작점, 도착점을 모두 포함해서 convex hull을 만든 뒤, convex hull의 변을 따라서 이동하는 게 최적이라는 것을 쉽게 알 수 있습니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="k">typedef</span> <span class="n">pair</span><span class="o">&lt;</span><span class="n">ll</span><span class="p">,</span> <span class="n">ll</span><span class="o">&gt;</span> <span class="n">p</span><span class="p">;</span> <span class="n">istream</span><span class="o">&amp;</span> <span class="k">operator</span> <span class="o">&gt;&gt;</span> <span class="p">(</span><span class="n">istream</span> <span class="o">&amp;</span><span class="n">in</span><span class="p">,</span> <span class="n">p</span> <span class="o">&amp;</span><span class="n">t</span><span class="p">){</span> <span class="n">in</span> <span class="o">&gt;&gt;</span> <span class="n">t</span><span class="p">.</span><span class="n">x</span> <span class="o">&gt;&gt;</span> <span class="n">t</span><span class="p">.</span><span class="n">y</span><span class="p">;</span> <span class="k">return</span> <span class="n">in</span><span class="p">;</span> <span class="p">}</span> <span class="n">ostream</span><span class="o">&amp;</span> <span class="k">operator</span> <span class="o">&lt;&lt;</span> <span class="p">(</span><span class="n">ostream</span> <span class="o">&amp;</span><span class="n">out</span><span class="p">,</span> <span class="n">p</span> <span class="n">t</span><span class="p">){</span> <span class="n">out</span> <span class="o">&lt;&lt;</span> <span class="n">t</span><span class="p">.</span><span class="n">x</span> <span class="o">&lt;&lt;</span> <span class="s">" "</span> <span class="o">&lt;&lt;</span> <span class="n">t</span><span class="p">.</span><span class="n">y</span><span class="p">;</span> <span class="k">return</span> <span class="n">out</span><span class="p">;</span> <span class="p">}</span> <span class="n">p</span> <span class="k">operator</span> <span class="o">-</span> <span class="p">(</span><span class="n">p</span> <span class="n">a</span><span class="p">,</span> <span class="n">p</span> <span class="n">b</span><span class="p">){</span> <span class="k">return</span> <span class="n">p</span><span class="p">(</span><span class="n">a</span><span class="p">.</span><span class="n">x</span> <span class="o">-</span> <span class="n">b</span><span class="p">.</span><span class="n">x</span><span class="p">,</span> <span class="n">a</span><span class="p">.</span><span class="n">y</span> <span class="o">-</span> <span class="n">b</span><span class="p">.</span><span class="n">y</span><span class="p">);</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">n</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">p</span><span class="o">&gt;</span> <span class="n">v</span><span class="p">;</span> <span class="kt">int</span> <span class="nf">ccw</span><span class="p">(</span><span class="k">const</span> <span class="n">p</span> <span class="o">&amp;</span><span class="n">a</span><span class="p">,</span> <span class="k">const</span> <span class="n">p</span> <span class="o">&amp;</span><span class="n">b</span><span class="p">,</span> <span class="k">const</span> <span class="n">p</span> <span class="o">&amp;</span><span class="n">c</span><span class="p">){</span> <span class="n">ll</span> <span class="n">dx1</span> <span class="o">=</span> <span class="n">b</span><span class="p">.</span><span class="n">x</span> <span class="o">-</span> <span class="n">a</span><span class="p">.</span><span class="n">x</span><span class="p">,</span> <span class="n">dy1</span> <span class="o">=</span> <span class="n">b</span><span class="p">.</span><span class="n">y</span> <span class="o">-</span> <span class="n">a</span><span class="p">.</span><span class="n">y</span><span class="p">;</span> <span class="n">ll</span> <span class="n">dx2</span> <span class="o">=</span> <span class="n">c</span><span class="p">.</span><span class="n">x</span> <span class="o">-</span> <span class="n">b</span><span class="p">.</span><span class="n">x</span><span class="p">,</span> <span class="n">dy2</span> <span class="o">=</span> <span class="n">c</span><span class="p">.</span><span class="n">y</span> <span class="o">-</span> <span class="n">b</span><span class="p">.</span><span class="n">y</span><span class="p">;</span> <span class="n">ll</span> <span class="n">res</span> <span class="o">=</span> <span class="n">dx1</span><span class="o">*</span><span class="n">dy2</span> <span class="o">-</span> <span class="n">dx2</span><span class="o">*</span><span class="n">dy1</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">res</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">)</span> <span class="k">return</span> <span class="mi">1</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">res</span><span class="p">)</span> <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="p">}</span> <span class="n">ll</span> <span class="nf">dst</span><span class="p">(</span><span class="k">const</span> <span class="n">p</span> <span class="o">&amp;</span><span class="n">a</span><span class="p">,</span> <span class="k">const</span> <span class="n">p</span> <span class="o">&amp;</span><span class="n">b</span><span class="p">){</span> <span class="n">ll</span> <span class="n">dx</span> <span class="o">=</span> <span class="n">a</span><span class="p">.</span><span class="n">x</span> <span class="o">-</span> <span class="n">b</span><span class="p">.</span><span class="n">x</span><span class="p">,</span> <span class="n">dy</span> <span class="o">=</span> <span class="n">a</span><span class="p">.</span><span class="n">y</span> <span class="o">-</span> <span class="n">b</span><span class="p">.</span><span class="n">y</span><span class="p">;</span> <span class="k">return</span> <span class="n">dx</span><span class="o">*</span><span class="n">dx</span> <span class="o">+</span> <span class="n">dy</span><span class="o">*</span><span class="n">dy</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">cross</span><span class="p">(</span><span class="n">p</span> <span class="n">a</span><span class="p">,</span> <span class="n">p</span> <span class="n">b</span><span class="p">,</span> <span class="n">p</span> <span class="n">c</span><span class="p">,</span> <span class="n">p</span> <span class="n">d</span><span class="p">){</span> <span class="kt">int</span> <span class="n">ab</span> <span class="o">=</span> <span class="n">ccw</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">c</span><span class="p">)</span> <span class="o">*</span> <span class="n">ccw</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">d</span><span class="p">);</span> <span class="kt">int</span> <span class="n">cd</span> <span class="o">=</span> <span class="n">ccw</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">d</span><span class="p">,</span> <span class="n">a</span><span class="p">)</span> <span class="o">*</span> <span class="n">ccw</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">d</span><span class="p">,</span> <span class="n">b</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">ab</span> <span class="o">&amp;&amp;</span> <span class="o">!</span><span class="n">cd</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span> <span class="o">&gt;</span> <span class="n">b</span><span class="p">)</span> <span class="n">swap</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">c</span> <span class="o">&gt;</span> <span class="n">d</span><span class="p">)</span> <span class="n">swap</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">d</span><span class="p">);</span> <span class="k">return</span> <span class="o">!</span><span class="p">(</span><span class="n">b</span> <span class="o">&lt;</span> <span class="n">c</span> <span class="o">||</span> <span class="n">d</span> <span class="o">&lt;</span> <span class="n">a</span><span class="p">);</span> <span class="p">}</span> <span class="k">return</span> <span class="n">ab</span> <span class="o">&lt;=</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">cd</span> <span class="o">&lt;=</span> <span class="mi">0</span><span class="p">;</span> <span class="p">}</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">p</span><span class="o">&gt;</span> <span class="n">convexHull</span><span class="p">(){</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">p</span><span class="o">&gt;</span> <span class="n">ret</span><span class="p">;</span> <span class="n">swap</span><span class="p">(</span><span class="n">v</span><span class="p">[</span><span class="mi">0</span><span class="p">],</span> <span class="o">*</span><span class="n">min_element</span><span class="p">(</span><span class="n">all</span><span class="p">(</span><span class="n">v</span><span class="p">)));</span> <span class="n">sort</span><span class="p">(</span><span class="n">v</span><span class="p">.</span><span class="n">begin</span><span class="p">()</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">v</span><span class="p">.</span><span class="n">end</span><span class="p">(),</span> <span class="p">[</span><span class="o">&amp;</span><span class="p">](</span><span class="k">const</span> <span class="n">p</span> <span class="o">&amp;</span><span class="n">a</span><span class="p">,</span> <span class="k">const</span> <span class="n">p</span> <span class="o">&amp;</span><span class="n">b</span><span class="p">){</span> <span class="k">auto</span> <span class="n">cw</span> <span class="o">=</span> <span class="n">ccw</span><span class="p">(</span><span class="n">v</span><span class="p">[</span><span class="mi">0</span><span class="p">],</span> <span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">cw</span><span class="p">)</span> <span class="k">return</span> <span class="n">cw</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">;</span> <span class="k">return</span> <span class="n">dst</span><span class="p">(</span><span class="n">v</span><span class="p">[</span><span class="mi">0</span><span class="p">],</span> <span class="n">a</span><span class="p">)</span> <span class="o">&lt;</span> <span class="n">dst</span><span class="p">(</span><span class="n">v</span><span class="p">[</span><span class="mi">0</span><span class="p">],</span> <span class="n">b</span><span class="p">);</span> <span class="p">});</span> <span class="k">for</span><span class="p">(</span><span class="k">const</span> <span class="k">auto</span> <span class="o">&amp;</span><span class="n">i</span> <span class="o">:</span> <span class="n">v</span><span class="p">){</span> <span class="k">while</span><span class="p">(</span><span class="n">ret</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">&gt;=</span> <span class="mi">2</span> <span class="o">&amp;&amp;</span> <span class="n">ccw</span><span class="p">(</span><span class="n">ret</span><span class="p">[</span><span class="n">ret</span><span class="p">.</span><span class="n">size</span><span class="p">()</span><span class="o">-</span><span class="mi">2</span><span class="p">],</span> <span class="n">ret</span><span class="p">.</span><span class="n">back</span><span class="p">(),</span> <span class="n">i</span><span class="p">)</span> <span class="o">&lt;=</span> <span class="mi">0</span><span class="p">)</span> <span class="n">ret</span><span class="p">.</span><span class="n">pop_back</span><span class="p">();</span> <span class="n">ret</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="p">}</span> <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> <span class="p">}</span> <span class="n">p</span> <span class="n">st</span><span class="p">,</span> <span class="n">ed</span><span class="p">;</span> <span class="kt">int</span> <span class="nf">valid</span><span class="p">(</span><span class="n">p</span> <span class="n">t</span><span class="p">){</span> <span class="kt">int</span> <span class="n">flag</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">j</span> <span class="o">==</span> <span class="n">n</span><span class="p">)</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">ccw</span><span class="p">(</span><span class="n">v</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">v</span><span class="p">[</span><span class="n">j</span><span class="p">],</span> <span class="n">st</span><span class="p">)</span> <span class="o">&lt;=</span> <span class="mi">0</span><span class="p">)</span> <span class="n">flag</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="k">return</span> <span class="n">flag</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">nxt</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">){</span> <span class="k">return</span> <span class="n">x</span><span class="o">+</span><span class="mi">1</span> <span class="o">==</span> <span class="n">n</span> <span class="o">?</span> <span class="mi">0</span> <span class="o">:</span> <span class="n">x</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">prv</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">){</span> <span class="k">return</span> <span class="n">x</span> <span class="o">==</span> <span class="mi">0</span> <span class="o">?</span> <span class="n">n</span><span class="o">-</span><span class="mi">1</span> <span class="o">:</span> <span class="n">x</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">solve</span><span class="p">(){</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">st</span> <span class="o">&gt;&gt;</span> <span class="n">ed</span> <span class="o">&gt;&gt;</span> <span class="n">n</span><span class="p">;</span> <span class="n">v</span><span class="p">.</span><span class="n">resize</span><span class="p">(</span><span class="n">n</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="o">&amp;</span><span class="n">i</span> <span class="o">:</span> <span class="n">v</span><span class="p">)</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">i</span><span class="p">;</span> <span class="n">v</span> <span class="o">=</span> <span class="n">convexHull</span><span class="p">();</span> <span class="n">n</span> <span class="o">=</span> <span class="n">v</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">valid</span><span class="p">(</span><span class="n">st</span><span class="p">)){</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">"IMPOSSIBLE</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="k">return</span><span class="p">;</span> <span class="p">}</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">valid</span><span class="p">(</span><span class="n">ed</span><span class="p">)){</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">"IMPOSSIBLE</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="k">return</span><span class="p">;</span> <span class="p">}</span> <span class="n">v</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">st</span><span class="p">);</span> <span class="n">v</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">ed</span><span class="p">);</span> <span class="n">v</span> <span class="o">=</span> <span class="n">convexHull</span><span class="p">();</span> <span class="n">n</span> <span class="o">=</span> <span class="n">v</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> <span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="o">&amp;&amp;</span><span class="n">ccw</span><span class="p">(</span><span class="n">v</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">],</span> <span class="n">v</span><span class="p">[</span><span class="n">i</span><span class="o">%</span><span class="n">n</span><span class="p">],</span> <span class="n">st</span><span class="p">)</span><span class="o">&gt;</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">n</span><span class="o">&amp;&amp;</span><span class="n">ccw</span><span class="p">(</span><span class="n">v</span><span class="p">[</span><span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">],</span> <span class="n">v</span><span class="p">[</span><span class="n">j</span><span class="o">%</span><span class="n">n</span><span class="p">],</span> <span class="n">ed</span><span class="p">)</span><span class="o">&gt;</span><span class="mi">0</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">==</span> <span class="n">j</span> <span class="o">||</span> <span class="n">i</span> <span class="o">&gt;</span> <span class="n">n</span> <span class="o">||</span> <span class="n">j</span> <span class="o">&gt;</span> <span class="n">n</span><span class="p">){</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">fixed</span><span class="p">;</span> <span class="n">cout</span><span class="p">.</span><span class="n">precision</span><span class="p">(</span><span class="mi">3</span><span class="p">);</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">sqrt</span><span class="p">(</span><span class="n">dst</span><span class="p">(</span><span class="n">st</span><span class="p">,</span> <span class="n">ed</span><span class="p">))</span> <span class="o">&lt;&lt;</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="k">return</span><span class="p">;</span> <span class="p">}</span> <span class="n">i</span> <span class="o">%=</span> <span class="n">n</span><span class="p">;</span> <span class="n">j</span> <span class="o">%=</span> <span class="n">n</span><span class="p">;</span> <span class="kt">double</span> <span class="n">t1</span><span class="p">,</span> <span class="n">t2</span><span class="p">;</span> <span class="n">t1</span> <span class="o">=</span> <span class="n">sqrt</span><span class="p">(</span><span class="n">dst</span><span class="p">(</span><span class="n">st</span><span class="p">,</span> <span class="n">v</span><span class="p">[</span><span class="n">i</span><span class="p">]))</span> <span class="o">+</span> <span class="n">sqrt</span><span class="p">(</span><span class="n">dst</span><span class="p">(</span><span class="n">ed</span><span class="p">,</span> <span class="n">v</span><span class="p">[</span><span class="n">prv</span><span class="p">(</span><span class="n">j</span><span class="p">)]));</span> <span class="n">t2</span> <span class="o">=</span> <span class="n">sqrt</span><span class="p">(</span><span class="n">dst</span><span class="p">(</span><span class="n">st</span><span class="p">,</span> <span class="n">v</span><span class="p">[</span><span class="n">prv</span><span class="p">(</span><span class="n">i</span><span class="p">)]))</span> <span class="o">+</span> <span class="n">sqrt</span><span class="p">(</span><span class="n">dst</span><span class="p">(</span><span class="n">ed</span><span class="p">,</span> <span class="n">v</span><span class="p">[</span><span class="n">j</span><span class="p">]));</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">k</span><span class="o">=</span><span class="n">i</span><span class="p">;</span> <span class="n">k</span><span class="o">!=</span><span class="n">prv</span><span class="p">(</span><span class="n">j</span><span class="p">);</span> <span class="n">k</span><span class="o">=</span><span class="n">nxt</span><span class="p">(</span><span class="n">k</span><span class="p">))</span> <span class="n">t1</span> <span class="o">+=</span> <span class="n">sqrt</span><span class="p">(</span><span class="n">dst</span><span class="p">(</span><span class="n">v</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">v</span><span class="p">[</span><span class="n">nxt</span><span class="p">(</span><span class="n">k</span><span class="p">)]));</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">k</span><span class="o">=</span><span class="n">j</span><span class="p">;</span> <span class="n">k</span><span class="o">!=</span><span class="n">prv</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="n">k</span><span class="o">=</span><span class="n">nxt</span><span class="p">(</span><span class="n">k</span><span class="p">))</span> <span class="n">t2</span> <span class="o">+=</span> <span class="n">sqrt</span><span class="p">(</span><span class="n">dst</span><span class="p">(</span><span class="n">v</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">v</span><span class="p">[</span><span class="n">nxt</span><span class="p">(</span><span class="n">k</span><span class="p">)]));</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">fixed</span><span class="p">;</span> <span class="n">cout</span><span class="p">.</span><span class="n">precision</span><span class="p">(</span><span class="mi">3</span><span class="p">);</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">min</span><span class="p">(</span><span class="n">t1</span><span class="p">,</span> <span class="n">t2</span><span class="p">)</span> <span class="o">&lt;&lt;</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="kt">int</span> <span class="n">t</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">t</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">t</span><span class="o">--</span><span class="p">)</span> <span class="n">solve</span><span class="p">();</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/5377백준12880 그래프 차이 최소2020-07-04T00:33:00+00:002020-07-04T00:33:00+00:00https://justicehui.github.io/ps/2020/07/04/BOJ12880<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/12880</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>DFS</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(N^4)$</li> </ul> <h3 id="풀이">풀이</h3> <p>간선 가중치의 상한과 하한을 고정시킨 다음 DFS를 돌리는 것을 반복하면 됩니다.</p> <p>하지만 가능한 상한이 150,000가지, 하한도 150,000가지이므로 TLE가 나게 됩니다. 최적화를 합시다.</p> <p>가중치의 종류는 최대 $N^2$개입니다. 좌표압축을 해줍시다.<br /> 이제 가능한 상한이 $N^2$개, 하한이 $N^2$개, DFS를 하는데 $O(N^2)$으로 총 $O(N^6)$에 풀 수 있습니다.</p> <p>하지만 상한을 고정시켰을 때 하한을 $N^2$가지를 모두 보는 것이 아니라 투포인터 느낌으로 보면 $O(N^2)$을 떼어줄 수 있습니다.<br /> $O(N^4)$에 풀 수 있습니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">g</span><span class="p">[</span><span class="mi">55</span><span class="p">][</span><span class="mi">55</span><span class="p">],</span> <span class="n">cnt</span><span class="p">;</span> <span class="kt">bool</span> <span class="n">chk</span><span class="p">[</span><span class="mi">55</span><span class="p">];</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">comp</span><span class="p">;</span> <span class="kt">void</span> <span class="nf">dfs</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">l</span><span class="p">,</span> <span class="kt">int</span> <span class="n">r</span><span class="p">,</span> <span class="kt">int</span> <span class="n">flag</span><span class="p">){</span> <span class="n">cnt</span><span class="o">++</span><span class="p">;</span> <span class="n">chk</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">flag</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">chk</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&amp;&amp;</span> <span class="n">l</span> <span class="o">&lt;=</span> <span class="n">g</span><span class="p">[</span><span class="n">v</span><span class="p">][</span><span class="n">i</span><span class="p">]</span> <span class="o">&amp;&amp;</span> <span class="n">g</span><span class="p">[</span><span class="n">v</span><span class="p">][</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;=</span> <span class="n">r</span><span class="p">)</span> <span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">,</span> <span class="n">flag</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">flag</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">chk</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&amp;&amp;</span> <span class="n">l</span> <span class="o">&lt;=</span> <span class="n">g</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">v</span><span class="p">]</span> <span class="o">&amp;&amp;</span> <span class="n">g</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">v</span><span class="p">]</span> <span class="o">&lt;=</span> <span class="n">r</span><span class="p">)</span> <span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">,</span> <span class="n">flag</span><span class="p">);</span> <span class="p">}</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">valid</span><span class="p">(</span><span class="kt">int</span> <span class="n">l</span><span class="p">,</span> <span class="kt">int</span> <span class="n">r</span><span class="p">){</span> <span class="n">memset</span><span class="p">(</span><span class="n">chk</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">chk</span><span class="p">);</span> <span class="n">cnt</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">dfs</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">,</span> <span class="mi">0</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">cnt</span> <span class="o">!=</span> <span class="n">n</span><span class="p">)</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="n">memset</span><span class="p">(</span><span class="n">chk</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">chk</span><span class="p">);</span> <span class="n">cnt</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">dfs</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">,</span> <span class="mi">1</span><span class="p">);</span> <span class="k">return</span> <span class="n">cnt</span> <span class="o">==</span> <span class="n">n</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span><span class="p">;</span> <span class="n">comp</span><span class="p">.</span><span class="n">reserve</span><span class="p">(</span><span class="n">n</span><span class="o">*</span><span class="n">n</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">g</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">],</span> <span class="n">comp</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">g</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]);</span> <span class="n">compress</span><span class="p">(</span><span class="n">comp</span><span class="p">);</span> <span class="kt">int</span> <span class="n">mn</span> <span class="o">=</span> <span class="mf">1e9</span><span class="o">+</span><span class="mi">7</span><span class="p">,</span> <span class="n">l</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">r</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span><span class="p">(;</span> <span class="n">r</span><span class="o">&lt;</span><span class="n">comp</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> <span class="n">r</span><span class="o">++</span><span class="p">)</span> <span class="k">for</span><span class="p">(;</span> <span class="n">l</span><span class="o">&lt;=</span><span class="n">r</span><span class="p">;</span> <span class="n">l</span><span class="o">++</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">valid</span><span class="p">(</span><span class="n">comp</span><span class="p">[</span><span class="n">l</span><span class="p">],</span> <span class="n">comp</span><span class="p">[</span><span class="n">r</span><span class="p">]))</span> <span class="n">mn</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">mn</span><span class="p">,</span> <span class="n">comp</span><span class="p">[</span><span class="n">r</span><span class="p">]</span> <span class="o">-</span> <span class="n">comp</span><span class="p">[</span><span class="n">l</span><span class="p">]);</span> <span class="k">else</span> <span class="k">break</span><span class="p">;</span> <span class="p">}</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">mn</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/12880