Submission #1199585

#TimeUsernameProblemLanguageResultExecution timeMemory
1199585hoa208Making Friends on Joitter is Fun (JOI20_joitter2)C++20
0 / 100
6 ms14400 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++) #define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--) #define pa pair<ll, ll> #define fi first #define se second #define bit(mask, j) ((mask >> j) & 1) #define t_test int t;cin >> t;while(t--) const ll mod = 1e9 + 7; const ll INF = 1e18; inline void adm(ll &x){if(x>=mod)x%=mod;else if(x<0)x+=mod;} //-------------------------------------------------------------------- const ll N = 1e5 + 10; const ll M = 3e5 + 10; ll n, m; ll ans = 0; set<ll> child[N], indeg[N], outdeg[N]; ll p[N], sz[N]; queue<pa> q; ll findset(ll u) { return u == p[u] ? u : p[u] = findset(p[u]); } ll size_dsu(ll &u) { return child[u].size() + indeg[u].size() + outdeg[u].size(); } void ghep(ll u, ll v) { u = findset(u); v = findset(v); if(u == v) return; if(size_dsu(u) < size_dsu(v)) swap(u, v); ans += sz[u] * child[v].size() + sz[v] * child[u].size(); sz[u] += sz[v]; p[v] = u; for(auto e : child[v]) { child[v].erase(e); if(child[u].count(e)) ans -= sz[u]; else child[u].insert(e); } for(auto e : indeg[v]) { indeg[v].erase(e); indeg[u].insert(e); outdeg[e].insert(u); if(outdeg[u].count(e)) { q.push({e, u}); } } for(auto e : outdeg[v]) { outdeg[v].erase(e); outdeg[u].insert(e); indeg[e].insert(u); if(indeg[u].count(e)) { q.push({e, u}); } } } void hbmt() { cin >> n >> m; FOR(i, 1, n) { p[i] = i; sz[i] = 1; child[i].insert(i); } FOR(i, 1, m) { ll u, v; cin >> u >> v; ll _u = findset(u), _v = findset(v); if(!child[_v].count(u)) { ans += sz[_v]; indeg[_v].insert(_u); outdeg[_u].insert(_v); child[_v].insert(u); if(outdeg[_v].count(_u)) q.push({_u, _v}); while(!q.empty()) { pa v = q.front(); q.pop(); ghep(v.fi, v.se); } } cout << ans << '\n'; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); if(fopen("hbmt.inp", "r")) { freopen("hbmt.inp", "r", stdin); freopen("hbmt.out", "w", stdout); } // t_test hbmt(); return 0; }

Compilation message (stderr)

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