Jekyll2021-01-15T10:26:30+00:00https://justicehui.github.io/rss/JusticeHui가 PS하는 블로그Let's solve problem with JusticeHui!JusticeHui백준19586 울타리2021-01-15T18:56:00+00:002021-01-15T18:56:00+00:00https://justicehui.github.io/ps/2021/01/15/BOJ19586<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/19586</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>볼록껍질</li> <li>로테이팅 캘리퍼스</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(N \log N)$</li> </ul> <h3 id="풀이">풀이</h3> <p>임의의 2차원 점 집합의 Minimum Bounding Box는 그 점들의 <strong>Convex Hull의 Minimum Bounding Box</strong>와 같다는 사실은 쉽게 알 수 있습니다.<br /> 더 나아가, Convex Hull의 한 변과 겹치는(무수히 많은 교점이 존재하는) Minimum Bounding Box가 존재한다는 사실이 잘 알려져 있습니다.</p> <p>Convex Hull을 구한 뒤, Convex Hull의 각 변에 대해 Bounding Box를 구하고, 그 중 최소 둘레를 구해봅시다.<br /> 반대쪽(180도) 변에 접하는 점은 Rotating Calipers를 이용해서 구할 수 있습니다. 이 방법을 응용하면, 오른쪽(90도), 왼쪽(270도) 변에 접하는 점도 Rotating Calipers를 이용해서 구할 수 있습니다.<br /> 벡터의 내적/외적을 잘 활용하면 됩니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cm">/****************************** Author: jhnah917(Justice_Hui) ******************************/</span> <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">Point</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">Point</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">Point</span> <span class="k">operator</span> <span class="o">+</span> <span class="p">(</span><span class="k">const</span> <span class="n">Point</span> <span class="n">p1</span><span class="p">,</span> <span class="k">const</span> <span class="n">Point</span> <span class="n">p2</span><span class="p">){</span> <span class="k">return</span> <span class="n">Point</span><span class="p">(</span><span class="n">p1</span><span class="p">.</span><span class="n">x</span><span class="o">+</span><span class="n">p2</span><span class="p">.</span><span class="n">x</span><span class="p">,</span> <span class="n">p1</span><span class="p">.</span><span class="n">y</span><span class="o">+</span><span class="n">p2</span><span class="p">.</span><span class="n">y</span><span class="p">);</span> <span class="p">}</span> <span class="n">Point</span> <span class="k">operator</span> <span class="o">-</span> <span class="p">(</span><span class="k">const</span> <span class="n">Point</span> <span class="n">p1</span><span class="p">,</span> <span class="k">const</span> <span class="n">Point</span> <span class="n">p2</span><span class="p">){</span> <span class="k">return</span> <span class="n">Point</span><span class="p">(</span><span class="n">p1</span><span class="p">.</span><span class="n">x</span><span class="o">-</span><span class="n">p2</span><span class="p">.</span><span class="n">x</span><span class="p">,</span> <span class="n">p1</span><span class="p">.</span><span class="n">y</span><span class="o">-</span><span class="n">p2</span><span class="p">.</span><span class="n">y</span><span class="p">);</span> <span class="p">}</span> <span class="n">ll</span> <span class="k">operator</span> <span class="o">*</span> <span class="p">(</span><span class="k">const</span> <span class="n">Point</span> <span class="n">p1</span><span class="p">,</span> <span class="k">const</span> <span class="n">Point</span> <span class="n">p2</span><span class="p">){</span> <span class="c1">/// dot</span> <span class="k">return</span> <span class="n">p1</span><span class="p">.</span><span class="n">x</span><span class="o">*</span><span class="n">p2</span><span class="p">.</span><span class="n">x</span> <span class="o">+</span> <span class="n">p1</span><span class="p">.</span><span class="n">y</span><span class="o">*</span><span class="n">p2</span><span class="p">.</span><span class="n">y</span><span class="p">;</span> <span class="p">}</span> <span class="n">ll</span> <span class="k">operator</span> <span class="o">/</span> <span class="p">(</span><span class="k">const</span> <span class="n">Point</span> <span class="n">p1</span><span class="p">,</span> <span class="k">const</span> <span class="n">Point</span> <span class="n">p2</span><span class="p">){</span> <span class="c1">/// cross</span> <span class="k">return</span> <span class="n">p1</span><span class="p">.</span><span class="n">x</span><span class="o">*</span><span class="n">p2</span><span class="p">.</span><span class="n">y</span> <span class="o">-</span> <span class="n">p2</span><span class="p">.</span><span class="n">x</span><span class="o">*</span><span class="n">p1</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="nf">CCW</span><span class="p">(</span><span class="k">const</span> <span class="n">Point</span> <span class="o">&amp;</span><span class="n">p1</span><span class="p">,</span> <span class="k">const</span> <span class="n">Point</span> <span class="o">&amp;</span><span class="n">p2</span><span class="p">,</span> <span class="k">const</span> <span class="n">Point</span> <span class="o">&amp;</span><span class="n">p3</span><span class="p">){</span> <span class="n">ll</span> <span class="n">res</span> <span class="o">=</span> <span class="p">(</span><span class="n">p2</span> <span class="o">-</span> <span class="n">p1</span><span class="p">)</span> <span class="o">/</span> <span class="p">(</span><span class="n">p3</span> <span class="o">-</span> <span class="n">p2</span><span class="p">);</span> <span class="k">return</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="o">-</span> <span class="p">(</span><span class="n">res</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">);</span> <span class="p">}</span> <span class="n">ll</span> <span class="nf">D</span><span class="p">(</span><span class="k">const</span> <span class="n">Point</span> <span class="o">&amp;</span><span class="n">p1</span><span class="p">,</span> <span class="k">const</span> <span class="n">Point</span> <span class="o">&amp;</span><span class="n">p2</span><span class="p">){</span> <span class="k">return</span> <span class="p">(</span><span class="n">p2</span><span class="o">-</span><span class="n">p1</span><span class="p">)</span> <span class="o">*</span> <span class="p">(</span><span class="n">p2</span><span class="o">-</span><span class="n">p1</span><span class="p">);</span> <span class="p">}</span> <span class="kt">double</span> <span class="nf">D</span><span class="p">(</span><span class="k">const</span> <span class="n">Point</span> <span class="o">&amp;</span><span class="n">p</span><span class="p">,</span> <span class="k">const</span> <span class="n">Point</span> <span class="o">&amp;</span><span class="n">q</span><span class="p">,</span> <span class="k">const</span> <span class="n">Point</span> <span class="o">&amp;</span><span class="n">dir</span><span class="p">){</span> <span class="k">const</span> <span class="n">Point</span> <span class="n">r</span> <span class="o">=</span> <span class="n">p</span> <span class="o">+</span> <span class="n">dir</span><span class="p">;</span> <span class="k">return</span> <span class="mf">1.0</span> <span class="o">*</span> <span class="n">abs</span><span class="p">((</span><span class="n">q</span><span class="o">-</span><span class="n">p</span><span class="p">)</span><span class="o">/</span><span class="p">(</span><span class="n">r</span><span class="o">-</span><span class="n">p</span><span class="p">))</span> <span class="o">/</span> <span class="n">sqrt</span><span class="p">(</span><span class="n">D</span><span class="p">(</span><span class="n">p</span><span class="p">,</span> <span class="n">r</span><span class="p">));</span> <span class="p">}</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">Point</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">Point</span><span class="o">&gt;</span> <span class="o">&amp;</span><span class="n">P</span><span class="p">){</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">Point</span><span class="o">&gt;</span> <span class="n">H</span><span class="p">;</span> <span class="n">swap</span><span class="p">(</span><span class="n">P</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">P</span><span class="p">)));</span> <span class="n">sort</span><span class="p">(</span><span class="n">P</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">P</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="n">P</span><span class="p">](</span><span class="k">const</span> <span class="n">Point</span> <span class="o">&amp;</span><span class="n">a</span><span class="p">,</span> <span class="k">const</span> <span class="n">Point</span> <span class="o">&amp;</span><span class="n">b</span><span class="p">){</span> <span class="kt">int</span> <span class="n">cw</span> <span class="o">=</span> <span class="n">CCW</span><span class="p">(</span><span class="n">P</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">D</span><span class="p">(</span><span class="n">P</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">D</span><span class="p">(</span><span class="n">P</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">P</span><span class="p">){</span> <span class="k">while</span><span class="p">(</span><span class="n">H</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">H</span><span class="p">[</span><span class="n">H</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">H</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">H</span><span class="p">.</span><span class="n">pop_back</span><span class="p">();</span> <span class="n">H</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">move</span><span class="p">(</span><span class="n">H</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">N</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">vector</span><span class="o">&lt;</span><span class="n">Point</span><span class="o">&gt;</span> <span class="n">P</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">P</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">vector</span><span class="o">&lt;</span><span class="n">Point</span><span class="o">&gt;</span> <span class="n">H</span> <span class="o">=</span> <span class="n">ConvexHull</span><span class="p">(</span><span class="n">P</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">H</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="n">cout</span> <span class="o">&lt;&lt;</span> <span class="mi">0</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="k">if</span><span class="p">(</span><span class="n">H</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="k">auto</span> <span class="n">mn</span> <span class="o">=</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">P</span><span class="p">));</span> <span class="k">auto</span> <span class="n">mx</span> <span class="o">=</span> <span class="o">*</span><span class="n">max_element</span><span class="p">(</span><span class="n">all</span><span class="p">(</span><span class="n">P</span><span class="p">));</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">fixed</span> <span class="o">&lt;&lt;</span> <span class="n">setprecision</span><span class="p">(</span><span class="mi">10</span><span class="p">)</span> <span class="o">&lt;&lt;</span> <span class="mf">2.0</span><span class="o">*</span><span class="n">sqrt</span><span class="p">(</span><span class="n">D</span><span class="p">(</span><span class="n">mn</span><span class="p">,</span> <span class="n">mx</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="c1">// Multiply by 4</span> <span class="kt">int</span> <span class="n">M</span> <span class="o">=</span> <span class="n">H</span><span class="p">.</span><span class="n">size</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="n">H</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">H</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">M</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">H</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">H</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">M</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">H</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">H</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> <span class="k">auto</span> <span class="n">ChkU</span> <span class="o">=</span> <span class="p">[</span><span class="o">&amp;</span><span class="n">H</span><span class="p">](</span><span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="kt">int</span> <span class="n">j</span><span class="p">){</span> <span class="k">return</span> <span class="p">(</span><span class="n">H</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">H</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">H</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="o">-</span> <span class="n">H</span><span class="p">[</span><span class="n">j</span><span class="p">])</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">;</span> <span class="p">};</span> <span class="k">auto</span> <span class="n">ChkL</span> <span class="o">=</span> <span class="p">[</span><span class="o">&amp;</span><span class="n">H</span><span class="p">](</span><span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="kt">int</span> <span class="n">j</span><span class="p">){</span> <span class="k">return</span> <span class="p">(</span><span class="n">H</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">H</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">H</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="o">-</span> <span class="n">H</span><span class="p">[</span><span class="n">j</span><span class="p">])</span> <span class="o">&gt;</span> <span class="mi">0</span> <span class="o">||</span> <span class="p">(</span><span class="n">H</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">H</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">H</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="o">-</span> <span class="n">H</span><span class="p">[</span><span class="n">j</span><span class="p">])</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">;</span> <span class="p">};</span> <span class="k">auto</span> <span class="n">ChkR</span> <span class="o">=</span> <span class="p">[</span><span class="o">&amp;</span><span class="n">H</span><span class="p">](</span><span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="kt">int</span> <span class="n">j</span><span class="p">){</span> <span class="k">return</span> <span class="p">(</span><span class="n">H</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">H</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">H</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="o">-</span> <span class="n">H</span><span class="p">[</span><span class="n">j</span><span class="p">])</span> <span class="o">&gt;</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="p">(</span><span class="n">H</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">H</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">H</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="o">-</span> <span class="n">H</span><span class="p">[</span><span class="n">j</span><span class="p">])</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">;</span> <span class="p">};</span> <span class="kt">int</span> <span class="n">u</span> <span class="o">=</span> <span class="mi">1</span><span class="p">,</span> <span class="n">l</span> <span class="o">=</span> <span class="mi">1</span><span class="p">,</span> <span class="n">r</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="kt">double</span> <span class="n">mn</span> <span class="o">=</span> <span class="mf">1e18</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="k">if</span><span class="p">(</span><span class="n">u</span><span class="o">%</span><span class="n">M</span> <span class="o">==</span> <span class="n">i</span><span class="p">)</span> <span class="n">u</span><span class="o">++</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">ChkU</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">u</span><span class="p">))</span> <span class="n">u</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="o">%</span><span class="n">M</span> <span class="o">==</span> <span class="n">i</span><span class="p">)</span> <span class="n">l</span><span class="o">++</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">ChkL</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">l</span><span class="o">++</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">r</span><span class="o">%</span><span class="n">M</span> <span class="o">==</span> <span class="n">i</span><span class="p">)</span> <span class="n">r</span><span class="o">++</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">ChkR</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">r</span><span class="p">))</span> <span class="n">r</span><span class="o">++</span><span class="p">;</span> <span class="n">Point</span> <span class="n">v1</span> <span class="o">=</span> <span class="n">H</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">H</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="n">Point</span> <span class="n">v2</span> <span class="o">=</span> <span class="p">{</span><span class="n">v1</span><span class="p">.</span><span class="n">y</span><span class="p">,</span> <span class="o">-</span><span class="n">v1</span><span class="p">.</span><span class="n">x</span><span class="p">};</span> <span class="kt">double</span> <span class="n">now</span> <span class="o">=</span> <span class="n">D</span><span class="p">(</span><span class="n">H</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">H</span><span class="p">[</span><span class="n">u</span><span class="p">],</span> <span class="n">v1</span><span class="p">)</span> <span class="o">+</span> <span class="n">D</span><span class="p">(</span><span class="n">H</span><span class="p">[</span><span class="n">l</span><span class="p">],</span> <span class="n">H</span><span class="p">[</span><span class="n">r</span><span class="p">],</span> <span class="n">v2</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">now</span><span class="o">*</span><span class="mi">2</span><span class="p">);</span> <span class="p">}</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">fixed</span> <span class="o">&lt;&lt;</span> <span class="n">setprecision</span><span class="p">(</span><span class="mi">10</span><span class="p">)</span> <span class="o">&lt;&lt;</span> <span class="n">mn</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="o">=</span> <span class="mi">1</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/19586백준1650 지민이의 테러 Season II2021-01-15T18:53:00+00:002021-01-15T18:53:00+00:00https://justicehui.github.io/ps/2021/01/15/BOJ1650<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/1650</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>MCMF</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(VE)$</li> </ul> <h3 id="풀이">풀이</h3> <p>MCMF에서 유량을 2만큼 흘리면 됩니다.</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; </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">struct</span> <span class="nc">Edge</span><span class="p">{</span> <span class="kt">int</span> <span class="n">v</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">inv</span><span class="p">;</span> <span class="n">Edge</span><span class="p">()</span> <span class="o">=</span> <span class="k">default</span><span class="p">;</span> <span class="n">Edge</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">c</span><span class="p">,</span> <span class="kt">int</span> <span class="n">d</span><span class="p">,</span> <span class="kt">int</span> <span class="n">inv</span><span class="p">)</span> <span class="o">:</span> <span class="n">v</span><span class="p">(</span><span class="n">v</span><span class="p">),</span> <span class="n">c</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">d</span><span class="p">),</span> <span class="n">inv</span><span class="p">(</span><span class="n">inv</span><span class="p">)</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">vector</span><span class="o">&lt;</span><span class="n">Edge</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">void</span> <span class="nf">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="kt">int</span> <span class="n">c</span><span class="p">,</span> <span class="kt">int</span> <span class="n">d</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">emplace_back</span><span class="p">(</span><span class="n">e</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">G</span><span class="p">[</span><span class="n">e</span><span class="p">].</span><span class="n">size</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">emplace_back</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="o">-</span><span class="n">d</span><span class="p">,</span> <span class="kt">int</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">size</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">prv</span><span class="p">[</span><span class="mi">2020</span><span class="p">],</span> <span class="n">inq</span><span class="p">[</span><span class="mi">2020</span><span class="p">],</span> <span class="n">dst</span><span class="p">[</span><span class="mi">2020</span><span class="p">],</span> <span class="n">idx</span><span class="p">[</span><span class="mi">2020</span><span class="p">];</span> <span class="kt">int</span> <span class="nf">go</span><span class="p">(){</span> <span class="k">static</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">S</span> <span class="o">=</span> <span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="p">,</span> <span class="n">T</span> <span class="o">=</span> <span class="n">N</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">memset</span><span class="p">(</span><span class="n">inq</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">inq</span><span class="p">);</span> <span class="n">memset</span><span class="p">(</span><span class="n">prv</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">prv</span><span class="p">);</span> <span class="n">memset</span><span class="p">(</span><span class="n">idx</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">idx</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="mh">0x3f</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">dst</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="n">q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">S</span><span class="p">);</span> <span class="n">inq</span><span class="p">[</span><span class="n">S</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">dst</span><span class="p">[</span><span class="n">S</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">q</span><span class="p">.</span><span class="n">size</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="n">inq</span><span class="p">[</span><span class="n">v</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">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="n">_i</span><span class="o">++</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">_i</span><span class="p">];</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span><span class="p">.</span><span class="n">c</span> <span class="o">&amp;&amp;</span> <span class="n">dst</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">&gt;</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="n">i</span><span class="p">.</span><span class="n">d</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="n">v</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="n">i</span><span class="p">.</span><span class="n">d</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="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">v</span><span class="p">;</span> <span class="n">idx</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">=</span> <span class="n">_i</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">inq</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">inq</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">=</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">i</span><span class="p">.</span><span class="n">v</span><span class="p">);</span> <span class="p">}</span> <span class="p">}</span> <span class="p">}</span> <span class="n">assert</span><span class="p">(</span><span class="n">dst</span><span class="p">[</span><span class="n">T</span><span class="p">]</span> <span class="o">&lt;</span> <span class="mf">1e9</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">T</span><span class="p">;</span> <span class="n">i</span><span class="o">!=</span><span class="n">S</span><span class="p">;</span> <span class="n">i</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">G</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="n">idx</span><span class="p">[</span><span class="n">i</span><span class="p">]].</span><span class="n">c</span><span class="o">--</span><span class="p">;</span> <span class="kt">int</span> <span class="n">inv</span> <span class="o">=</span> <span class="n">G</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="n">idx</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="n">G</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="n">c</span><span class="o">++</span><span class="p">;</span> <span class="p">}</span> <span class="k">return</span> <span class="n">dst</span><span class="p">[</span><span class="n">T</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">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">addEdge</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">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="mf">1e9</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">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">s</span><span class="p">,</span> <span class="n">e</span><span class="p">,</span> <span class="n">x</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="o">&gt;&gt;</span> <span class="n">x</span><span class="p">;</span> <span class="n">addEdge</span><span class="p">(</span><span class="n">s</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">e</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="n">x</span><span class="p">);</span> <span class="n">addEdge</span><span class="p">(</span><span class="n">e</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">s</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="n">x</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="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">2</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">ans</span> <span class="o">+=</span> <span class="n">go</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/1650백준1591 수열 복원2021-01-15T01:52:00+00:002021-01-15T01:52:00+00:00https://justicehui.github.io/ps/2021/01/15/BOJ1591<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/1591</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>오일러 회로/경로</li> </ul> <h3 id="풀이">풀이</h3> <p>수열을 적당히 이어 붙여서 원본 수열을 만들어야 합니다.<br /> 원본 수열이 주어진 수열을 <strong>모두 지난다</strong>는 점에서 모든 정점을 방문하는 <strong>해밀턴 경로</strong>나 모든 간선을 방문하는 <strong>오일러 경로</strong>를 생각해볼 수 있습니다. 해밀턴 경로 문제는 NP-Complete 문제이므로 오일러 경로 관련 풀이를 생각해봅시다.</p> <p>주어진 두 수열을 잘 <strong>연결</strong>하고, 그 <strong>연결</strong>하는 간선들을 모두 봤을 때 원본 수열이 나오도록 만들면 됩니다.<br /> 주어진 수열 $A$에서 맨 뒷 글자만 잘라낸 수열 $X = A[:-1]$과 맨 앞 글자만 잘라낸 수열 $Y = A[0:]$을 생각해봅시다. 원본 수열에서, $X$ 바로 뒤에 $Y$가 나오는 부분 수열이 존재해야 합니다. 그러므로 $X$에서 $Y$로 가는 간선을 만들고 오일러 회로/경로를 구하면 됩니다.</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; </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</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">pv</span><span class="p">;</span> <span class="n">map</span><span class="o">&lt;</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="p">,</span> <span class="kt">int</span><span class="o">&gt;</span> <span class="n">ID</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">Rev</span><span class="p">[</span><span class="mi">1010</span><span class="p">];</span> <span class="kt">int</span> <span class="n">In</span><span class="p">[</span><span class="mi">1010</span><span class="p">],</span> <span class="n">Out</span><span class="p">[</span><span class="mi">1010</span><span class="p">],</span> <span class="n">G</span><span class="p">[</span><span class="mi">1010</span><span class="p">][</span><span class="mi">1010</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">Path</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="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">pv</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">while</span><span class="p">(</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="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">--</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">Path</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">Get</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">pv</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">In</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">Out</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="k">return</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">pv</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">Out</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="k">return</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">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="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="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="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="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">if</span><span class="p">(</span><span class="n">j</span> <span class="o">!=</span> <span class="n">M</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">t</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="mi">1</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">t</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">ID</span><span class="p">.</span><span class="n">count</span><span class="p">(</span><span class="n">a</span><span class="p">))</span> <span class="n">ID</span><span class="p">[</span><span class="n">a</span><span class="p">]</span> <span class="o">=</span> <span class="o">++</span><span class="n">pv</span><span class="p">,</span> <span class="n">Rev</span><span class="p">[</span><span class="n">pv</span><span class="p">]</span> <span class="o">=</span> <span class="n">a</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">ID</span><span class="p">.</span><span class="n">count</span><span class="p">(</span><span class="n">b</span><span class="p">))</span> <span class="n">ID</span><span class="p">[</span><span class="n">b</span><span class="p">]</span> <span class="o">=</span> <span class="o">++</span><span class="n">pv</span><span class="p">,</span> <span class="n">Rev</span><span class="p">[</span><span class="n">pv</span><span class="p">]</span> <span class="o">=</span> <span class="n">b</span><span class="p">;</span> <span class="kt">int</span> <span class="n">s</span> <span class="o">=</span> <span class="n">ID</span><span class="p">[</span><span class="n">a</span><span class="p">],</span> <span class="n">e</span> <span class="o">=</span> <span class="n">ID</span><span class="p">[</span><span class="n">b</span><span class="p">];</span> <span class="n">Out</span><span class="p">[</span><span class="n">s</span><span class="p">]</span><span class="o">++</span><span class="p">;</span> <span class="n">In</span><span class="p">[</span><span class="n">e</span><span class="p">]</span><span class="o">++</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">e</span><span class="p">]</span><span class="o">++</span><span class="p">;</span> <span class="p">}</span> <span class="n">Get</span><span class="p">();</span> <span class="n">reverse</span><span class="p">(</span><span class="n">Path</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span> <span class="n">Path</span><span class="p">.</span><span class="n">end</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">Rev</span><span class="p">[</span><span class="n">Path</span><span class="p">[</span><span class="mi">0</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">Path</span><span class="p">.</span><span class="n">erase</span><span class="p">(</span><span class="n">Path</span><span class="p">.</span><span class="n">begin</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">Path</span><span class="p">)</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">Rev</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">back</span><span class="p">()</span> <span class="o">&lt;&lt;</span> <span class="s">" "</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/1591백준13506 카멜레온 부분 문자열2021-01-15T01:46:00+00:002021-01-15T01:46:00+00:00https://justicehui.github.io/ps/2021/01/15/BOJ13506<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/13506</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>KMP</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(N)$</li> </ul> <h3 id="풀이">풀이</h3> <p>$S$의 Prefix이면서 동시에 Suffix인 것들의 길이는 $fail(N), fail(fail(N)), fail(fail(fail(N))), \cdots$ 뿐입니다.<br /> Failure Function의 구축 과정을 잘 생각해보면, $fail(N)$을 제외한 $fail(fail(N)), fail(fail(fail(N))), \cdots$은 중간에 한 번 이상 더 나온다는 사실을 알 수 있습니다.</p> <p>Failure Function을 구한 뒤, Failure Function을 쭉 따라가면서 정답을 구하면 됩니다.</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; </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="kt">int</span> <span class="n">N</span><span class="p">,</span> <span class="n">Fail</span><span class="p">[</span><span class="mi">1010101</span><span class="p">],</span> <span class="n">A</span><span class="p">[</span><span class="mi">1010101</span><span class="p">];</span> <span class="kt">char</span> <span class="n">S</span><span class="p">[</span><span class="mi">1010101</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">strlen</span><span class="p">(</span><span class="n">S</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="n">i</span><span class="o">++</span><span class="p">){</span> <span class="k">while</span><span class="p">(</span><span class="n">j</span> <span class="o">&amp;&amp;</span> <span class="n">S</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">!=</span> <span class="n">S</span><span class="p">[</span><span class="n">j</span><span class="p">])</span> <span class="n">j</span> <span class="o">=</span> <span class="n">Fail</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="k">if</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="o">==</span> <span class="n">S</span><span class="p">[</span><span class="n">j</span><span class="p">])</span> <span class="n">Fail</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="o">++</span><span class="n">j</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">N</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="n">A</span><span class="p">[</span><span class="n">Fail</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">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">Fail</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">i</span><span class="p">;</span> <span class="n">i</span><span class="o">=</span><span class="n">Fail</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="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="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">S</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">cout</span> <span class="o">&lt;&lt;</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/13506백준20039 Coronavirus Trend2021-01-14T22:44:00+00:002021-01-14T22:44:00+00:00https://justicehui.github.io/icpc/2021/01/14/BOJ20039<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/20039</li> </ul> <h3 id="문제-출처">문제 출처</h3> <ul> <li>2020 인터넷 예선 D번</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>세그먼트 트리</li> <li>DP</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(N \log N)$</li> </ul> <h3 id="풀이">풀이</h3> <p>DP 느낌이 강하게 납니다. LIS 비슷하게 점화식을 세워봅시다.</p> <ul> <li>$A_i = $ $i$번째 원소까지 봤을 때, 마지막에 감소한 수열의 최대 길이</li> <li>$B_i = $ $i$번째 원소까지 봤을 때, 마지막에 2번 감소한 수열의 최대 길이</li> <li>$C_i = $ $i$번째 원소까지 봤을 때, 마지막에 증가한 수열의 최대 길이</li> <li>$D_i = $ $i$번째 원소까지 봤을 때, 마지막에 2번 증가한 수열의 최대 길이</li> </ul> <p>Naive하게 계산하면 $O(N^2)$이고, Segment Tree를 이용해 계산하면 $O(N \log N)$에 풀 수 있습니다.</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()) #define IDX(v, x) lower_bound(all(v), x) - v.begin() </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">A</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">B</span> <span class="o">=</span> <span class="mi">1</span><span class="p">,</span> <span class="n">C</span> <span class="o">=</span> <span class="mi">2</span><span class="p">,</span> <span class="n">D</span> <span class="o">=</span> <span class="mi">3</span><span class="p">,</span> <span class="n">S</span> <span class="o">=</span> <span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="mi">19</span><span class="p">;</span> <span class="kt">int</span> <span class="n">N</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="n">ST</span><span class="p">[</span><span class="mi">4</span><span class="p">][</span><span class="n">S</span> <span class="o">&lt;&lt;</span> <span class="mi">1</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">Init</span><span class="p">(){</span> <span class="n">memset</span><span class="p">(</span><span class="n">ST</span><span class="p">,</span> <span class="mh">0xc0</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">ST</span><span class="p">);</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">Update</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</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">v</span><span class="p">){</span> <span class="n">x</span> <span class="o">|=</span> <span class="n">S</span><span class="p">;</span> <span class="n">ST</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="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">ST</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">v</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">ST</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="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">ST</span><span class="p">[</span><span class="n">i</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">ST</span><span class="p">[</span><span class="n">i</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="kt">int</span> <span class="nf">Query</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</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">l</span> <span class="o">|=</span> <span class="n">S</span><span class="p">;</span> <span class="n">r</span> <span class="o">|=</span> <span class="n">S</span><span class="p">;</span> <span class="kt">int</span> <span class="n">ret</span> <span class="o">=</span> <span class="o">-</span><span class="mf">1e9</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="k">if</span><span class="p">(</span><span class="n">l</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">max</span><span class="p">(</span><span class="n">ret</span><span class="p">,</span> <span class="n">ST</span><span class="p">[</span><span class="n">i</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="o">~</span><span class="n">r</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">max</span><span class="p">(</span><span class="n">ret</span><span class="p">,</span> <span class="n">ST</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">r</span><span class="o">--</span><span class="p">]);</span> <span class="n">l</span> <span class="o">&gt;&gt;=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">r</span> <span class="o">&gt;&gt;=</span> <span class="mi">1</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="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="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">V</span><span class="p">[</span><span class="n">i</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">V</span><span class="p">[</span><span class="n">i</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="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">V</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">IDX</span><span class="p">(</span><span class="n">comp</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="mi">1</span><span class="p">;</span> <span class="n">Init</span><span class="p">();</span> <span class="n">Update</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">V</span><span class="p">[</span><span class="mi">1</span><span class="p">],</span> <span class="mi">0</span><span class="p">);</span> <span class="n">Update</span><span class="p">(</span><span class="n">C</span><span class="p">,</span> <span class="n">V</span><span class="p">[</span><span class="mi">1</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">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="kt">int</span> <span class="n">a</span> <span class="o">=</span> <span class="n">max</span><span class="p">({</span> <span class="n">Query</span><span class="p">(</span><span class="n">A</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="mi">1</span><span class="p">,</span> <span class="n">N</span><span class="p">),</span> <span class="n">Query</span><span class="p">(</span><span class="n">B</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="mi">1</span><span class="p">,</span> <span class="n">N</span><span class="p">),</span> <span class="n">Query</span><span class="p">(</span><span class="n">D</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="mi">1</span><span class="p">,</span> <span class="n">N</span><span class="p">)</span> <span class="p">})</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="kt">int</span> <span class="n">b</span> <span class="o">=</span> <span class="n">max</span><span class="p">({</span> <span class="n">Query</span><span class="p">(</span><span class="n">A</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="mi">1</span><span class="p">,</span> <span class="n">N</span><span class="p">),</span> <span class="n">Query</span><span class="p">(</span><span class="n">B</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="mi">1</span><span class="p">,</span> <span class="n">N</span><span class="p">)</span> <span class="p">})</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="kt">int</span> <span class="n">c</span> <span class="o">=</span> <span class="n">max</span><span class="p">({</span> <span class="n">Query</span><span class="p">(</span><span class="n">B</span><span class="p">,</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="p">]</span><span class="o">-</span><span class="mi">1</span><span class="p">),</span> <span class="n">Query</span><span class="p">(</span><span class="n">C</span><span class="p">,</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="p">]</span><span class="o">-</span><span class="mi">1</span><span class="p">),</span> <span class="n">Query</span><span class="p">(</span><span class="n">D</span><span class="p">,</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="p">]</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="p">})</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="kt">int</span> <span class="n">d</span> <span class="o">=</span> <span class="n">max</span><span class="p">({</span> <span class="n">Query</span><span class="p">(</span><span class="n">C</span><span class="p">,</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="p">]</span><span class="o">-</span><span class="mi">1</span><span class="p">),</span> <span class="n">Query</span><span class="p">(</span><span class="n">D</span><span class="p">,</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="p">]</span><span class="o">-</span><span class="mi">1</span><span class="p">)</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="o">==</span> <span class="mi">1</span><span class="p">)</span> <span class="n">a</span> <span class="o">=</span> <span class="mi">2</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">b</span> <span class="o">==</span> <span class="mi">1</span><span class="p">)</span> <span class="n">b</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">c</span> <span class="o">==</span> <span class="mi">1</span><span class="p">)</span> <span class="n">c</span> <span class="o">=</span> <span class="mi">2</span><span class="p">;</span> <span class="k">if</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="n">d</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">Update</span><span class="p">(</span><span class="n">A</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="mi">0</span><span class="p">);</span> <span class="n">Update</span><span class="p">(</span><span class="n">C</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="mi">0</span><span class="p">);</span> <span class="n">Update</span><span class="p">(</span><span class="n">A</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">a</span><span class="p">);</span> <span class="n">Update</span><span class="p">(</span><span class="n">A</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">b</span><span class="p">);</span> <span class="n">Update</span><span class="p">(</span><span class="n">B</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">b</span><span class="p">);</span> <span class="n">Update</span><span class="p">(</span><span class="n">C</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">c</span><span class="p">);</span> <span class="n">Update</span><span class="p">(</span><span class="n">C</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">d</span><span class="p">);</span> <span class="n">Update</span><span class="p">(</span><span class="n">D</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">d</span><span class="p">);</span> <span class="p">}</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">max</span><span class="p">({</span> <span class="n">Query</span><span class="p">(</span><span class="n">B</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="n">N</span><span class="p">),</span> <span class="n">Query</span><span class="p">(</span><span class="n">D</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="n">N</span><span class="p">),</span> <span class="mi">0</span> <span class="p">});</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/20039백준7538 Incomplete chess boards2021-01-14T22:36:00+00:002021-01-14T22:36:00+00:00https://justicehui.github.io/ps/2021/01/14/BOJ7538<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/7578</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>이분 매칭</li> </ul> <h3 id="풀이">풀이</h3> <p>격자 그래프는 이분 그래프입니다.<br /> Maximum Bipartite Matching이 Perfect Matching인지 확인하면 됩니다.</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">const</span> <span class="kt">int</span> <span class="n">di</span><span class="p">[]</span> <span class="o">=</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="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">};</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">dj</span><span class="p">[]</span> <span class="o">=</span> <span class="p">{</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</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="kr">inline</span> <span class="kt">int</span> <span class="nf">id</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="kt">int</span> <span class="n">j</span><span class="p">){</span> <span class="k">return</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">8</span> <span class="o">+</span> <span class="n">j</span><span class="p">;</span> <span class="p">}</span> <span class="k">namespace</span> <span class="n">BM</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">66</span><span class="p">];</span> <span class="kt">int</span> <span class="n">chk</span><span class="p">[</span><span class="mi">66</span><span class="p">],</span> <span class="n">par</span><span class="p">[</span><span class="mi">66</span><span class="p">],</span> <span class="n">pv</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">66</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="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">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="n">pv</span> <span class="o">=</span> <span class="mi">0</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">bool</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="n">chk</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">pv</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="o">==</span> <span class="n">pv</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="n">pv</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="nb">true</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">Run</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">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">8</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="mi">8</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">&amp;</span> <span class="mi">1</span><span class="p">)</span> <span class="n">pv</span><span class="o">++</span><span class="p">,</span> <span class="n">ret</span> <span class="o">+=</span> <span class="n">DFS</span><span class="p">(</span><span class="n">id</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">ret</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">N</span> <span class="o">=</span> <span class="mi">8</span><span class="p">;</span> <span class="kt">bool</span> <span class="n">Block</span><span class="p">[</span><span class="mi">9</span><span class="p">][</span><span class="mi">9</span><span class="p">];</span> <span class="kt">void</span> <span class="nf">Solve</span><span class="p">(){</span> <span class="n">BM</span><span class="o">::</span><span class="n">Clear</span><span class="p">();</span> <span class="kt">int</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="n">d</span><span class="p">;</span> <span class="n">cin</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="o">&gt;&gt;</span> <span class="n">c</span> <span class="o">&gt;&gt;</span> <span class="n">d</span><span class="p">;</span> <span class="n">Block</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="o">=</span> <span class="n">Block</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="o">=</span> <span class="nb">true</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="p">{</span> <span class="k">if</span><span class="p">(</span><span class="n">Block</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">continue</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="mi">4</span><span class="p">;</span> <span class="n">k</span><span class="o">++</span><span class="p">){</span> <span class="kt">int</span> <span class="n">ii</span> <span class="o">=</span> <span class="n">i</span> <span class="o">+</span> <span class="n">di</span><span class="p">[</span><span class="n">k</span><span class="p">],</span> <span class="n">jj</span> <span class="o">=</span> <span class="n">j</span> <span class="o">+</span> <span class="n">dj</span><span class="p">[</span><span class="n">k</span><span class="p">];</span> <span class="k">if</span><span class="p">(</span><span class="n">ii</span> <span class="o">&lt;</span> <span class="mi">1</span> <span class="o">||</span> <span class="n">jj</span> <span class="o">&lt;</span> <span class="mi">1</span> <span class="o">||</span> <span class="n">ii</span> <span class="o">&gt;</span> <span class="n">N</span> <span class="o">||</span> <span class="n">jj</span> <span class="o">&gt;</span> <span class="n">N</span> <span class="o">||</span> <span class="n">Block</span><span class="p">[</span><span class="n">ii</span><span class="p">][</span><span class="n">jj</span><span class="p">])</span> <span class="k">continue</span><span class="p">;</span> <span class="n">BM</span><span class="o">::</span><span class="n">AddEdge</span><span class="p">(</span><span class="n">id</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">id</span><span class="p">(</span><span class="n">ii</span><span class="p">,</span> <span class="n">jj</span><span class="p">));</span> <span class="p">}</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">res</span> <span class="o">=</span> <span class="n">BM</span><span class="o">::</span><span class="n">Run</span><span class="p">()</span> <span class="o">==</span> <span class="mi">31</span><span class="p">;</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">res</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">Block</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="o">=</span> <span class="n">Block</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="o">=</span> <span class="nb">false</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">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">tc</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">tc</span><span class="o">&lt;=</span><span class="n">T</span><span class="p">;</span> <span class="n">tc</span><span class="o">++</span><span class="p">){</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">"Scenario #"</span> <span class="o">&lt;&lt;</span> <span class="n">tc</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">Solve</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> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/7578백준2080 겹치는 선분2021-01-14T22:33:00+00:002021-01-14T22:33:00+00:00https://justicehui.github.io/ps/2021/01/14/BOJ2080<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/2080</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>CCW</li> </ul> <h3 id="풀이">풀이</h3> <p>선분/직선은 $y = ax + b$로 표현할 수 있고, 두 선분의 $a, b$가 <strong>모두 같은 경우</strong>에만 두 직선이 겹칠 수 있습니다.<br /> 주어진 선분을 $a, b$ 값 별로 나눈 다음, 각각에 대해 독립적으로 문제를 해결해도 충분합니다.<br /> 간단한 스위핑을 통해 문제를 해결할 수 있습니다.</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() </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">struct</span> <span class="nc">Line</span><span class="p">{</span> <span class="n">ll</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">xx</span><span class="p">,</span> <span class="n">yy</span><span class="p">;</span> <span class="n">Line</span><span class="p">()</span> <span class="o">=</span> <span class="k">default</span><span class="p">;</span> <span class="n">Line</span><span class="p">(</span><span class="n">ll</span> <span class="n">x</span><span class="p">,</span> <span class="n">ll</span> <span class="n">y</span><span class="p">,</span> <span class="n">ll</span> <span class="n">xx</span><span class="p">,</span> <span class="n">ll</span> <span class="n">yy</span><span class="p">)</span> <span class="o">:</span> <span class="n">x</span><span class="p">(</span><span class="n">x</span><span class="p">),</span> <span class="n">y</span><span class="p">(</span><span class="n">y</span><span class="p">),</span> <span class="n">xx</span><span class="p">(</span><span class="n">xx</span><span class="p">),</span> <span class="n">yy</span><span class="p">(</span><span class="n">yy</span><span class="p">)</span> <span class="p">{}</span> <span class="kt">bool</span> <span class="k">operator</span> <span class="o">&lt;</span> <span class="p">(</span><span class="k">const</span> <span class="n">Line</span> <span class="o">&amp;</span><span class="n">t</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span> <span class="k">if</span><span class="p">(</span><span class="n">tie</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">)</span> <span class="o">!=</span> <span class="n">tie</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">t</span><span class="p">.</span><span class="n">y</span><span class="p">))</span> <span class="k">return</span> <span class="n">tie</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">)</span> <span class="o">&lt;</span> <span class="n">tie</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">t</span><span class="p">.</span><span class="n">y</span><span class="p">);</span> <span class="k">return</span> <span class="n">tie</span><span class="p">(</span><span class="n">xx</span><span class="p">,</span> <span class="n">yy</span><span class="p">)</span> <span class="o">&gt;</span> <span class="n">tie</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">xx</span><span class="p">,</span> <span class="n">t</span><span class="p">.</span><span class="n">yy</span><span class="p">);</span> <span class="p">}</span> <span class="p">};</span> <span class="k">struct</span> <span class="nc">LineCompare</span><span class="p">{</span> <span class="n">ll</span> <span class="n">a1</span><span class="p">,</span> <span class="n">a2</span><span class="p">,</span> <span class="n">b1</span><span class="p">,</span> <span class="n">b2</span><span class="p">;</span> <span class="c1">// y = (a1/a2)x + (b1/b2)</span> <span class="kt">int</span> <span class="n">flag</span><span class="p">;</span> <span class="c1">// 0: normal, 1: dx=0, 2: dy=0, 3: dx=dy=0</span> <span class="n">LineCompare</span><span class="p">()</span> <span class="o">=</span> <span class="k">default</span><span class="p">;</span> <span class="n">LineCompare</span><span class="p">(</span><span class="n">ll</span> <span class="n">a1</span><span class="p">,</span> <span class="n">ll</span> <span class="n">a2</span><span class="p">,</span> <span class="n">ll</span> <span class="n">b1</span><span class="p">,</span> <span class="n">ll</span> <span class="n">b2</span><span class="p">,</span> <span class="kt">int</span> <span class="n">flag</span><span class="p">)</span> <span class="o">:</span> <span class="n">a1</span><span class="p">(</span><span class="n">a1</span><span class="p">),</span> <span class="n">a2</span><span class="p">(</span><span class="n">a2</span><span class="p">),</span> <span class="n">b1</span><span class="p">(</span><span class="n">b1</span><span class="p">),</span> <span class="n">b2</span><span class="p">(</span><span class="n">b2</span><span class="p">),</span> <span class="n">flag</span><span class="p">(</span><span class="n">flag</span><span class="p">)</span> <span class="p">{}</span> <span class="kt">bool</span> <span class="k">operator</span> <span class="o">&lt;</span> <span class="p">(</span><span class="k">const</span> <span class="n">LineCompare</span> <span class="o">&amp;</span><span class="n">t</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span> <span class="k">return</span> <span class="n">tie</span><span class="p">(</span><span class="n">a1</span><span class="p">,</span> <span class="n">a2</span><span class="p">,</span> <span class="n">b1</span><span class="p">,</span> <span class="n">b2</span><span class="p">,</span> <span class="n">flag</span><span class="p">)</span> <span class="o">&lt;</span> <span class="n">tie</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">a1</span><span class="p">,</span> <span class="n">t</span><span class="p">.</span><span class="n">a2</span><span class="p">,</span> <span class="n">t</span><span class="p">.</span><span class="n">b1</span><span class="p">,</span> <span class="n">t</span><span class="p">.</span><span class="n">b2</span><span class="p">,</span> <span class="n">t</span><span class="p">.</span><span class="n">flag</span><span class="p">);</span> <span class="p">}</span> <span class="p">};</span> <span class="k">struct</span> <span class="nc">Event</span><span class="p">{</span> <span class="n">ll</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">;</span> <span class="kt">int</span> <span class="n">v</span><span class="p">;</span> <span class="n">Event</span><span class="p">()</span> <span class="o">=</span> <span class="k">default</span><span class="p">;</span> <span class="n">Event</span><span class="p">(</span><span class="n">ll</span> <span class="n">x</span><span class="p">,</span> <span class="n">ll</span> <span class="n">y</span><span class="p">,</span> <span class="kt">int</span> <span class="n">v</span><span class="p">)</span> <span class="o">:</span> <span class="n">x</span><span class="p">(</span><span class="n">x</span><span class="p">),</span> <span class="n">y</span><span class="p">(</span><span class="n">y</span><span class="p">),</span> <span class="n">v</span><span class="p">(</span><span class="n">v</span><span class="p">)</span> <span class="p">{}</span> <span class="kt">bool</span> <span class="k">operator</span> <span class="o">&lt;</span> <span class="p">(</span><span class="k">const</span> <span class="n">Event</span> <span class="o">&amp;</span><span class="n">t</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span> <span class="k">return</span> <span class="n">tie</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">v</span><span class="p">)</span> <span class="o">&lt;</span> <span class="n">tie</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">t</span><span class="p">.</span><span class="n">y</span><span class="p">,</span> <span class="n">t</span><span class="p">.</span><span class="n">v</span><span class="p">);</span> <span class="p">}</span> <span class="p">};</span> <span class="n">LineCompare</span> <span class="nf">Get</span><span class="p">(</span><span class="k">const</span> <span class="n">Line</span> <span class="o">&amp;</span><span class="n">line</span><span class="p">){</span> <span class="n">ll</span> <span class="n">dx</span> <span class="o">=</span> <span class="n">line</span><span class="p">.</span><span class="n">xx</span> <span class="o">-</span> <span class="n">line</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">line</span><span class="p">.</span><span class="n">yy</span> <span class="o">-</span> <span class="n">line</span><span class="p">.</span><span class="n">y</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">dx</span> <span class="o">==</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">dy</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="k">return</span> <span class="p">{</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">3</span><span class="p">};</span> <span class="k">if</span><span class="p">(</span><span class="n">dy</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="k">return</span> <span class="p">{</span><span class="n">line</span><span class="p">.</span><span class="n">y</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">2</span><span class="p">};</span> <span class="k">if</span><span class="p">(</span><span class="n">dx</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="k">return</span> <span class="p">{</span><span class="n">line</span><span class="p">.</span><span class="n">x</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">};</span> <span class="n">ll</span> <span class="n">a1</span> <span class="o">=</span> <span class="n">dy</span><span class="p">,</span> <span class="n">a2</span> <span class="o">=</span> <span class="n">dx</span><span class="p">;</span> <span class="n">ll</span> <span class="n">b1</span> <span class="o">=</span> <span class="n">line</span><span class="p">.</span><span class="n">xx</span> <span class="o">*</span> <span class="n">line</span><span class="p">.</span><span class="n">y</span> <span class="o">-</span> <span class="n">line</span><span class="p">.</span><span class="n">x</span> <span class="o">*</span> <span class="n">line</span><span class="p">.</span><span class="n">yy</span><span class="p">,</span> <span class="n">b2</span> <span class="o">=</span> <span class="n">dx</span><span class="p">;</span> <span class="n">ll</span> <span class="n">ga</span> <span class="o">=</span> <span class="n">__gcd</span><span class="p">(</span><span class="n">a1</span><span class="p">,</span> <span class="n">a2</span><span class="p">),</span> <span class="n">gb</span> <span class="o">=</span> <span class="n">__gcd</span><span class="p">(</span><span class="n">b1</span><span class="p">,</span> <span class="n">b2</span><span class="p">);</span> <span class="n">a1</span> <span class="o">/=</span> <span class="n">ga</span><span class="p">;</span> <span class="n">a2</span> <span class="o">/=</span> <span class="n">ga</span><span class="p">;</span> <span class="n">b1</span> <span class="o">/=</span> <span class="n">gb</span><span class="p">;</span> <span class="n">b2</span> <span class="o">/=</span> <span class="n">gb</span><span class="p">;</span> <span class="k">return</span> <span class="p">{</span><span class="n">a1</span><span class="p">,</span> <span class="n">a2</span><span class="p">,</span> <span class="n">b1</span><span class="p">,</span> <span class="n">b2</span><span class="p">,</span> <span class="mi">0</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">Line</span> <span class="n">A</span><span class="p">[</span><span class="mi">101010</span><span class="p">];</span> <span class="n">map</span><span class="o">&lt;</span><span class="n">LineCompare</span><span class="p">,</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">Line</span><span class="o">&gt;&gt;</span> <span class="n">mp</span><span class="p">;</span> <span class="n">ll</span> <span class="n">ans</span><span class="p">;</span> <span class="kt">void</span> <span class="nf">Solve</span><span class="p">(</span><span class="k">const</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">Line</span><span class="o">&gt;</span> <span class="o">&amp;</span><span class="n">v</span><span class="p">,</span> <span class="k">const</span> <span class="n">LineCompare</span> <span class="o">&amp;</span><span class="n">com</span><span class="p">){</span> <span class="kt">bool</span> <span class="n">useY</span> <span class="o">=</span> <span class="n">com</span><span class="p">.</span><span class="n">flag</span> <span class="o">==</span> <span class="mi">2</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">Event</span><span class="o">&gt;</span> <span class="n">event</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="n">event</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="n">x</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="mi">1</span><span class="p">);</span> <span class="n">event</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="n">xx</span><span class="p">,</span> <span class="n">i</span><span class="p">.</span><span class="n">yy</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">);</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">event</span><span class="p">));</span> <span class="n">ll</span> <span class="n">acc</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">const</span> <span class="k">auto</span> <span class="o">&amp;</span><span class="n">i</span> <span class="o">:</span> <span class="n">event</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span><span class="p">.</span><span class="n">v</span> <span class="o">==</span> <span class="mi">1</span><span class="p">)</span> <span class="n">ans</span> <span class="o">+=</span> <span class="n">acc</span><span class="p">;</span> <span class="n">acc</span> <span class="o">+=</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="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="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">x</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">y</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">xx</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">yy</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">tie</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">x</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">y</span><span class="p">)</span> <span class="o">&gt;</span> <span class="n">tie</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">xx</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">yy</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">x</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">xx</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">y</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">yy</span><span class="p">);</span> <span class="p">}</span> <span class="n">mp</span><span class="p">[</span><span class="n">Get</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">push_back</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="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">v</span> <span class="o">:</span> <span class="n">mp</span><span class="p">)</span> <span class="n">Solve</span><span class="p">(</span><span class="n">v</span><span class="p">.</span><span class="n">second</span><span class="p">,</span> <span class="n">v</span><span class="p">.</span><span class="n">first</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/2080백준9866 Vacation Planning2021-01-14T22:29:00+00:002021-01-14T22:29:00+00:00https://justicehui.github.io/usaco/2021/01/14/BOJ9866<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/9866</li> </ul> <h3 id="문제-출처">문제 출처</h3> <ul> <li>2013 USACO December Gold 1번</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>다익스트라</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(MK \log N + KQ)$</li> </ul> <h3 id="풀이">풀이</h3> <p>허브의 개수 $K$가 작으므로, (어떤 정점에서 각 허브로 가는 최소 비용)과 (각 허브에서 다른 정점으로 가는 최소 비용)을 각각 전처리하면 된다는 생각을 해볼 수 있습니다.<br /> 이 값들을 알고 있으면 (시작점에서 어떤 허브로 가는 최소 비용) + (어떤 허브에서 끝점으로 가는 최소 비용) 중 최솟값이 정답이 됩니다.</p> <p>각 허브에서 다른 정점으로 가는 최소 비용은 단순히 다익스트라 알고리즘을 $K$번 돌리면 됩니다. 마찬가지로, 어떤 정점에서 각 허브로 가는 것은 그래프의 간선 방향을 반대로 뒤집고 다익스트라 알고리즘을 돌리면 됩니다.</p> <p>$O(M \log N)$ 다익스트라를 $K$번 돌려서 전처리하면, 쿼리에 대한 정답은 $O(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="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">pll</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="n">Q</span><span class="p">,</span> <span class="n">H</span><span class="p">[</span><span class="mi">222</span><span class="p">];</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">pll</span><span class="o">&gt;</span> <span class="n">G</span><span class="p">[</span><span class="mi">20202</span><span class="p">],</span> <span class="n">R</span><span class="p">[</span><span class="mi">20202</span><span class="p">];</span> <span class="n">ll</span> <span class="n">D</span><span class="p">[</span><span class="mi">222</span><span class="p">][</span><span class="mi">2</span><span class="p">][</span><span class="mi">20202</span><span class="p">];</span> <span class="kt">void</span> <span class="nf">Dijkstra</span><span class="p">(</span><span class="kt">int</span> <span class="n">st</span><span class="p">,</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">pll</span><span class="o">&gt;</span> <span class="o">*</span><span class="n">g</span><span class="p">,</span> <span class="n">ll</span> <span class="o">*</span><span class="n">dst</span><span class="p">){</span> <span class="n">priority_queue</span><span class="o">&lt;</span><span class="n">pll</span><span class="o">&gt;</span> <span class="n">pq</span><span class="p">;</span> <span class="n">pq</span><span class="p">.</span><span class="n">emplace</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="n">st</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="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">pq</span><span class="p">.</span><span class="n">size</span><span class="p">()){</span> <span class="n">ll</span> <span class="n">v</span> <span class="o">=</span> <span class="n">pq</span><span class="p">.</span><span class="n">top</span><span class="p">().</span><span class="n">y</span><span class="p">,</span> <span class="n">c</span> <span class="o">=</span> <span class="o">-</span><span class="n">pq</span><span class="p">.</span><span class="n">top</span><span class="p">().</span><span class="n">x</span><span class="p">;</span> <span class="n">pq</span><span class="p">.</span><span class="n">pop</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">dst</span><span class="p">[</span><span class="n">v</span><span class="p">])</span> <span class="k">continue</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">dst</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="o">&gt;</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="n">i</span><span class="p">.</span><span class="n">y</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="n">x</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="n">i</span><span class="p">.</span><span class="n">y</span><span class="p">;</span> <span class="n">pq</span><span class="p">.</span><span class="n">emplace</span><span class="p">(</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">x</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="p">}</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="o">&gt;&gt;</span> <span class="n">K</span> <span class="o">&gt;&gt;</span> <span class="n">Q</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="n">ll</span> <span class="n">s</span><span class="p">,</span> <span class="n">e</span><span class="p">,</span> <span class="n">x</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="o">&gt;&gt;</span> <span class="n">x</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">emplace_back</span><span class="p">(</span><span class="n">e</span><span class="p">,</span> <span class="n">x</span><span class="p">);</span> <span class="n">R</span><span class="p">[</span><span class="n">e</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">x</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">K</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">H</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="n">memset</span><span class="p">(</span><span class="n">D</span><span class="p">,</span> <span class="mh">0x3f</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">D</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">K</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">Dijkstra</span><span class="p">(</span><span class="n">H</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">G</span><span class="p">,</span> <span class="n">D</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">Dijkstra</span><span class="p">(</span><span class="n">H</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">R</span><span class="p">,</span> <span class="n">D</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="n">ll</span> <span class="n">cnt</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</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="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">Q</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">ll</span> <span class="n">mn</span> <span class="o">=</span> <span class="mh">0x3f3f3f3f3f3f3f3f</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">K</span><span class="p">;</span> <span class="n">j</span><span class="o">++</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">D</span><span class="p">[</span><span class="n">j</span><span class="p">][</span><span class="mi">1</span><span class="p">][</span><span class="n">s</span><span class="p">]</span> <span class="o">+</span> <span class="n">D</span><span class="p">[</span><span class="n">j</span><span class="p">][</span><span class="mi">0</span><span class="p">][</span><span class="n">e</span><span class="p">]);</span> <span class="k">if</span><span class="p">(</span><span class="n">mn</span> <span class="o">&lt;</span> <span class="mf">1e18</span><span class="p">)</span> <span class="n">cnt</span><span class="o">++</span><span class="p">,</span> <span class="n">sum</span> <span class="o">+=</span> <span class="n">mn</span><span class="p">;</span> <span class="p">}</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">cnt</span> <span class="o">&lt;&lt;</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span> <span class="o">&lt;&lt;</span> <span class="n">sum</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/9866백준7610 Synchronization2021-01-14T22:22:00+00:002021-01-14T22:22:00+00:00https://justicehui.github.io/joioc/2021/01/14/BOJ7610<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/7610</li> </ul> <h3 id="문제-출처">문제 출처</h3> <ul> <li>2013 JOI Open Contest 2번</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>Link Cut Tree</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O((M+Q) \log N)$</li> </ul> <h3 id="풀이">풀이</h3> <p>간선 제거 쿼리가 없는 문제를 생각해봅시다.<br /> 각 컴포넌트의 “정답”을 루트 정점에 저장하면서, 간선이 추가될 때마다 Union-Find를 이용해 컴포넌트를 합치면 됩니다. 이때 각 컴포넌트의 “정답”은 단순히 컴포넌트의 크기가 됩니다.</p> <p>간선을 끊는다면? <strong>“Link Cut Tree를 쓰면 된다!”</strong> 라는 단순하고 명쾌한 해답을 찾을 수 있습니다. Union-Find처럼 각 컴포넌트의 “정답”을 루트 정점에서 관리하면 됩니다.</p> <p>하지만 간선을 끊는 쿼리와 연결하는 쿼리가 여러 번 주어지면, 두 컴포넌트를 합칠 때 정보의 교집합이 생길 수 있습니다. 이는 트리의 간선이 연결하는 정점 쌍이 바뀌지 않기 때문에 쉽게 처리할 수 있습니다.<br /> 간선 $E = (u, v)$가 <strong>마지막으로 끊어지기 직전의</strong> 컴포넌트 크기 $S(E)$를 알고 있다면, $E$가 다시 트리에 추가될 때 해당 컴포넌트의 “정답”은 $Ans(u)+Ans(v)-S(E)$가 됩니다.</p> <p>간선을 끊고 붙이고 루트 정점을 구하는 연산은 모두 Link Cut Tree를 이용해 amortized $O(\log N)$에 처리할 수 있습니다.</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">struct</span> <span class="nc">Node</span><span class="p">{</span> <span class="n">Node</span> <span class="o">*</span><span class="n">l</span><span class="p">,</span> <span class="o">*</span><span class="n">r</span><span class="p">,</span> <span class="o">*</span><span class="n">p</span><span class="p">;</span> <span class="kt">int</span> <span class="n">val</span><span class="p">;</span> <span class="n">Node</span><span class="p">()</span> <span class="o">:</span> <span class="n">Node</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span> <span class="p">{}</span> <span class="n">Node</span><span class="p">(</span><span class="kt">int</span> <span class="n">val</span><span class="p">)</span> <span class="o">:</span> <span class="n">l</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">),</span> <span class="n">r</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">),</span> <span class="n">p</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">),</span> <span class="n">val</span><span class="p">(</span><span class="n">val</span><span class="p">)</span> <span class="p">{}</span> <span class="kt">bool</span> <span class="n">IsLeft</span><span class="p">()</span> <span class="k">const</span> <span class="p">{</span> <span class="k">return</span> <span class="k">this</span> <span class="o">==</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">l</span><span class="p">;</span> <span class="p">}</span> <span class="kt">bool</span> <span class="n">IsRoot</span><span class="p">()</span> <span class="k">const</span> <span class="p">{</span> <span class="k">return</span> <span class="o">!</span><span class="n">p</span> <span class="o">||</span> <span class="p">(</span><span class="n">p</span><span class="o">-&gt;</span><span class="n">l</span> <span class="o">!=</span> <span class="k">this</span> <span class="o">&amp;&amp;</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">r</span> <span class="o">!=</span> <span class="k">this</span><span class="p">);</span> <span class="p">}</span> <span class="kt">void</span> <span class="n">Rotate</span><span class="p">(){</span> <span class="k">if</span><span class="p">(</span><span class="n">IsRoot</span><span class="p">())</span> <span class="k">return</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">IsLeft</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">r</span><span class="o">-&gt;</span><span class="n">p</span> <span class="o">=</span> <span class="n">p</span><span class="p">;</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">l</span> <span class="o">=</span> <span class="n">r</span><span class="p">;</span> <span class="n">r</span> <span class="o">=</span> <span class="n">p</span><span class="p">;</span> <span class="p">}</span> <span class="k">else</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">l</span><span class="o">-&gt;</span><span class="n">p</span> <span class="o">=</span> <span class="n">p</span><span class="p">;</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">r</span> <span class="o">=</span> <span class="n">l</span><span class="p">;</span> <span class="n">l</span> <span class="o">=</span> <span class="n">p</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">p</span><span class="o">-&gt;</span><span class="n">IsRoot</span><span class="p">())</span> <span class="p">(</span><span class="n">p</span><span class="o">-&gt;</span><span class="n">IsLeft</span><span class="p">()</span> <span class="o">?</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">p</span><span class="o">-&gt;</span><span class="n">l</span> <span class="o">:</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">p</span><span class="o">-&gt;</span><span class="n">r</span><span class="p">)</span> <span class="o">=</span> <span class="k">this</span><span class="p">;</span> <span class="k">auto</span> <span class="n">t</span> <span class="o">=</span> <span class="n">p</span><span class="p">;</span> <span class="n">p</span> <span class="o">=</span> <span class="n">t</span><span class="o">-&gt;</span><span class="n">p</span><span class="p">;</span> <span class="n">t</span><span class="o">-&gt;</span><span class="n">p</span> <span class="o">=</span> <span class="k">this</span><span class="p">;</span> <span class="p">}</span> <span class="p">};</span> <span class="kt">void</span> <span class="nf">Splay</span><span class="p">(</span><span class="n">Node</span> <span class="o">*</span><span class="n">x</span><span class="p">){</span> <span class="k">for</span><span class="p">(;</span> <span class="o">!</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">IsRoot</span><span class="p">();</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">Rotate</span><span class="p">()){</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">p</span><span class="o">-&gt;</span><span class="n">IsRoot</span><span class="p">()){</span> <span class="k">if</span><span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">IsLeft</span><span class="p">()</span> <span class="o">==</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">p</span><span class="o">-&gt;</span><span class="n">IsLeft</span><span class="p">())</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">p</span><span class="o">-&gt;</span><span class="n">Rotate</span><span class="p">();</span> <span class="k">else</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">Rotate</span><span class="p">();</span> <span class="p">}</span> <span class="p">}</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">Access</span><span class="p">(</span><span class="n">Node</span> <span class="o">*</span><span class="n">x</span><span class="p">){</span> <span class="n">Splay</span><span class="p">(</span><span class="n">x</span><span class="p">);</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">r</span> <span class="o">=</span> <span class="nb">nullptr</span><span class="p">;</span> <span class="k">for</span><span class="p">(;</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">p</span><span class="p">;</span> <span class="n">Splay</span><span class="p">(</span><span class="n">x</span><span class="p">))</span> <span class="n">Splay</span><span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">p</span><span class="p">),</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">p</span><span class="o">-&gt;</span><span class="n">r</span> <span class="o">=</span> <span class="n">x</span><span class="p">;</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">link</span><span class="p">(</span><span class="n">Node</span> <span class="o">*</span><span class="n">p</span><span class="p">,</span> <span class="n">Node</span> <span class="o">*</span><span class="n">c</span><span class="p">){</span> <span class="n">Access</span><span class="p">(</span><span class="n">c</span><span class="p">);</span> <span class="n">Access</span><span class="p">(</span><span class="n">p</span><span class="p">);</span> <span class="n">c</span><span class="o">-&gt;</span><span class="n">l</span> <span class="o">=</span> <span class="n">p</span><span class="p">;</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">p</span> <span class="o">=</span> <span class="n">c</span><span class="p">;</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">Cut</span><span class="p">(</span><span class="n">Node</span> <span class="o">*</span><span class="n">x</span><span class="p">){</span> <span class="n">Access</span><span class="p">(</span><span class="n">x</span><span class="p">);</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">l</span><span class="o">-&gt;</span><span class="n">p</span> <span class="o">=</span> <span class="nb">nullptr</span><span class="p">;</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">l</span> <span class="o">=</span> <span class="nb">nullptr</span><span class="p">;</span> <span class="p">}</span> <span class="n">Node</span><span class="o">*</span> <span class="nf">Root</span><span class="p">(</span><span class="n">Node</span> <span class="o">*</span><span class="n">x</span><span class="p">){</span> <span class="n">Access</span><span class="p">(</span><span class="n">x</span><span class="p">);</span> <span class="k">while</span><span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">l</span><span class="p">)</span> <span class="n">x</span> <span class="o">=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">l</span><span class="p">;</span> <span class="n">Access</span><span class="p">(</span><span class="n">x</span><span class="p">);</span> <span class="k">return</span> <span class="n">x</span><span class="p">;</span> <span class="p">}</span> <span class="n">Node</span><span class="o">*</span> <span class="nf">Par</span><span class="p">(</span><span class="n">Node</span> <span class="o">*</span><span class="n">x</span><span class="p">){</span> <span class="n">Access</span><span class="p">(</span><span class="n">x</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">l</span><span class="p">)</span> <span class="k">return</span> <span class="nb">nullptr</span><span class="p">;</span> <span class="n">x</span> <span class="o">=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">l</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">r</span><span class="p">)</span> <span class="n">x</span> <span class="o">=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">r</span><span class="p">;</span> <span class="n">Access</span><span class="p">(</span><span class="n">x</span><span class="p">);</span> <span class="k">return</span> <span class="n">x</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">Q</span><span class="p">;</span> <span class="kt">int</span> <span class="n">X</span><span class="p">[</span><span class="mi">202020</span><span class="p">],</span> <span class="n">Y</span><span class="p">[</span><span class="mi">202020</span><span class="p">];</span> <span class="n">Node</span> <span class="n">nd</span><span class="p">[</span><span class="mi">202020</span><span class="p">];</span> <span class="kt">bool</span> <span class="n">chk</span><span class="p">[</span><span class="mi">202020</span><span class="p">];</span> <span class="kt">int</span> <span class="n">sum</span><span class="p">[</span><span class="mi">202020</span><span class="p">];</span> <span class="kt">void</span> <span class="nf">On</span><span class="p">(</span><span class="kt">int</span> <span class="n">t</span><span class="p">){</span> <span class="kt">int</span> <span class="n">a</span> <span class="o">=</span> <span class="n">Root</span><span class="p">(</span><span class="n">nd</span> <span class="o">+</span> <span class="n">X</span><span class="p">[</span><span class="n">t</span><span class="p">])</span> <span class="o">-</span> <span class="n">nd</span><span class="p">;</span> <span class="kt">int</span> <span class="n">b</span> <span class="o">=</span> <span class="n">Root</span><span class="p">(</span><span class="n">nd</span> <span class="o">+</span> <span class="n">Y</span><span class="p">[</span><span class="n">t</span><span class="p">])</span> <span class="o">-</span> <span class="n">nd</span><span class="p">;</span> <span class="kt">int</span> <span class="n">now</span> <span class="o">=</span> <span class="n">nd</span><span class="p">[</span><span class="n">a</span><span class="p">].</span><span class="n">val</span> <span class="o">+</span> <span class="n">nd</span><span class="p">[</span><span class="n">b</span><span class="p">].</span><span class="n">val</span> <span class="o">-</span> <span class="n">sum</span><span class="p">[</span><span class="n">t</span><span class="p">];</span> <span class="n">link</span><span class="p">(</span><span class="n">nd</span> <span class="o">+</span> <span class="n">X</span><span class="p">[</span><span class="n">t</span><span class="p">],</span> <span class="n">nd</span> <span class="o">+</span> <span class="n">Y</span><span class="p">[</span><span class="n">t</span><span class="p">]);</span> <span class="n">a</span> <span class="o">=</span> <span class="n">Root</span><span class="p">(</span><span class="n">nd</span> <span class="o">+</span> <span class="n">X</span><span class="p">[</span><span class="n">t</span><span class="p">])</span> <span class="o">-</span> <span class="n">nd</span><span class="p">;</span> <span class="n">nd</span><span class="p">[</span><span class="n">a</span><span class="p">].</span><span class="n">val</span> <span class="o">=</span> <span class="n">now</span><span class="p">;</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">Off</span><span class="p">(</span><span class="kt">int</span> <span class="n">t</span><span class="p">){</span> <span class="kt">int</span> <span class="n">a</span> <span class="o">=</span> <span class="n">X</span><span class="p">[</span><span class="n">t</span><span class="p">],</span> <span class="n">b</span> <span class="o">=</span> <span class="n">Y</span><span class="p">[</span><span class="n">t</span><span class="p">];</span> <span class="kt">int</span> <span class="n">rt</span> <span class="o">=</span> <span class="n">Root</span><span class="p">(</span><span class="n">nd</span> <span class="o">+</span> <span class="n">a</span><span class="p">)</span> <span class="o">-</span> <span class="n">nd</span><span class="p">;</span> <span class="kt">int</span> <span class="n">now</span> <span class="o">=</span> <span class="n">nd</span><span class="p">[</span><span class="n">rt</span><span class="p">].</span><span class="n">val</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">nd</span> <span class="o">+</span> <span class="n">a</span><span class="p">)</span> <span class="o">-</span> <span class="n">nd</span> <span class="o">==</span> <span class="n">b</span><span class="p">)</span> <span class="n">Cut</span><span class="p">(</span><span class="n">nd</span> <span class="o">+</span> <span class="n">a</span><span class="p">);</span> <span class="k">else</span> <span class="n">Cut</span><span class="p">(</span><span class="n">nd</span> <span class="o">+</span> <span class="n">b</span><span class="p">);</span> <span class="n">sum</span><span class="p">[</span><span class="n">t</span><span class="p">]</span> <span class="o">=</span> <span class="n">now</span><span class="p">;</span> <span class="n">a</span> <span class="o">=</span> <span class="n">Root</span><span class="p">(</span><span class="n">nd</span> <span class="o">+</span> <span class="n">a</span><span class="p">)</span> <span class="o">-</span> <span class="n">nd</span><span class="p">;</span> <span class="n">b</span> <span class="o">=</span> <span class="n">Root</span><span class="p">(</span><span class="n">nd</span> <span class="o">+</span> <span class="n">b</span><span class="p">)</span> <span class="o">-</span> <span class="n">nd</span><span class="p">;</span> <span class="n">nd</span><span class="p">[</span><span class="n">a</span><span class="p">].</span><span class="n">val</span> <span class="o">=</span> <span class="n">nd</span><span class="p">[</span><span class="n">b</span><span class="p">].</span><span class="n">val</span> <span class="o">=</span> <span class="n">now</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">Q</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">X</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&gt;&gt;</span> <span class="n">Y</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">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="n">chk</span><span class="p">[</span><span class="n">t</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">chk</span><span class="p">[</span><span class="n">t</span><span class="p">])</span> <span class="n">On</span><span class="p">(</span><span class="n">t</span><span class="p">);</span> <span class="k">else</span> <span class="n">Off</span><span class="p">(</span><span class="n">t</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">Q</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">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="kt">int</span> <span class="n">rt</span> <span class="o">=</span> <span class="n">Root</span><span class="p">(</span><span class="n">nd</span> <span class="o">+</span> <span class="n">t</span><span class="p">)</span> <span class="o">-</span> <span class="n">nd</span><span class="p">;</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">nd</span><span class="p">[</span><span class="n">rt</span><span class="p">].</span><span class="n">val</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="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/7610백준20188 등산 마니아2021-01-14T17:53:00+00:002021-01-14T17:53:00+00:00https://justicehui.github.io/koi/2021/01/14/BOJ20188<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/20188</li> </ul> <h3 id="문제-출처">문제 출처</h3> <ul> <li>2020 KOI 2차 초등부 3번</li> <li>2020 KOI 2차 중등부 2번</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>트리 DP</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(N)$</li> </ul> <h3 id="풀이">풀이</h3> <p><strong>모든 경로 길이의 합</strong>과 <strong>루트에서 어떤 두 정점의 LCA로 가는 경로</strong>로 나눠서 생각합니다.</p> <p>모든 경로 길이의 합은 <strong>각 간선이 사용되는 횟수</strong>를 구해서 모두 더해주면 됩니다.<br /> 정점 $p, c$($p$가 부모 정점)를 연결하는 간선 $(p, c)$가 사용되는 횟수는 $S_c \cdot (N-S_c)$입니다.(단, $S_v$는 $v$를 루트로 하는 서브 트리의 크기)</p> <p><strong>루트에서 어떤 두 정점의 LCA로 가는 경로의 길이 합</strong>은 각 정점이 LCA가 되는 경우의 수를 구하면 됩니다. 정점 $p$의 자식들을 각각 $c_1, c_2, \cdots , c_k$라고 할 때, 정점 $p$가 LCA가 되는 경우의 수는 ${S_p \choose 2} - \sum_{i=1}^{k} {S_{c_i} \choose 2}$입니다.</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">S</span><span class="p">[</span><span class="mi">303030</span><span class="p">],</span> <span class="n">D</span><span class="p">[</span><span class="mi">303030</span><span class="p">],</span> <span class="n">P</span><span class="p">[</span><span class="mi">303030</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">303030</span><span class="p">];</span> <span class="n">ll</span> <span class="n">R</span><span class="p">;</span> <span class="n">ll</span> <span class="nf">C2</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="mi">1LL</span> <span class="o">*</span> <span class="n">x</span> <span class="o">*</span> <span class="p">(</span><span class="n">x</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> <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="kt">int</span> <span class="n">b</span> <span class="o">=</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">v</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">P</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">b</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="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">b</span><span class="p">)</span> <span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">D</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">S</span><span class="p">[</span><span class="n">v</span><span class="p">]</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="n">v</span><span class="p">);</span> <span class="k">return</span> <span class="n">S</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">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">DFS</span><span class="p">(</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="n">R</span> <span class="o">+=</span> <span class="mi">1LL</span> <span class="o">*</span> <span class="n">S</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">N</span> <span class="o">-</span> <span class="n">S</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">ll</span> <span class="n">now</span> <span class="o">=</span> <span class="n">C2</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="k">for</span><span class="p">(</span><span class="k">const</span> <span class="k">auto</span> <span class="n">j</span> <span class="o">:</span> <span class="n">G</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">j</span> <span class="o">!=</span> <span class="n">P</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">now</span> <span class="o">-=</span> <span class="n">C2</span><span class="p">(</span><span class="n">S</span><span class="p">[</span><span class="n">j</span><span class="p">]);</span> <span class="n">R</span> <span class="o">+=</span> <span class="n">now</span> <span class="o">*</span> <span class="n">D</span><span class="p">[</span><span class="n">i</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="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/20188