# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
211854 | Akashi | 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) | C++14 | 15 ms | 19072 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 += 1LL * SZ[x] * SZ[y];
for(auto it : in[y]) if(!bridge[x].count(it) && find(it) != x) Sol += SZ[x];
int vec = bridge[x].size();
for(auto it : bridge[y]){
if(bridge[x].count(it)) --vec;
if(find(it) == x) Sol -= SZ[x];
}
Sol += 1LL * vec * SZ[y];
for(auto it : elem[y]) if(bridge[x].count(it)) Sol -= SZ[y];
for(auto it : elem[y]) elem[x].insert(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;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |