oj.uz

답안 #51988

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51988 2018-06-22T22:04:01 Z pzdba 철인 이종 경기 (APIO18_duathlon) C++14
31 / 100
 273 ms 45680 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);
	LL s1 = 0;
	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];

			s1 += s[v]-1;
			// sc[u] += (s[v]-1)*(com[u].size()-1);
		}
		sc[u] += s1*(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:176: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:197: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:201: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 9 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7604 KB Output is correct
4 Correct 9 ms 7604 KB Output is correct
5 Correct 9 ms 7604 KB Output is correct
6 Correct 8 ms 7624 KB Output is correct
7 Incorrect 7 ms 7624 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 252 ms 44156 KB Output is correct
2 Correct 273 ms 44156 KB Output is correct
3 Correct 207 ms 44156 KB Output is correct
4 Correct 249 ms 44156 KB Output is correct
5 Correct 193 ms 44156 KB Output is correct
6 Correct 205 ms 44156 KB Output is correct
7 Correct 256 ms 44156 KB Output is correct
8 Correct 192 ms 44156 KB Output is correct
9 Correct 183 ms 44156 KB Output is correct
10 Correct 183 ms 44156 KB Output is correct
11 Correct 167 ms 44156 KB Output is correct
12 Correct 139 ms 44156 KB Output is correct
13 Correct 141 ms 44156 KB Output is correct
14 Correct 112 ms 44156 KB Output is correct
15 Correct 87 ms 44156 KB Output is correct
16 Correct 88 ms 44156 KB Output is correct
17 Correct 11 ms 44156 KB Output is correct
18 Correct 11 ms 44156 KB Output is correct
19 Correct 14 ms 44156 KB Output is correct
20 Correct 11 ms 44156 KB Output is correct
21 Correct 11 ms 44156 KB Output is correct
22 Correct 12 ms 44156 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 44156 KB Output is correct
2 Correct 8 ms 44156 KB Output is correct
3 Correct 9 ms 44156 KB Output is correct
4 Correct 8 ms 44156 KB Output is correct
5 Correct 9 ms 44156 KB Output is correct
6 Correct 8 ms 44156 KB Output is correct
7 Correct 8 ms 44156 KB Output is correct
8 Correct 12 ms 44156 KB Output is correct
9 Correct 10 ms 44156 KB Output is correct
10 Correct 8 ms 44156 KB Output is correct
11 Correct 9 ms 44156 KB Output is correct
12 Correct 8 ms 44156 KB Output is correct
13 Correct 8 ms 44156 KB Output is correct
14 Correct 9 ms 44156 KB Output is correct
15 Correct 8 ms 44156 KB Output is correct
16 Correct 8 ms 44156 KB Output is correct
17 Correct 8 ms 44156 KB Output is correct
18 Correct 12 ms 44156 KB Output is correct
19 Correct 8 ms 44156 KB Output is correct
20 Correct 10 ms 44156 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 170 ms 44156 KB Output is correct
2 Correct 169 ms 44156 KB Output is correct
3 Correct 182 ms 44156 KB Output is correct
4 Correct 168 ms 44156 KB Output is correct
5 Correct 181 ms 44156 KB Output is correct
6 Correct 196 ms 45680 KB Output is correct
7 Correct 223 ms 45680 KB Output is correct
8 Correct 202 ms 45680 KB Output is correct
9 Correct 195 ms 45680 KB Output is correct
10 Correct 221 ms 45680 KB Output is correct
11 Correct 175 ms 45680 KB Output is correct
12 Correct 181 ms 45680 KB Output is correct
13 Correct 176 ms 45680 KB Output is correct
14 Correct 144 ms 45680 KB Output is correct
15 Correct 166 ms 45680 KB Output is correct
16 Correct 80 ms 45680 KB Output is correct
17 Correct 131 ms 45680 KB Output is correct
18 Correct 133 ms 45680 KB Output is correct
19 Correct 176 ms 45680 KB Output is correct
20 Correct 149 ms 45680 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 45680 KB Output is correct
2 Correct 8 ms 45680 KB Output is correct
3 Incorrect 9 ms 45680 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 45680 KB Output is correct
2 Correct 168 ms 45680 KB Output is correct
3 Incorrect 184 ms 45680 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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