oj.uz

Submission #59341

# Submission time Handle Problem Language Result Execution time Memory
59341 2018-07-21T15:13:00 Z MatheusLealV Duathlon (APIO18_duathlon) C++17
23 / 100
 1000 ms 763912 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;

	int qtd = 0;

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

		qtd ++;

		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 -= sz[v] * (tam[x] - 1);

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

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

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

	//if(tam[x] >= 2) prod2 += (tot - sz[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;

	if(qtd == 0)
	{
		if(tam[x] >= 2) prod2 += (tot - sz[x]) * (tam[x] * (tam[x] - 1));

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

	//cout<<"MID = "<<x<<" resp = "<<prod2<<" "<<tot<<" "<<sz[x]<<" "<<tam[x]<<"\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 5880 KB Output is correct
2 Correct 7 ms 5956 KB Output is correct
3 Correct 7 ms 5956 KB Output is correct
4 Correct 7 ms 5964 KB Output is correct
5 Correct 7 ms 6148 KB Output is correct
6 Correct 7 ms 6148 KB Output is correct
7 Incorrect 8 ms 6148 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 5880 KB Output is correct
2 Correct 7 ms 5956 KB Output is correct
3 Correct 7 ms 5956 KB Output is correct
4 Correct 7 ms 5964 KB Output is correct
5 Correct 7 ms 6148 KB Output is correct
6 Correct 7 ms 6148 KB Output is correct
7 Incorrect 8 ms 6148 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 155 ms 18548 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 18548 KB Output is correct
2 Correct 9 ms 18548 KB Output is correct
3 Correct 10 ms 18548 KB Output is correct
4 Correct 10 ms 18548 KB Output is correct
5 Correct 7 ms 18548 KB Output is correct
6 Correct 7 ms 18548 KB Output is correct
7 Correct 8 ms 18548 KB Output is correct
8 Correct 8 ms 18548 KB Output is correct
9 Correct 8 ms 18548 KB Output is correct
10 Correct 11 ms 18548 KB Output is correct
11 Correct 7 ms 18548 KB Output is correct
12 Correct 8 ms 18548 KB Output is correct
13 Correct 7 ms 18548 KB Output is correct
14 Correct 9 ms 18548 KB Output is correct
15 Correct 9 ms 18548 KB Output is correct
16 Correct 9 ms 18548 KB Output is correct
17 Correct 8 ms 18548 KB Output is correct
18 Correct 8 ms 18548 KB Output is correct
19 Correct 8 ms 18548 KB Output is correct
20 Correct 10 ms 18548 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 18548 KB Output is correct
2 Correct 216 ms 18548 KB Output is correct
3 Correct 192 ms 18548 KB Output is correct
4 Correct 226 ms 18548 KB Output is correct
5 Correct 179 ms 18548 KB Output is correct
6 Correct 230 ms 20592 KB Output is correct
7 Correct 222 ms 20592 KB Output is correct
8 Correct 248 ms 20592 KB Output is correct
9 Correct 200 ms 20592 KB Output is correct
10 Correct 248 ms 20592 KB Output is correct
11 Correct 247 ms 20592 KB Output is correct
12 Correct 191 ms 20592 KB Output is correct
13 Correct 205 ms 20592 KB Output is correct
14 Correct 163 ms 20592 KB Output is correct
15 Correct 145 ms 20592 KB Output is correct
16 Correct 108 ms 20592 KB Output is correct
17 Correct 109 ms 20592 KB Output is correct
18 Correct 170 ms 20592 KB Output is correct
19 Correct 154 ms 20592 KB Output is correct
20 Correct 147 ms 20592 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 20592 KB Output is correct
2 Correct 234 ms 20592 KB Output is correct
3 Execution timed out 1137 ms 763912 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 5880 KB Output is correct
2 Correct 7 ms 5956 KB Output is correct
3 Correct 7 ms 5956 KB Output is correct
4 Correct 7 ms 5964 KB Output is correct
5 Correct 7 ms 6148 KB Output is correct
6 Correct 7 ms 6148 KB Output is correct
7 Incorrect 8 ms 6148 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 5880 KB Output is correct
2 Correct 7 ms 5956 KB Output is correct
3 Correct 7 ms 5956 KB Output is correct
4 Correct 7 ms 5964 KB Output is correct
5 Correct 7 ms 6148 KB Output is correct
6 Correct 7 ms 6148 KB Output is correct
7 Incorrect 8 ms 6148 KB Output isn't correct
8 Halted 0 ms 0 KB -