oj.uz

Submission #59327

# Submission time Handle Problem Language Result Execution time Memory
59327 2018-07-21T14:17:09 Z MatheusLealV Duathlon (APIO18_duathlon) C++17
0 / 100
 1000 ms 697432 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] = ok[x] = tam[x];

	ll quadrado = 0, soma = 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) ans += sz[v] * (tam[x] * (tam[x] - 1));
	}

	if(tam[x] >= 2) ans += (tot - sz[x]) * (tam[x] * (tam[x] - 1));

	soma += tot - sz[x];

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

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

	ans += prod2;
}


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]);
    	}
    }

    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 <= 1; 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 9 ms 5880 KB Output is correct
2 Correct 9 ms 5952 KB Output is correct
3 Correct 8 ms 5952 KB Output is correct
4 Correct 8 ms 6080 KB Output is correct
5 Correct 7 ms 6088 KB Output is correct
6 Correct 7 ms 6136 KB Output is correct
7 Incorrect 7 ms 6136 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5880 KB Output is correct
2 Correct 9 ms 5952 KB Output is correct
3 Correct 8 ms 5952 KB Output is correct
4 Correct 8 ms 6080 KB Output is correct
5 Correct 7 ms 6088 KB Output is correct
6 Correct 7 ms 6136 KB Output is correct
7 Incorrect 7 ms 6136 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 17816 KB Output is correct
2 Correct 239 ms 17816 KB Output is correct
3 Correct 206 ms 17816 KB Output is correct
4 Correct 206 ms 17816 KB Output is correct
5 Correct 192 ms 17816 KB Output is correct
6 Correct 281 ms 20476 KB Output is correct
7 Correct 257 ms 20476 KB Output is correct
8 Correct 255 ms 20476 KB Output is correct
9 Correct 236 ms 20476 KB Output is correct
10 Incorrect 216 ms 20476 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 20476 KB Output is correct
2 Correct 208 ms 20476 KB Output is correct
3 Execution timed out 1110 ms 697432 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5880 KB Output is correct
2 Correct 9 ms 5952 KB Output is correct
3 Correct 8 ms 5952 KB Output is correct
4 Correct 8 ms 6080 KB Output is correct
5 Correct 7 ms 6088 KB Output is correct
6 Correct 7 ms 6136 KB Output is correct
7 Incorrect 7 ms 6136 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5880 KB Output is correct
2 Correct 9 ms 5952 KB Output is correct
3 Correct 8 ms 5952 KB Output is correct
4 Correct 8 ms 6080 KB Output is correct
5 Correct 7 ms 6088 KB Output is correct
6 Correct 7 ms 6136 KB Output is correct
7 Incorrect 7 ms 6136 KB Output isn't correct
8 Halted 0 ms 0 KB -