# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
211854 | 2020-03-21T14:19:16 Z | Akashi | Making Friends on Joitter is Fun (JOI20_joitter2) | C++14 | 15 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 += 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; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 15 ms | 19072 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 15 ms | 19072 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 15 ms | 19072 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |