Submission #829963

#TimeUsernameProblemLanguageResultExecution timeMemory
829963tolbiDuathlon (APIO18_duathlon)C++17
23 / 100
197 ms36660 KiB
#pragma optimize("Bismillahirrahmanirrahim") //█▀█─█──█──█▀█─█─█ //█▄█─█──█──█▄█─█■█ //█─█─█▄─█▄─█─█─█─█ //Allahuekber //ahmet23 orz... //FatihSultanMehmedHan //YavuzSultanSelimHan //AbdulhamidHan //Sani buyuk Osman Pasa Plevneden cikmam diyor #define author tolbi #include <bits/stdc++.h> using namespace std; #define deci(x) int x;cin>>x; #define decstr(x) string x;cin>>x; #define sortarr(x) sort(x.begin(), x.end()) #define sortrarr(x) sort(x.rbegin(), x.rend()) #define rev(x) reverse(x.begin(), x.end()) #define cinarr(x) for (auto &it : x) cin>>it; #define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl; #define tol(bi) (1LL<<((int)(bi))) #define endl '\n' typedef long long ll; mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count()); ll solve2(int n, vector<int> u, vector<int> v){ int totn = n; vector<vector<int>> arr(n); for (int i = 0; i < u.size(); i++){ arr[u[i]].push_back(v[i]); arr[v[i]].push_back(u[i]); } vector<int> dept(n,-1); vector<int> sz; vector<vector<int>> stk(n); function<int(int,int)> f; ll ans = 0; f = [&](int node, int lnode)->int{ int mide = dept[node]; stk[node].push_back(node); int sadeben = 1; for (int i = 0; i < arr[node].size(); i++){ if (arr[node][i]==lnode) continue; if (dept[arr[node][i]]!=-1){ mide=min(mide,dept[arr[node][i]]); continue; } dept[arr[node][i]]=dept[node]+1; mide=min(mide,f(arr[node][i],node)); if (mide==dept[node]){ sadeben+=stk[arr[node][i]].size(); } if (stk[node].size()<stk[arr[node][i]].size()) swap(stk[node],stk[arr[node][i]]); while (stk[arr[node][i]].size()){ stk[node].push_back(stk[arr[node][i]].back()); stk[arr[node][i]].pop_back(); } } ans+=(sadeben-1)*(sadeben-1)*(totn-sadeben)*2; ans+=(sadeben)*(sadeben-1)*(sadeben-2); if (mide>=dept[node]){ sz.push_back(0); while (stk[node].size()){ stk[node].pop_back(); sz.back()++; } } return mide; }; dept[0]=0; f(0,-1); return ans; } ll solve(int n, vector<int> u, vector<int> v){ int totn = n; vector<vector<int>> arr(n); for (int i = 0; i < u.size(); i++){ arr[u[i]].push_back(v[i]); arr[v[i]].push_back(u[i]); } vector<int> dept(n,-1); vector<int> ele(n); vector<int> sz; vector<vector<int>> stk(n); vector<vector<int>> hehe; function<int(int,int)> f; vector<int> par(n); f = [&](int node, int lnode)->int{ if (lnode!=-1) par[node]=lnode; int mide = dept[node]; vector<int> crstak; stk[node].push_back(node); for (int i = 0; i < arr[node].size(); i++){ if (arr[node][i]==lnode) continue; if (dept[arr[node][i]]!=-1){ mide=min(mide,dept[arr[node][i]]); continue; } dept[arr[node][i]]=dept[node]+1; mide=min(mide,f(arr[node][i],node)); if (stk[node].size()<stk[arr[node][i]].size()) swap(stk[node],stk[arr[node][i]]); while (stk[arr[node][i]].size()){ stk[node].push_back(stk[arr[node][i]].back()); stk[arr[node][i]].pop_back(); } } if (mide>=dept[node]){ sz.push_back(0); while (stk[node].size()){ ele[stk[node].back()]=hehe.size(); stk[node].pop_back(); sz.back()++; } hehe.push_back(vector<int>()); } return mide; }; dept[0]=0; f(0,-1); for (int i = 1; i < n; i++){ if (ele[i]!=ele[par[i]]){ hehe[ele[i]].push_back(ele[par[i]]); hehe[ele[par[i]]].push_back(ele[i]); } } n=hehe.size(); dept[0]=0; swap(arr,hehe); ll ans = 0; for (int i = 0; i < sz.size(); i++){ //ans+=(ll)sz[i]*((ll)sz[i]-1)*((ll)sz[i]-2); }//3 from cycle vector<int> subsz(n); //coutarr(sz); f = [&](int node, int lnode)->int{ subsz[node]=sz[node]; for (int i = 0; i < arr[node].size(); i++){ if (arr[node][i]==lnode) continue; f(arr[node][i],node); subsz[node]+=subsz[arr[node][i]]; ans+=((ll)subsz[arr[node][i]])*((ll)sz[node])*((ll)totn-subsz[arr[node][i]]-sz[node]); //2 from outside, 1 from cycle //ans+=(ll)(sz[node]-1)*((ll)sz[node]-1)*(ll)subsz[arr[node][i]]*2LL; //2 from cycle, 1 from outside } //ans+=(ll)(sz[node]-1)*((ll)sz[node]-1)*((ll)totn-subsz[node])*2LL; ans+=(ll)(sz[node])*((ll)totn-subsz[node])*((ll)subsz[node]-(ll)sz[node]); return 23; }; f(0,-1); return ans; } int32_t main(){ int T = 1; int tno = 0; while (T-(tno++)){ deci(n);deci(m); vector<int> par(n); iota(par.begin(), par.end(), 0); function<int(int)> find; find = [&](int node)->int{ if (par[node]==node) return node; return par[node]=find(par[node]); }; vector<pair<int,int>> edges(m); for (int i = 0; i < m; i++){ cin>>edges[i].first>>edges[i].second; edges[i].first--,edges[i].second--; int u = edges[i].first; int v = edges[i].second; u=find(u); v=find(v); if (ayahya()%2) swap(u,v); par[u]=v; } map<int,int> mp; map<int,vector<int>> u; map<int,vector<int>> v; vector<int> indis(n); for (int i = 0; i < n; i++){ indis[i]=mp[find(i)]++; } for (int i = 0; i < m; i++){ u[find(edges[i].first)].push_back(indis[edges[i].first]); v[find(edges[i].first)].push_back(indis[edges[i].second]); } ll ans = 0; for (auto it : mp){ ans+=solve(it.second,u[it.first],v[it.first]); ans+=solve2(it.second,u[it.first],v[it.first]); u.erase(it.first); v.erase(it.first); } cout<<ans<<endl; } }//wa

Compilation message (stderr)

count_triplets.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
count_triplets.cpp: In function 'll solve2(int, std::vector<int>, std::vector<int>)':
count_triplets.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int i = 0; i < u.size(); i++){
      |                     ~~^~~~~~~~~~
count_triplets.cpp: In lambda function:
count_triplets.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int i = 0; i < arr[node].size(); i++){
      |                         ~~^~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'll solve(int, std::vector<int>, std::vector<int>)':
count_triplets.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for (int i = 0; i < u.size(); i++){
      |                     ~~^~~~~~~~~~
count_triplets.cpp: In lambda function:
count_triplets.cpp:92:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for (int i = 0; i < arr[node].size(); i++){
      |                         ~~^~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'll solve(int, std::vector<int>, std::vector<int>)':
count_triplets.cpp:129:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for (int i = 0; i < sz.size(); i++){
      |                     ~~^~~~~~~~~~~
count_triplets.cpp: In lambda function:
count_triplets.cpp:136:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |         for (int i = 0; i < arr[node].size(); i++){
      |                         ~~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...