oj.uz

Submission #59329

# Submission time Handle Problem Language Result Execution time Memory
59329 2018-07-21T14:30:29 Z MatheusLealV Duathlon (APIO18_duathlon) C++17
23 / 100
 1000 ms 865336 KB 
#include <bits/stdc++.h>
#define N 100050
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

ll n, m, c, ans, ok[N];
   
vector< pii > grafo[N];

vector< int > G[N];
 
ll sz[N], tot = 0;

int dfsnum[N], dfslow[N], cnt, pai[N], ponte[N];

int superpai[N], tam[N];

vector < pii > A;

void dfs(int x)
{
	dfsnum[x] = dfslow[x] = ++cnt;
 
	for(int i = 0; i< grafo[x].size(); i++)
	{
		int v =grafo[x][i].f, id = grafo[x][i].s;
 
		if(!dfsnum[v])
		{
			pai[v] = x;
 
			dfs(v);
 
			if(dfslow[v] > dfsnum[x]) ponte[id] = 1;
 
			dfslow[x] = min(dfslow[v], dfslow[x]);
		}
 
		else if(v != pai[x]) dfslow[x] = min(dfsnum[v], dfslow[x]);
	}
}

void dfspai(int x, int p)
{
	tam[p] ++;

	superpai[x] = p;

	ok[x] = 1;

	for(auto v: grafo[x])
	{
		if(ok[v.f] or ponte[v.s]) continue;

		dfspai(v.f, p);
	}
}
  
void fill(int x, int p)
{
	tot += tam[x];

	for(auto v: G[x])
	{
		if(v == p) continue;

		fill(v, x);
	}
}

void dfs2(int x, int p)
{	
	//cout<<x<<" "<<tam[x]<<"\n";

	sz[x] = tam[x];

	ok[x] = 1;

	ll quadrado = 0, soma = 0, prod2 = 0;

	for(auto v: G[x])
	{
		if(v == p) continue;

		dfs2(v, x);

		quadrado += sz[v] * sz[v];

		soma += sz[v];

		sz[x] += sz[v];

		if(tam[x] >= 2) prod2 += sz[v] * (tam[x] * (tam[x] - 1));
	}

	if(tam[x] >= 2) prod2 += (tot - sz[x]) * (tam[x] * (tam[x] - 1));
	//cout<<"OIIII = "<<x<<" resp = "<<(prod2)<<"\n";

	soma += tot - sz[x];

	quadrado += (tot - sz[x]) * (tot - sz[x]);

	prod2 += (soma * soma - quadrado) * tam[x];

	ans += prod2;

	//cout<<"MID = "<<x<<" resp = "<<prod2<<"\n";
}


int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
  
    cin>>n>>m;    
  
    for(int i = 1, a, b; i <= m; i++)
    {
        cin>>a>>b;
   
        grafo[a].push_back({b, i});
  
        grafo[b].push_back({a, i});

        A.push_back({a, b});
    }

    for(int i = 1; i <= n; i++) if(!dfsnum[i]) dfs(i);

    for(int i = 1; i <= n; i++) if(!ok[i]) dfspai(i, i);

    for(int i = 0; i < m; i++)
    {
    	int a = A[i].f, b = A[i].s;

    	if(superpai[a] != superpai[b])
    	{
    		G[superpai[a]].push_back(superpai[b]);

    		G[superpai[b]].push_back(superpai[a]);

    		//cout<<"A "<<superpai[a]<<" "<<superpai[b]<<"\n";
    	}
    }

    for(int i = 1; i <= n; i++)
    {
    	if(tam[i] <= 2) continue;

    	ans += (tam[i] * (tam[i] - 1) * (tam[i] - 2));
    }

    memset(ok, 0, sizeof ok);

   // cout<<" ---- \n";

    for(int i = 1; i <= n; i++)
    {
  		if(ok[i]) continue;

		tot = 0;

		fill(i, i);

		dfs2(i, i);
    }

    cout<<ans<<"\n";
}

Compilation message

count_triplets.cpp: In function 'void dfs(int)':
count_triplets.cpp:27:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i< grafo[x].size(); i++)
                 ~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5844 KB Output is correct
2 Correct 9 ms 5868 KB Output is correct
3 Correct 8 ms 6044 KB Output is correct
4 Correct 7 ms 6044 KB Output is correct
5 Correct 8 ms 6044 KB Output is correct
6 Correct 8 ms 6100 KB Output is correct
7 Incorrect 7 ms 6100 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 5844 KB Output is correct
2 Correct 9 ms 5868 KB Output is correct
3 Correct 8 ms 6044 KB Output is correct
4 Correct 7 ms 6044 KB Output is correct
5 Correct 8 ms 6044 KB Output is correct
6 Correct 8 ms 6100 KB Output is correct
7 Incorrect 7 ms 6100 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 194 ms 18556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 18556 KB Output is correct
2 Correct 217 ms 18556 KB Output is correct
3 Correct 197 ms 18556 KB Output is correct
4 Correct 164 ms 18556 KB Output is correct
5 Correct 169 ms 18556 KB Output is correct
6 Correct 209 ms 20464 KB Output is correct
7 Correct 268 ms 20464 KB Output is correct
8 Correct 280 ms 20464 KB Output is correct
9 Correct 218 ms 20464 KB Output is correct
10 Correct 211 ms 20464 KB Output is correct
11 Correct 182 ms 20464 KB Output is correct
12 Correct 175 ms 20464 KB Output is correct
13 Correct 254 ms 20464 KB Output is correct
14 Correct 154 ms 20464 KB Output is correct
15 Correct 201 ms 20464 KB Output is correct
16 Correct 120 ms 20464 KB Output is correct
17 Correct 171 ms 20464 KB Output is correct
18 Correct 148 ms 20464 KB Output is correct
19 Correct 122 ms 20464 KB Output is correct
20 Correct 149 ms 20464 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 20464 KB Output is correct
2 Correct 266 ms 20464 KB Output is correct
3 Execution timed out 1157 ms 865336 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5844 KB Output is correct
2 Correct 9 ms 5868 KB Output is correct
3 Correct 8 ms 6044 KB Output is correct
4 Correct 7 ms 6044 KB Output is correct
5 Correct 8 ms 6044 KB Output is correct
6 Correct 8 ms 6100 KB Output is correct
7 Incorrect 7 ms 6100 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 5844 KB Output is correct
2 Correct 9 ms 5868 KB Output is correct
3 Correct 8 ms 6044 KB Output is correct
4 Correct 7 ms 6044 KB Output is correct
5 Correct 8 ms 6044 KB Output is correct
6 Correct 8 ms 6100 KB Output is correct
7 Incorrect 7 ms 6100 KB Output isn't correct
8 Halted 0 ms 0 KB -