Submission #937081

#TimeUsernameProblemLanguageResultExecution timeMemory
937081PringMaking Friends on Joitter is Fun (JOI20_joitter2)C++17
100 / 100
810 ms90072 KiB
#include <bits/stdc++.h> using namespace std; #ifdef MIKU #define debug(x...) cout << '[' << #x << "] : ", dout(x) void dout() { cout << endl; } template <typename T, typename ...U> void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); } #else #define debug(...) 39 #endif #define int long long #define fs first #define sc second #define mp make_pair #define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++) typedef pair<int, int> pii; const int MXN = 100005; int n, m; struct DSU { int p[MXN]; void init(int n) { fill(p + 1, p + n + 1, -1); } int find(int x) { return (p[x] < 0 ? x : p[x] = find(p[x])); } bool onion(int x, int y) { x = find(x); y = find(y); if (x == y) return false; p[y] += p[x]; p[x] = y; return true; } }; namespace DS { DSU dsu; int deg_in[MXN], deg_out[MXN]; queue<pii> q; set<pii> out[MXN]; unordered_map<int, vector<int>> M[MXN]; set<int> S[MXN]; int ansE = 0, ansG = 0; int tri(int x) { return x * (x - 1); } int SIZE(int X) { return -dsu.p[X]; } void init(int n) { dsu.init(n); } void ADD_EDGE(int x, int X, int Y) { deg_in[Y]++; deg_out[X]++; out[X].insert(mp(x, Y)); M[Y][X].push_back(x); S[x].insert(Y); ansE += SIZE(Y); // debug('+', x, Y, ansE); } void ERASE_EDGE(int x, int X, int Y) { deg_out[X]--; deg_in[Y]--; out[X].erase(mp(x, Y)); S[x].erase(Y); ansE -= SIZE(Y); // debug('-', x, Y, ansE); } void MERGE(int X, int Y) { ansG -= tri(SIZE(X)); ansG -= tri(SIZE(Y)); ansG += tri(SIZE(X) + SIZE(Y)); for (auto &i : M[X][Y]) ERASE_EDGE(i, Y, X); M[X].erase(Y); for (auto &i : M[Y][X]) ERASE_EDGE(i, X, Y); M[Y].erase(X); if (deg_in[X] + deg_out[X] >= deg_in[Y] + deg_out[Y]) swap(X, Y); // debug("MERGE", X, Y); { for (auto it = M[X].begin(); it != M[X].end(); it++) { for (auto &i : it -> sc) { ERASE_EDGE(i, dsu.find(i), X); q.push(mp(i, Y)); } } M[X].clear(); } { vector<pii> v; for (auto i : out[X]) v.push_back(i); for (auto i : v) { ERASE_EDGE(i.fs, X, i.sc); q.push(mp(i.fs, i.sc)); } for (auto i : v) { M[i.sc][X].clear(); } out[X].clear(); // debug("CLEAR", X); } ansE -= SIZE(Y) * deg_in[Y]; dsu.onion(X, Y); ansE += SIZE(Y) * deg_in[Y]; } void TEST(int x, int Y) { if (S[x].find(Y) != S[x].end()) return; int X = dsu.find(x); auto it = M[X].find(Y); if (it == M[X].end() || it -> sc.empty()) { ADD_EDGE(x, X, Y); return; } MERGE(X, Y); } void clear_queue() { while (q.size()) { auto [x, y] = q.front(); q.pop(); if (dsu.find(x) == dsu.find(y)) continue; TEST(x, dsu.find(y)); } } void COUT() { cout << endl; FOR(i, 1, n + 1) { cout << i << ": "; // for (auto j : S[i]) cout << j << ' '; for (auto it = M[i].begin(); it != M[i].end(); it++) { cout << '[' << it -> fs << ":"; for (auto &j : it -> sc) cout << ' ' << j; cout << "] "; } cout << endl; } debug(ansE, ansG); cout << endl; } } void miku() { int a, b; cin >> n >> m; // cin >> n; DS::init(n); while (m--) { cin >> a >> b; // while (cin >> a >> b) { DS::q.push(mp(a, b)); DS::clear_queue(); // DS::COUT(); cout << DS::ansE + DS::ansG << '\n'; // for (auto &i : DS::out[5]) cout << '<' << i.fs << ' ' << i.sc << "> "; // cout << endl; } } int32_t main() { cin.tie(0) -> sync_with_stdio(false); // cin.exceptions(iostream::failbit); miku(); return 0; }

Compilation message (stderr)

joitter2.cpp: In function 'void DS::COUT()':
joitter2.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
joitter2.cpp:150:9: note: in expansion of macro 'debug'
  150 |         debug(ansE, ansG);
      |         ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...