제출 #211891

#제출 시각아이디문제언어결과실행 시간메모리
211891Akashi조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)C++14
0 / 100
15 ms19200 KiB
#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 += 2LL * SZ[x] * SZ[y]; for(auto it : bridge[y]) if(elem[x].count(it)) Sol = Sol - SZ[y]; for(auto it : elem[y]) if(bridge[x].count(it)) Sol = Sol - SZ[x]; for(auto it : bridge[y]) if(!bridge[x].count(it) && !elem[x].count(it)) Sol = Sol + SZ[x]; int nr = bridge[x].size(); for(auto it : bridge[y]) if(bridge[x].count(it)) --nr; for(auto it : elem[y]) if(bridge[x].count(it)) --nr; Sol = Sol + 1LL * SZ[y] * nr; for(auto it : elem[y]){ elem[x].insert(it); if(bridge[x].count(it)) bridge[x].erase(it); } if(in[x].count(y)) in[x].erase(y); if(out[x].count(y)) out[x].erase(y); 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(!elem[x].count(it)) 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; }

컴파일 시 표준 에러 (stderr) 메시지

joitter2.cpp: In function 'int main()':
joitter2.cpp:71:19: warning: variable 'fy' set but not used [-Wunused-but-set-variable]
     int x, y, fx, fy;
                   ^~
joitter2.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
joitter2.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...