oj.uz

답안 #51967

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51967 2018-06-22T18:44:12 Z pzdba 철인 이종 경기 (APIO18_duathlon) C++14
31 / 100
 201 ms 23424 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;

pii edges[200005];
vector<pii> g[100005];
bool idx[200005];
int low[100005], vis[100005], p[100005];
LL sz[100005], T = 1;
void dfs1(int u, int p){
	vis[u] = low[u] = T++;
	for(int i=0;i<g[u].size();i++){
		int v = g[u][i].first;
		if(v == p) continue;
		if(vis[v]) low[u] = min(low[u], vis[v]);
		else{
			dfs1(v, u);
			low[u] = min(low[u], low[v]);
			if(low[v] > vis[u]) idx[g[u][i].second] = 1;
		}
	}
}

int root(int a){
	while(p[a] != a){
		p[a] = p[p[a]];
		a = p[a];
	}
	return a;
}
bool merge(int a, int b){
	a = root(a), b = root(b);
	if(a == b) return 0;
	sz[b] += sz[a];
	p[a] = b;
	return 1;
}

vector<int> scc[200005];
LL s[100005], sc[100005];
LL ans = 0;

void dfs2(int u, int p, int r){
	vis[u] = 1;
	s[u] += sz[u];
	sc[u] += (sz[u]-1)*(sz[u]-1);
	for(int i=0;i<scc[u].size();i++){
		int cur = scc[u][i];

		LL s1 = 0, sc1 = 0;
		for(int j=0;j<g[cur].size();j++){
			int v = g[cur][j].first, edge = g[cur][j].second;
			int rv = root(v);
			if(!idx[edge]) continue;
			if(rv == p) continue;
			dfs2(rv, u, v);

			ans += sc[rv]*s[u]; // sc - f
			ans += s[rv]*sc[u]; // s - cf 

			ans += s[rv]*s1; // s - c - f

			s1 += s[rv];
			s[u] += s[rv];
			sc[u] += sc[rv];
		}

		for(int j=0;j<g[cur].size();j++){
			int v = g[cur][j].first, edge = g[cur][j].second;
			int rv = root(v);
			if(!idx[edge]) continue;
			if(rv == p) continue;

			if(cur == r) sc[u] += s[rv];
			else sc[u] += s[rv]*s[u];
		}
	}
}

int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i=0;i<m;i++){
		int a, b;
		scanf("%d%d", &a, &b);
		g[a].push_back(pii(b, i));
		g[b].push_back(pii(a, i));
		edges[i] = pii(a, b);
	}
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
		dfs1(i, 0);
	}
	for(int i=1;i<=n;i++) p[i] = i, sz[i] = 1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<g[i].size();j++){
			int v = g[i][j].first, edge = g[i][j].second;
			if(!idx[edge]){
				merge(i, v);
			}
		}
	}
	for(int i=1;i<=n;i++){
		scc[root(i)].push_back(i);
	}
	memset(vis, 0, sizeof(vis));
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
	 	if(root(i) == i) dfs2(i, 0, 0);
	}
	ans *= 2;
	for(int i=1;i<=n;i++){
		if(root(i) == i){
			ans += (LL)sz[i]*(sz[i]-1)*(sz[i]-2);
		}
	}
	printf("%lld\n", ans);
}

Compilation message

