답안 #59329 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59329	2018-07-21T14:30:29 Z	MatheusLealV	철인 이종 경기 (APIO18_duathlon)	C++17	23 / 100	1000 ms	865336 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, 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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

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

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-