Submission #1177019

#TimeUsernameProblemLanguageResultExecution timeMemory
1177019arwakhattabMaking Friends on Joitter is Fun (JOI20_joitter2)C++20
0 / 100
21 ms45568 KiB
#include <bits/stdc++.h> #define all(x) begin(x), end(x) using namespace std; using ll = long long; const char nl = '\n', sp = ' '; const int N = 1e5; struct DSU { int n; vector<int> par, size; vector<bitset<N> > msk; DSU() { } DSU(int n) : n(n) { par.assign(n, 0); size.assign(n, 1); msk.assign(n, 0); for (int i = 0; i < n; i++) { par[i] = i; msk[i][i] = true; } } int find(int v) { return (v == par[v] ? v : par[v] = find(par[v])); } void set(int u, int v) { msk[find(v)][u] = true; } bool get(int u, int v) { return msk[find(v)][u]; } ll get_ans(int u) { u = find(u); ll m = size[u]; return m * (msk[u].count() - 1); } bool unite(int a, int b) { a = find(a), b = find(b); if (a == b) return false; if (size[a] < size[b]) swap(a, b); par[b] = a; size[a] += size[b]; msk[a] |= msk[b]; return true; } int sz(int v) { return size[find(v)]; } }; void solve() { int n, m; cin >> n >> m; set<pair<int, int> > edges; DSU dsu(n); ll ans = 0; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; --u, --v; if (edges.contains({v, u})) { ans -= dsu.get_ans(u); ans -= dsu.get_ans(v); dsu.unite(u, v); ans += dsu.get_ans(u); } else if (!dsu.get(u, v)) { dsu.set(u, v); ans += dsu.sz(v); } edges.insert({u, v}); cout << ans << nl; } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #ifndef ONLINE_JUDGE freopen("../in.txt", "r", stdin); freopen("../out.txt", "w", stdout); #endif int t = 1; // cin >> t; while (t--) { solve(); } }

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:90:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     freopen("../in.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
joitter2.cpp:91:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     freopen("../out.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...