oj.uz

Submission #51989

# Submission time Handle Problem Language Result Execution time Memory
51989 2018-06-22T22:13:30 Z pzdba Duathlon (APIO18_duathlon) C++14
31 / 100
 227 ms 45824 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

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 7 ms 7468 KB Output is correct
4 Correct 9 ms 7632 KB Output is correct
5 Correct 7 ms 7632 KB Output is correct
6 Correct 7 ms 7632 KB Output is correct
7 Incorrect 7 ms 7632 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 7 ms 7468 KB Output is correct
4 Correct 9 ms 7632 KB Output is correct
5 Correct 7 ms 7632 KB Output is correct
6 Correct 7 ms 7632 KB Output is correct
7 Incorrect 7 ms 7632 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 44020 KB Output is correct
2 Correct 227 ms 44020 KB Output is correct
3 Correct 181 ms 44020 KB Output is correct
4 Correct 177 ms 44020 KB Output is correct
5 Correct 168 ms 44020 KB Output is correct
6 Correct 171 ms 44020 KB Output is correct
7 Correct 161 ms 44020 KB Output is correct
8 Correct 206 ms 44020 KB Output is correct
9 Correct 155 ms 44020 KB Output is correct
10 Correct 167 ms 44020 KB Output is correct
11 Correct 114 ms 44020 KB Output is correct
12 Correct 118 ms 44020 KB Output is correct
13 Correct 108 ms 44020 KB Output is correct
14 Correct 113 ms 44020 KB Output is correct
15 Correct 78 ms 44020 KB Output is correct
16 Correct 73 ms 44020 KB Output is correct
17 Correct 11 ms 44020 KB Output is correct
18 Correct 11 ms 44020 KB Output is correct
19 Correct 13 ms 44020 KB Output is correct
20 Correct 13 ms 44020 KB Output is correct
21 Correct 13 ms 44020 KB Output is correct
22 Correct 11 ms 44020 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 44020 KB Output is correct
2 Correct 10 ms 44020 KB Output is correct
3 Correct 10 ms 44020 KB Output is correct
4 Correct 8 ms 44020 KB Output is correct
5 Correct 9 ms 44020 KB Output is correct
6 Correct 8 ms 44020 KB Output is correct
7 Correct 8 ms 44020 KB Output is correct
8 Correct 9 ms 44020 KB Output is correct
9 Correct 12 ms 44020 KB Output is correct
10 Correct 9 ms 44020 KB Output is correct
11 Correct 8 ms 44020 KB Output is correct
12 Correct 8 ms 44020 KB Output is correct
13 Correct 8 ms 44020 KB Output is correct
14 Correct 9 ms 44020 KB Output is correct
15 Correct 8 ms 44020 KB Output is correct
16 Correct 8 ms 44020 KB Output is correct
17 Correct 8 ms 44020 KB Output is correct
18 Correct 12 ms 44020 KB Output is correct
19 Correct 11 ms 44020 KB Output is correct
20 Correct 9 ms 44020 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 44020 KB Output is correct
2 Correct 176 ms 44020 KB Output is correct
3 Correct 156 ms 44020 KB Output is correct
4 Correct 157 ms 44020 KB Output is correct
5 Correct 165 ms 44020 KB Output is correct
6 Correct 188 ms 45824 KB Output is correct
7 Correct 198 ms 45824 KB Output is correct
8 Correct 192 ms 45824 KB Output is correct
9 Correct 191 ms 45824 KB Output is correct
10 Correct 165 ms 45824 KB Output is correct
11 Correct 167 ms 45824 KB Output is correct
12 Correct 177 ms 45824 KB Output is correct
13 Correct 197 ms 45824 KB Output is correct
14 Correct 145 ms 45824 KB Output is correct
15 Correct 124 ms 45824 KB Output is correct
16 Correct 86 ms 45824 KB Output is correct
17 Correct 176 ms 45824 KB Output is correct
18 Correct 146 ms 45824 KB Output is correct
19 Correct 164 ms 45824 KB Output is correct
20 Correct 127 ms 45824 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 45824 KB Output is correct
2 Correct 10 ms 45824 KB Output is correct
3 Incorrect 11 ms 45824 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 45824 KB Output is correct
2 Correct 194 ms 45824 KB Output is correct
3 Incorrect 181 ms 45824 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 7 ms 7468 KB Output is correct
4 Correct 9 ms 7632 KB Output is correct
5 Correct 7 ms 7632 KB Output is correct
6 Correct 7 ms 7632 KB Output is correct
7 Incorrect 7 ms 7632 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 7 ms 7468 KB Output is correct
4 Correct 9 ms 7632 KB Output is correct
5 Correct 7 ms 7632 KB Output is correct
6 Correct 7 ms 7632 KB Output is correct
7 Incorrect 7 ms 7632 KB Output isn't correct
8 Halted 0 ms 0 KB -