Submission #108441

#TimeUsernameProblemLanguageResultExecution timeMemory
108441PeppaPigDuathlon (APIO18_duathlon)C++14
0 / 100
1067 ms19856 KiB
#include <bits/stdc++.h> #define long long long #define pii pair<int, int> #define x first #define y second using namespace std; const int N = 1e5+5; int n, m; int pre[N], low[N], ap[N], id[N]; vector<vector<int> > g(N), bcc; vector<int> sz; void tarjan(int u, int p) { static int idx = 0; static stack<int> S; pre[u] = low[u] = ++idx, S.emplace(u); int cnt = 0; for(int v : g[u]) if(v != p) { if(!pre[v]) { ++cnt; tarjan(v, u); low[u] = min(low[u], low[v]); if((!p && cnt > 1) || (p && low[v] >= pre[u])) ap[u] = 1; if(low[v] >= pre[u]) { bcc.emplace_back(vector<int>()); bcc.back().emplace_back(u); while(bcc.back().back() != v) { bcc.back().emplace_back(S.top()); S.pop(); } } } else low[u] = min(low[u], pre[v]); } } bitset<N> idart; void gen_bct() { g.clear(); g.emplace_back(vector<int>()); sz.emplace_back(0); for(int i = 1; i <= n; i++) if(ap[i]) { idart[id[i] = g.size()] = true; g.emplace_back(vector<int>()); sz.emplace_back(1); } for(vector<int> &cc : bcc) { g.emplace_back(vector<int>()); sz.emplace_back(cc.size()); for(int v : cc) { if(ap[v]) g[id[v]].emplace_back(g.size()-1), g[g.size()-1].emplace_back(id[v]); else id[v] = g.size()-1; } } } bitset<N> chk; int siz[N]; long ans, sum_sz, sum_sz2; int getsz(int u, int p) { siz[u] = 1; for(int v : g[u]) if(v != p && !chk[v]) siz[u] += getsz(v, u); return siz[u]; } int find_cen(int u, int p, int all, pii &ret) { int mx = all - sz[u]; for(int v : g[u]) if(v != p && !chk[v]) mx = max(mx, find_cen(v, u, all, ret)); ret = min(ret, pii(mx, u)); } int noap_sz(int u) { return idart[u] ? 1 : sz[u] - g[u].size(); } //Non-overlap Size int noad_sz(int u) { return sz[u] - 2 * (int)!idart[u]; } //Size with no 2 adjacent APs void dfs(int u, int p, long all, bool fill) { if(!fill) ans += noap_sz(u) * (sum_sz2 + sum_sz * (all - idart[u])); //Start * (Change another subtree + Change this subtree) else { sum_sz += noap_sz(u); //Finish sum_sz2 += (all - idart[u]) * noap_sz(u); //Change and Finish } for(int v : g[u]) if(v != p && !chk[v]) dfs(v, u, all + noad_sz(v), fill); } void proc(int u) { getsz(u, u); pii ret(sz[u] + 1, -1); find_cen(u, u, sz[u], ret); chk[u = ret.y] = true; if(sz[u] > 2) ans += (sz[u] - 2) * (noap_sz(u) * (noap_sz(u)-1) / 2ll); sum_sz = noap_sz(u); sum_sz2 = idart[u] ? 0 : 1ll * noad_sz(u) * noap_sz(u); for(int v : g[u]) if(!chk[v]) { dfs(v, u, noad_sz(v), 0); dfs(v, u, noad_sz(v), 1); } for(int v : g[u]) if(!chk[v]) proc(v); } int main() { scanf("%d %d", &n, &m); for(int i = 1, a, b; i <= m; i++) { scanf("%d %d", &a, &b); g[a].emplace_back(b), g[b].emplace_back(a); } for(int i = 1; i <= n; i++) if(!pre[i]) tarjan(i, 0); gen_bct(); for(int i = 1; i < (int)g.size(); i++) if(!chk[i]) proc(i); printf("%lld\n", 2ll * ans); return 0; }

Compilation message (stderr)

count_triplets.cpp: In function 'int find_cen(int, int, int, std::pair<int, int>&)':
count_triplets.cpp:72:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:105: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...
#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...