제출 #51982

#제출 시각아이디문제언어결과실행 시간메모리
51982pzdba철인 이종 경기 (APIO18_duathlon)C++14
8 / 100
232 ms44228 KiB
#include <bits/stdc++.h> using namespace std; #define NIL -1 typedef pair<int, int> pii; typedef long long LL; bool vis[100005]; class Edge { public: int u; int v; Edge(int u, int v); }; Edge::Edge(int u, int v) { this->u = u; this->v = v; } // A class that represents an directed graph class Graph { int V; // No. of vertices int E; // No. of edges list<int> *adj; // A dynamic array of adjacency lists // A Recursive DFS based function used by BCC() void BCCUtil(int u, int disc[], int low[], list<Edge> *st, int parent[]); public: Graph(int V); // Constructor void addEdge(int v, int w); // function to add an edge to graph void BCC(); // prints strongly connected components }; Graph::Graph(int V) { this->V = V; this->E = 0; adj = new list<int>[V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); E++; } int cnt = 1; set<int> com[100005]; // A recursive function that finds and prints strongly connected // components using DFS traversal // u --> The vertex to be visited next // disc[] --> Stores discovery times of visited vertices // low[] -- >> earliest visited vertex (the vertex with minimum // discovery time) that can be reached from subtree // rooted with current vertex // *st -- >> To store visited edges void Graph::BCCUtil(int u, int disc[], int low[], list<Edge> *st, int parent[]) { // A static variable is used for simplicity, we can avoid use // of static variable by passing a pointer. static int time = 0; // Initialize discovery time and low value disc[u] = low[u] = ++time; int children = 0; // Go through all vertices adjacent to this list<int>::iterator i; for (i = adj[u].begin(); i != adj[u].end(); ++i) { int v = *i; // v is current adjacent of 'u' // If v is not visited yet, then recur for it if (disc[v] == -1) { children++; parent[v] = u; //store the edge in stack st->push_back(Edge(u,v)); BCCUtil(v, disc, low, st, parent); // Check if the subtree rooted with 'v' has a // connection to one of the ancestors of 'u' // Case 1 -- per Strongly Connected Components Article low[u] = min(low[u], low[v]); //If u is an articulation point, //pop all edges from stack till u -- v if( (disc[u] == 1 && children > 1) || (disc[u] > 1 && low[v] >= disc[u]) ) { while(st->back().u != u || st->back().v != v) { com[cnt].insert(st->back().u+1); com[cnt].insert(st->back().v+1); // cout << st->back().u << "--" << st->back().v << " "; st->pop_back(); } com[cnt].insert(st->back().u+1); com[cnt].insert(st->back().v+1); // cout << st->back().u << "--" << st->back().v; st->pop_back(); cnt++; } } // Update low value of 'u' only of 'v' is still in stack // (i.e. it's a back edge, not cross edge). // Case 2 -- per Strongly Connected Components Article else if(v != parent[u] && disc[v] < low[u]) { low[u] = min(low[u], disc[v]); st->push_back(Edge(u,v)); } } } // The function to do DFS traversal. It uses BCCUtil() void Graph::BCC() { int *disc = new int[V]; int *low = new int[V]; int *parent = new int[V]; list<Edge> *st = new list<Edge>[E]; // Initialize disc and low, and parent arrays for (int i = 0; i < V; i++) { disc[i] = NIL; low[i] = NIL; parent[i] = NIL; } for (int i = 0; i < V; i++) { if (disc[i] == NIL) BCCUtil(i, disc, low, st, parent); int j = 0; //If stack is not empty, pop all edges from stack while(st->size() > 0) { j = 1; com[cnt].insert(st->back().u+1); com[cnt].insert(st->back().v+1); // cout << st->back().u << "--" << st->back().v << " "; st->pop_back(); } if(j == 1) { cnt++; // cout << endl; } } } vector<int> gs[100005]; LL ans = 0; LL s[100005], sc[100005]; void dfs(int u, int p){ vis[u] = 1; s[u] += com[u].size(); sc[u] += (LL)(com[u].size()-1)*(com[u].size()-1); for(auto its:com[u]){ if(its == p) continue; for(int i=0;i<gs[its].size();i++){ int v = gs[its][i]; if(vis[v]) continue; dfs(v, its); ans += sc[v]*(s[u]-1); ans += (s[v]-1)*(sc[u]); ans -= (s[v]-1)*(s[u]-1); s[u] += s[v]-1; sc[u] += sc[v]; sc[u] += (s[v]-1)*(com[u].size()-1); } } } int main(){ int n, m; scanf("%d%d", &n, &m); Graph g(n); for(int i=0;i<m;i++){ int a, b; scanf("%d%d", &a, &b); a--; b--; g.addEdge(a, b); g.addEdge(b, a); } g.BCC(); cnt--; for(int i=1;i<=cnt;i++){ for(auto its:com[i]) gs[its].push_back(i); } for(int i=1;i<=cnt;i++){ if(vis[i]) continue; dfs(i, 0); } ans *= 2; for(int i=1;i<=cnt;i++){ ans += (LL)(com[i].size())*(com[i].size()-1)*(com[i].size()-2); } printf("%lld\n", ans); }

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

count_triplets.cpp: In function 'void dfs(int, int)':
count_triplets.cpp:175:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<gs[its].size();i++){
               ~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:193:7: 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:8: 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...