# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
211871 | 2020-03-21T14:46:41 Z | Akashi | 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) | C++14 | 16 ms | 19072 KB |
#include <bits/stdc++.h> using namespace std; int n, m; int TT[100001], SZ[100001]; set <int> in[100001], out[100001], bridge[100001], elem[100001]; long long Sol = 0; inline int find(int x){ if(x != TT[x]) return (TT[x] = find(TT[x])); return x; } inline void unite(int x, int y){ if(x == y) return ; if(elem[x].size() + in[x].size() + out[x].size() + bridge[x].size() < in[y].size() + out[y].size() + bridge[y].size() + elem[y].size()) swap(x, y); Sol += 2LL * SZ[x] * SZ[y]; for(auto it : bridge[y]) if(elem[x].count(it)) Sol = Sol - SZ[y]; for(auto it : elem[y]) if(bridge[x].count(it)) Sol = Sol - SZ[x]; for(auto it : bridge[y]) if(!bridge[x].count(it) && !elem[x].count(it)) Sol = Sol + SZ[x]; int nr = bridge[x].size(); for(auto it : bridge[y]) if(bridge[x].count(it)) --nr; for(auto it : elem[y]) if(bridge[x].count(it)) --nr; Sol = Sol + 1LL * SZ[y] * nr; for(auto it : elem[y]){ elem[x].insert(it); if(bridge[x].count(it)) bridge[x].erase(it); } for(auto it : in[y]) if(it != x) in[x].insert(it); for(auto it : out[y]) if(it != x) out[x].insert(it); for(auto it : bridge[y]) if(find(it) != x) bridge[x].insert(it); SZ[x] += SZ[y]; TT[y] = x; for(auto it : in[y]){ if(out[x].count(it)){ unite(x, find(it)); x = find(x); } } for(auto it : out[y]){ if(in[x].count(it)){ unite(x, find(it)); x = find(x); } } } int main() { freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); scanf("%d%d", &n, &m); for(int i = 1; i <= n ; ++i){ TT[i] = i, SZ[i] = 1; elem[i].insert(i); } int x, y, fx, fy; for(int i = 1; i <= m ; ++i){ scanf("%d%d", &x, &y); fx = x; fy = y; x = find(x); y = find(y); if(x == y){ printf("%lld\n", Sol); continue ; } if(!bridge[y].count(fx)){ out[x].insert(y); in[y].insert(x); bridge[y].insert(fx); Sol += SZ[y]; if(in[x].count(y)) unite(x, y); } printf("%lld\n", Sol); } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 16 ms | 19072 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 16 ms | 19072 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 16 ms | 19072 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |