Submission #19155

#TimeUsernameProblemLanguageResultExecution timeMemory
19155kdh9949두 섬간의 연결 (kriii1_2)C++98
0 / 1
39 ms1992 KiB
#include <cstdio> #include <algorithm> typedef long long ll; struct DisjSet{ int par[100010]; int sz[100010]; DisjSet(int n){ for(int i = 1; i <= n; i++) par[i] = i, sz[i] = 1; } int Find(int a){ if(par[a] == a) return a; return par[a] = Find(par[a]); } void Union(int a, int b){ sz[Find(b)] += sz[Find(a)]; par[Find(a)] = Find(b); } }; ll ans1, ans2; int n, c; ll a, b; DisjSet *DS; ll f1(ll x){ return x * (x - 1) / 2; } ll f2(int x){ return x * (x - 1) * (x + 1) / 6; } int main(){ scanf("%d", &n); DS = new DisjSet(n); for(int i = 0; i < n - 1; i++){ scanf("%d", &c); a = DS -> sz[DS -> Find(c)]; b = DS -> sz[DS -> Find(c + 1)]; ans1 -= f1(a) + f1(b); ans2 -= f2(a) + f2(b); DS -> Union(c, c + 1); ans1 += f1(a + b); ans2 += f2(a + b); printf("%lld %lld\n", ans1, ans2); } }
#Verdict Execution timeMemoryGrader output
Fetching results...