Submission #961773

#TimeUsernameProblemLanguageResultExecution timeMemory
961773danikoynovMaking Friends on Joitter is Fun (JOI20_joitter2)C++14
0 / 100
1 ms600 KiB
#include <bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; const int maxn = 2010; int n, par[maxn], m; int sz[maxn]; int find_leader(int v) { if (par[v] == v) return v; return (par[v] = find_leader(par[v])); } set < int > rem; set < int > in_adj_diff[maxn]; set < int > in_adj[maxn], out_adj[maxn]; ll calc(int v) { //cout << "calc " << v << " " << sz[v] << " " << in_adj_diff[v].size() << endl; //for (int w : in_adj_diff[v])cout << w << " "; //cout << endl; ll s = sz[v]; return s * (s - 1 + (ll)(in_adj_diff[v].size())); } ll res; void unite(int v, int u) { v = find_leader(v); u = find_leader(u); if (v == u) return; ///cout << "unite " << endl; if (rem.find(v) == rem.end()) { res = res - calc(v); rem.insert(v); } if (rem.find(u) == rem.end()) { res = res - calc(u); rem.insert(u); } vector < int > d;par[u] = v; sz[v] += sz[u]; for (int w : out_adj[u]) { if (find_leader(w) == v) continue; out_adj[v].insert(w); if (in_adj_diff[v].find(find_leader(w)) != in_adj_diff[u].end()) d.push_back(w); } for (int w : in_adj[u]) { if (find_leader(w) == v) continue; ///cout << "to " << v << " " << w << endl; in_adj_diff[v].insert(w); if (out_adj[v].find(find_leader(w)) != out_adj[v].end()) d.push_back(w); } vector < int > sd; for (int k : in_adj_diff[v]) { ///cout << v << " : " << k << " " << endl; if (find_leader(k) == v) sd.push_back(k); } for (int k : sd) in_adj_diff[v].erase(k); for (int c : d) unite(v, c); } void solve() { cin >> n >> m; for (int i = 1; i <= n; i ++) { par[i] = i; sz[i] = 1; } for (int i = 1; i <= m; i ++) { int v, u; cin >> v >> u; int lv = find_leader(v); int lu = find_leader(u); if (v == u) { cout << res << endl; continue; } if (in_adj_diff[lv].find(lu) != in_adj_diff[lv].end()) { rem.clear(); unite(lv, lu); set < int > st; for (int c : rem) st.insert(find_leader(c)); for (int c : st) res += calc(c); } else { res = res - calc(lv); res = res - calc(lu); out_adj[lv].insert(lu); in_adj[lu].insert(lv); in_adj_diff[lu].insert(v); res = res + calc(lv); res = res + calc(lu); } cout << res << endl; } } int main() { solve(); return 0; } /** 6 7 1 2 2 3 3 4 4 5 5 6 6 5 5 4 4 3 1 2 2 3 3 2 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...