제출 #54172

#제출 시각아이디문제언어결과실행 시간메모리
54172bogdan10bos철인 이종 경기 (APIO18_duathlon)C++14
0 / 100
253 ms55072 KiB
#include <bits/stdc++.h> using namespace std; //#define FILE_IO typedef long long LL; int N, M; namespace Biconnex { int h[400005], low[400005]; vector<int> edg[400005]; stack<int> stv; int K = 0; vector<int> bcx[400005], cmp[400005]; void addEdge(int x, int y) { edg[x].push_back(y); edg[y].push_back(x); } void DFS(int nod, int fth = 0) { h[nod] = h[fth] + 1; low[nod] = h[nod]; stv.push(nod); for(auto nxt: edg[nod]) { if(nxt == fth) continue; if(h[nxt] != 0) { low[nod] = min(low[nod], h[nxt]); continue; } stv.push(nod); DFS(nxt, nod); low[nod] = min(low[nod], low[nxt]); if(low[nxt] >= h[nod]) { K++; while(stv.top() != nod) { int x = stv.top(); cmp[K].push_back(x); bcx[x].push_back(K); stv.pop(); } cmp[K].push_back(nod); bcx[nod].push_back(K); stv.pop(); } } } void getbiconnex() { for(int i = 1; i <= N; i++) if(!h[i]) DFS(i); for(int i = 1; i <= K; i++) cmp[i].erase(unique(cmp[i].begin(), cmp[i].end()), cmp[i].end()); for(int i = 1; i <= N; i++) bcx[i].erase(unique(bcx[i].begin(), bcx[i].end()), bcx[i].end()); } } namespace Tree { int N, K; LL ans; int f[400005], viz[400005]; int valuare[400005], val[400005], sz[400005], cmp[400005]; vector<int> edg[400005]; void addEdge(int x, int y) { f[x] = f[y] = 1; edg[x].push_back(y); edg[y].push_back(x); } void setValue(int x, int y) { f[x] = 1; val[x] = y; } void DFS(int nod, int fth = 0) { if(fth == 0) cmp[nod] = nod; else cmp[nod] = cmp[fth]; viz[nod] = 1; valuare[nod] = val[nod] == -1 ? 1 : val[nod] - edg[nod].size(); sz[nod] = valuare[nod]; for(auto nxt: edg[nod]) { if(nxt == fth) continue; DFS(nxt, nod); sz[nod] += sz[nxt]; } } void solve() { ans = 0; for(int i = 1; i <= N; i++) if(f[i]) setValue(i, -1); for(int i = 1; i <= N + K; i++) if(f[i] && !viz[i]) DFS(i); for(int i = N + 1; i <= N + K; i++) if(f[i]) { int nod = i; int M = sz[ cmp[i] ]; /// 3 elemente ans += 1LL * val[i] * (val[i] - 1) * (val[i] - 2); /// 2 elemente for(auto nxt: edg[i]) { if(sz[nxt] > sz[nod]) continue; ans += 2LL * (val[i] - 1) * (val[i] - 2) * (sz[nxt] - 1); ans += 2LL * (val[i] - 1) * (sz[nxt] - 1); } if(sz[nod] != M) { ans += 2LL * (val[i] - 1) * (val[i] - 2) * (M - sz[nod] - 1); ans += 2LL * (val[i] - 1) * (M - sz[nod] - 1); } /// 1 element (mijloc) for(auto nxt: edg[i]) { if(sz[nxt] > sz[nod]) continue; ans += 1LL * val[i] * (sz[nxt] - 1) * (M - val[i] - sz[nxt] + 1); } if(sz[nod] != M) { ans += 1LL * val[i] * (M - sz[nod] - 1) * (sz[nod] - val[nod] + 1); } } printf("%lld\n", ans); } } void makeTree() { using namespace Biconnex; for(int i = 1; i <= K; i++) { if(cmp[i].size() > 2) { Tree::setValue(i + N, cmp[i].size()); for(auto &nod: cmp[i]) if(bcx[nod].size() > 1) Tree::addEdge(i + N, nod); } else { Tree::addEdge(cmp[i][0], cmp[i][1]); } } Tree::N = N; Tree::K = K; } void gen() { freopen("1.in", "w", stdout); int N = 1e5; printf("%d %d\n", N, N); for(int i = 1; i < N; i++) printf("%d %d\n", i, i + 1); printf("%d %d\n", 1, N); exit(0); } int main() { //gen(); #ifdef FILE_IO freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); #endif scanf("%d%d", &N, &M); for(int i = 1; i <= M; i++) { int x, y; scanf("%d%d", &x, &y); Biconnex::addEdge(x, y); } Biconnex::getbiconnex(); makeTree(); Tree::solve(); return 0; }

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

count_triplets.cpp: In function 'void gen()':
count_triplets.cpp:175:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("1.in", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:193: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:197: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...
#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...