探索やるだけ。に見えて定数倍重いので普通にやるとTLEする。 setとか使って謎の枝狩りを仕込む。こんな枝狩り見たことないなぁ。 TLEぎりぎりで通る。 #include<stdio.h> #include "stdafx.h" #include<algorithm> #include<vector> #include<queue> #include<set> using namespace std; int main() </set></queue></vector></algorithm></stdio.h>…

どう見てもデータ構造ゲー。とりあえずグループにするということでUnion-findをつくる。 BITでもつかって「n匹以下が属するグループ数」の累積和をもっといてやると通る。 オーダーはO(m log^2 n)。 #include<stdio.h> #include<vector> #include<algorithm> int par[200000]; int ran[20</algorithm></vector></stdio.h>…