답안 #59328 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59328	2018-07-21T14:18:51 Z	MatheusLealV	철인 이종 경기 (APIO18_duathlon)	C++17	23 / 100	1000 ms	882820 KB

count_triplets

#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;

	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 <= 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

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5880 KB	Output is correct
2	Correct	7 ms	5960 KB	Output is correct
3	Correct	8 ms	5960 KB	Output is correct
4	Correct	7 ms	5996 KB	Output is correct
5	Correct	7 ms	5996 KB	Output is correct
6	Correct	7 ms	6072 KB	Output is correct
7	Incorrect	10 ms	6120 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5880 KB	Output is correct
2	Correct	7 ms	5960 KB	Output is correct
3	Correct	8 ms	5960 KB	Output is correct
4	Correct	7 ms	5996 KB	Output is correct
5	Correct	7 ms	5996 KB	Output is correct
6	Correct	7 ms	6072 KB	Output is correct
7	Incorrect	10 ms	6120 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #3
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	181 ms	18668 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	246 ms	18668 KB	Output is correct
2	Correct	294 ms	18668 KB	Output is correct
3	Correct	275 ms	18668 KB	Output is correct
4	Correct	226 ms	18668 KB	Output is correct
5	Correct	255 ms	18668 KB	Output is correct
6	Correct	287 ms	20588 KB	Output is correct
7	Correct	301 ms	20588 KB	Output is correct
8	Correct	209 ms	20588 KB	Output is correct
9	Correct	193 ms	20588 KB	Output is correct
10	Correct	206 ms	20588 KB	Output is correct
11	Correct	149 ms	20588 KB	Output is correct
12	Correct	159 ms	20588 KB	Output is correct
13	Correct	156 ms	20588 KB	Output is correct
14	Correct	178 ms	20588 KB	Output is correct
15	Correct	194 ms	20588 KB	Output is correct
16	Correct	111 ms	20588 KB	Output is correct
17	Correct	138 ms	20588 KB	Output is correct
18	Correct	177 ms	20588 KB	Output is correct
19	Correct	148 ms	20588 KB	Output is correct
20	Correct	138 ms	20588 KB	Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	194 ms	20588 KB	Output is correct
2	Correct	218 ms	20588 KB	Output is correct
3	Execution timed out	1153 ms	882820 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5880 KB	Output is correct
2	Correct	7 ms	5960 KB	Output is correct
3	Correct	8 ms	5960 KB	Output is correct
4	Correct	7 ms	5996 KB	Output is correct
5	Correct	7 ms	5996 KB	Output is correct
6	Correct	7 ms	6072 KB	Output is correct
7	Incorrect	10 ms	6120 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5880 KB	Output is correct
2	Correct	7 ms	5960 KB	Output is correct
3	Correct	8 ms	5960 KB	Output is correct
4	Correct	7 ms	5996 KB	Output is correct
5	Correct	7 ms	5996 KB	Output is correct
6	Correct	7 ms	6072 KB	Output is correct
7	Incorrect	10 ms	6120 KB	Output isn't correct
8	Halted	0 ms	0 KB	-