제출 #51982

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51982		pzdba	철인 이종 경기 (APIO18_duathlon)	C++14	8 / 100	232 ms	44228 KiB

count_triplets

#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);
   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 8 / 8
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10