count_triplets.cpp: In function 'void dfs1(int, int)':
count_triplets.cpp:13:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[u].size();i++){
              ~^~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs2(int, int, int)':
count_triplets.cpp:48:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<scc[u].size();i++){
              ~^~~~~~~~~~~~~~
count_triplets.cpp:52:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<g[cur].size();j++){
               ~^~~~~~~~~~~~~~
count_triplets.cpp:69:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<g[cur].size();j++){
               ~^~~~~~~~~~~~~~
count_triplets.cpp:51:14: warning: unused variable 'sc1' [-Wunused-variable]
   LL s1 = 0, sc1 = 0;
              ^~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:97:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<g[i].size();j++){
               ~^~~~~~~~~~~~
count_triplets.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
count_triplets.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7800 KB Output is correct
2 Correct 8 ms 7800 KB Output is correct
3 Correct 8 ms 7984 KB Output is correct
4 Correct 8 ms 7984 KB Output is correct
5 Correct 8 ms 7984 KB Output is correct
6 Correct 8 ms 7984 KB Output is correct
7 Incorrect 8 ms 7984 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7800 KB Output is correct
2 Correct 8 ms 7800 KB Output is correct
3 Correct 8 ms 7984 KB Output is correct
4 Correct 8 ms 7984 KB Output is correct
5 Correct 8 ms 7984 KB Output is correct
6 Correct 8 ms 7984 KB Output is correct
7 Incorrect 8 ms 7984 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 120 ms 21964 KB Output is correct
2 Correct 128 ms 21964 KB Output is correct
3 Correct 163 ms 21964 KB Output is correct
4 Correct 138 ms 22084 KB Output is correct
5 Correct 141 ms 22084 KB Output is correct
6 Correct 133 ms 22084 KB Output is correct
7 Correct 128 ms 22084 KB Output is correct
8 Correct 181 ms 22084 KB Output is correct
9 Correct 113 ms 22084 KB Output is correct
10 Correct 120 ms 22084 KB Output is correct
11 Correct 122 ms 22084 KB Output is correct
12 Correct 108 ms 22084 KB Output is correct
13 Correct 141 ms 22084 KB Output is correct
14 Correct 95 ms 22084 KB Output is correct
15 Correct 74 ms 22084 KB Output is correct
16 Correct 85 ms 22084 KB Output is correct
17 Correct 19 ms 22084 KB Output is correct
18 Correct 20 ms 22084 KB Output is correct
19 Correct 26 ms 22084 KB Output is correct
20 Correct 19 ms 22084 KB Output is correct
21 Correct 20 ms 22084 KB Output is correct
22 Correct 20 ms 22084 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 120 ms 22084 KB Output is correct
2 Correct 119 ms 22084 KB Output is correct
3 Correct 124 ms 22084 KB Output is correct
4 Correct 117 ms 22084 KB Output is correct
5 Correct 110 ms 22084 KB Output is correct
6 Correct 201 ms 23424 KB Output is correct
7 Correct 137 ms 23424 KB Output is correct
8 Correct 136 ms 23424 KB Output is correct
9 Correct 140 ms 23424 KB Output is correct
10 Correct 116 ms 23424 KB Output is correct
11 Correct 115 ms 23424 KB Output is correct
12 Correct 121 ms 23424 KB Output is correct
13 Correct 113 ms 23424 KB Output is correct
14 Correct 130 ms 23424 KB Output is correct
15 Correct 112 ms 23424 KB Output is correct
16 Correct 79 ms 23424 KB Output is correct
17 Correct 91 ms 23424 KB Output is correct
18 Correct 95 ms 23424 KB Output is correct
19 Correct 97 ms 23424 KB Output is correct
20 Correct 97 ms 23424 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 23424 KB Output is correct
2 Correct 161 ms 23424 KB Output is correct
3 Incorrect 181 ms 23424 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7800 KB Output is correct
2 Correct 8 ms 7800 KB Output is correct
3 Correct 8 ms 7984 KB Output is correct
4 Correct 8 ms 7984 KB Output is correct
5 Correct 8 ms 7984 KB Output is correct
6 Correct 8 ms 7984 KB Output is correct
7 Incorrect 8 ms 7984 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7800 KB Output is correct
2 Correct 8 ms 7800 KB Output is correct
3 Correct 8 ms 7984 KB Output is correct
4 Correct 8 ms 7984 KB Output is correct
5 Correct 8 ms 7984 KB Output is correct
6 Correct 8 ms 7984 KB Output is correct
7 Incorrect 8 ms 7984 KB Output isn't correct
8 Halted 0 ms 0 KB -