답안 #61402 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
61402	2018-07-25T18:51:17 Z	kingpig9	철인 이종 경기 (APIO18_duathlon)	C++11	23 / 100	193 ms	32580 KB

count_triplets

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5 + 10;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

ll sqr (ll x) {
	return x * x;
}

struct union_find {
	int par[MAXN];
	int sz[MAXN];
	union_find() {
		for (int i = 0; i < MAXN; i++) {
			par[i] = i;
			sz[i] = 1;
		}
	}

	int find (int x) {
		return x == par[x] ? x : par[x] = find(par[x]);
	}

	void merge (int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) {
			return;
		}
		par[x] = y;
		sz[y] += sz[x];
	}
} uf = union_find();

int N, M;
vector<int> adj[MAXN];
int sub[MAXN];

void dfs (int x) {
	sub[x] = 1;

	for (int y : adj[x]) {
		adj[y].erase(find(all(adj[y]), x));
		dfs(y);
		sub[x] += sub[y];
	}
}

int main() {
	//subtask 5
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= M; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		adj[x].push_back(y);
		adj[y].push_back(x);
		uf.merge(x, y);
	}

	for (int i = 1; i <= N; i++) {
		if (i == uf.find(i)) {
			dfs(i);
		}
	}

	ll ans = 0;
	for (int c = 1; c <= N; c++) {
		int sz = uf.sz[uf.find(c)];
		ans += sqr(sz - 1) - sqr(sz - sub[c]);
		for (int y : adj[c]) {
			ans -= sqr(sub[y]);
		}
	}
	printf("%lld\n", ans);
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:60: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:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	10 ms	6904 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	10 ms	6904 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	193 ms	26572 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	134 ms	26572 KB	Output is correct
2	Correct	136 ms	26572 KB	Output is correct
3	Correct	144 ms	26572 KB	Output is correct
4	Correct	111 ms	26572 KB	Output is correct
5	Correct	104 ms	26572 KB	Output is correct
6	Correct	167 ms	26572 KB	Output is correct
7	Correct	125 ms	26572 KB	Output is correct
8	Correct	138 ms	26572 KB	Output is correct
9	Correct	152 ms	26572 KB	Output is correct
10	Correct	110 ms	26572 KB	Output is correct
11	Correct	109 ms	26572 KB	Output is correct
12	Correct	119 ms	26572 KB	Output is correct
13	Correct	134 ms	26572 KB	Output is correct
14	Correct	138 ms	26572 KB	Output is correct
15	Correct	139 ms	26572 KB	Output is correct
16	Correct	89 ms	26572 KB	Output is correct
17	Correct	105 ms	29240 KB	Output is correct
18	Correct	77 ms	30236 KB	Output is correct
19	Correct	87 ms	31624 KB	Output is correct
20	Correct	74 ms	32580 KB	Output is correct

Subtask #6
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	32580 KB	Output is correct
2	Correct	6 ms	32580 KB	Output is correct
3	Runtime error	11 ms	32580 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	121 ms	32580 KB	Output is correct
2	Correct	132 ms	32580 KB	Output is correct
3	Runtime error	138 ms	32580 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	10 ms	6904 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	10 ms	6904 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-