제출 #232064

#제출 시각아이디문제언어결과실행 시간메모리
232064dualityMaking Friends on Joitter is Fun (JOI20_joitter2)C++11
100 / 100
845 ms50332 KiB
#define DEBUG 0 #include <bits/stdc++.h> using namespace std; #if DEBUG // basic debugging macros int __i__,__j__; #define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl #define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl #define printVar(n) cout<<#n<<": "<<n<<endl #define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl #define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;} #define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;} // advanced debugging class // debug 1,2,'A',"test"; class _Debug { public: template<typename T> _Debug& operator,(T val) { cout << val << endl; return *this; } }; #define debug _Debug(), #else #define printLine(l) #define printLine2(l,c) #define printVar(n) #define printArr(a,l) #define print2dArr(a,r,c) #define print2dArr2(a,r,c,l) #define debug #endif // define #define MAX_VAL 999999999 #define MAX_VAL_2 999999999999999999LL #define EPS 1e-6 #define mp make_pair #define pb push_back // typedef typedef unsigned int UI; typedef long long int LLI; typedef unsigned long long int ULLI; typedef unsigned short int US; typedef pair<int,int> pii; typedef pair<LLI,LLI> plli; typedef vector<int> vi; typedef vector<LLI> vlli; typedef vector<pii> vpii; typedef vector<plli> vplli; // ---------- END OF TEMPLATE ---------- int parent[100000],size[100000]; int find(int n) { if (parent[n] != n) parent[n] = find(parent[n]); return parent[n]; } set<pii> in[100000],out[100000]; LLI ans = 0; int merge(int a,int b) { if (find(a) == find(b)) return 0; if (in[a].size()+out[a].size() > in[b].size()+out[b].size()) swap(a,b); ans -= (LLI) size[a]*in[a].size()+(LLI) size[b]*in[b].size(); vi v; for (auto it = in[a].begin(); it != in[a].end(); it++) { out[it->first].erase(mp(a,it->second)); if (it->first != b) { in[b].insert(*it),out[it->first].insert(mp(b,it->second)); auto it2 = in[it->first].lower_bound(mp(b,0)); if ((it2 != in[it->first].end()) && (it2->first == b)) v.pb(it->first); } } for (auto it = out[a].begin(); it != out[a].end(); it++) { in[it->first].erase(mp(a,it->second)); if (it->first != b) { out[b].insert(*it),in[it->first].insert(mp(b,it->second)); auto it2 = out[it->first].lower_bound(mp(b,0)); if ((it2 != out[it->first].end()) && (it2->first == b)) v.pb(it->first); } } ans += (LLI) (size[a]+size[b])*in[b].size()+2LL*size[a]*size[b]; in[a].clear(),out[a].clear(),parent[a] = b,size[b] += size[a]; while (!v.empty()) merge(b,v.back()),v.pop_back(); return 0; } int main() { int i; int N,M,A,B; scanf("%d %d",&N,&M); for (i = 0; i < N; i++) parent[i] = i,size[i] = 1; for (i = 0; i < M; i++) { scanf("%d %d",&A,&B); A--,B--; if ((find(A) != find(B)) && !in[find(B)].count(mp(find(A),A))) { in[find(B)].insert(mp(find(A),A)),out[find(A)].insert(mp(find(B),A)); ans += size[find(B)]; auto it = in[find(A)].lower_bound(mp(find(B),0)); if ((it != in[find(A)].end()) && (it->first == find(B))) merge(find(A),find(B)); } printf("%lld\n",ans); } return 0; }

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

joitter2.cpp: In function 'int main()':
joitter2.cpp:94: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:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&A,&B);
         ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...