oj.uz

답안 #51982

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51982 2018-06-22T21:38:50 Z pzdba 철인 이종 경기 (APIO18_duathlon) C++14
8 / 100
 232 ms 44228 KB 
#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);
}

Compilation message

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7452 KB Output is correct
4 Correct 7 ms 7472 KB Output is correct
5 Correct 7 ms 7472 KB Output is correct
6 Correct 7 ms 7472 KB Output is correct
7 Incorrect 7 ms 7520 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7452 KB Output is correct
4 Correct 7 ms 7472 KB Output is correct
5 Correct 7 ms 7472 KB Output is correct
6 Correct 7 ms 7472 KB Output is correct
7 Incorrect 7 ms 7520 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 186 ms 44040 KB Output is correct
2 Correct 232 ms 44228 KB Output is correct
3 Correct 194 ms 44228 KB Output is correct
4 Correct 172 ms 44228 KB Output is correct
5 Correct 197 ms 44228 KB Output is correct
6 Correct 182 ms 44228 KB Output is correct
7 Correct 183 ms 44228 KB Output is correct
8 Correct 180 ms 44228 KB Output is correct
9 Correct 173 ms 44228 KB Output is correct
10 Correct 197 ms 44228 KB Output is correct
11 Correct 194 ms 44228 KB Output is correct
12 Correct 122 ms 44228 KB Output is correct
13 Correct 114 ms 44228 KB Output is correct
14 Correct 114 ms 44228 KB Output is correct
15 Correct 99 ms 44228 KB Output is correct
16 Correct 81 ms 44228 KB Output is correct
17 Correct 11 ms 44228 KB Output is correct
18 Correct 12 ms 44228 KB Output is correct
19 Correct 11 ms 44228 KB Output is correct
20 Correct 12 ms 44228 KB Output is correct
21 Correct 11 ms 44228 KB Output is correct
22 Correct 11 ms 44228 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 44228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 173 ms 44228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 44228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 177 ms 44228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7452 KB Output is correct
4 Correct 7 ms 7472 KB Output is correct
5 Correct 7 ms 7472 KB Output is correct
6 Correct 7 ms 7472 KB Output is correct
7 Incorrect 7 ms 7520 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7452 KB Output is correct
4 Correct 7 ms 7472 KB Output is correct
5 Correct 7 ms 7472 KB Output is correct
6 Correct 7 ms 7472 KB Output is correct
7 Incorrect 7 ms 7520 KB Output isn't correct
8 Halted 0 ms 0 KB -