oj.uz

Submission #61412

# Submission time Handle Problem Language Result Execution time Memory
61412 2018-07-25T21:15:03 Z kingpig9 Duathlon (APIO18_duathlon) C++11
31 / 100
 276 ms 27496 KB 
#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 debug(...)
#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];
	}
};

int N, M;
vector<int> adj[MAXN];
vector<int> verts;
int par[MAXN], depth[MAXN];
bool vis[MAXN];
union_find uf = union_find();
union_find cy = union_find();	//cycle components

void dfs (int x, int p) {
	debug("x = %d\n", x);
	verts.push_back(x);
	vis[x] = true;
	par[x] = p;

	for (int y : adj[x]) {
		if (y != p) {
			if (vis[y]) {
				if (depth[y] < depth[x]) {
					//then it's a component
					for (int i = x; ; i = par[i]) {
						cy.merge(x, i);
						debug("merge(%d, %d)\n", x, i);
						if (i == y) {
							break;
						}
					}
				}
			} else {
				depth[y] = depth[x] + 1;
				dfs(y, x);
			}
		}
	}
}

vector<int> cadj[MAXN];	//comp adjacent
int sub[MAXN];
vector<int> cverts;

void dfsc (int x) {
	cverts.push_back(x);
	sub[x] = cy.sz[x];
	for (int y : cadj[x]) {
		cadj[y].erase(find(all(cadj[y]), x));
		dfsc(y);
		sub[x] += sub[y];
	}
}

ll go (int root) {
	dfs(root, 0);
	for (int x : verts) {
		int fx = cy.find(x);
		for (int y : adj[x]) {
			int fy = cy.find(y);
			if (fx != fy) {
				cadj[fx].push_back(fy);
				debug("CADJ %d %d\n", fx, fy);
			}
		}
	}

	int szroot = uf.sz[root];
	int froot = cy.find(root);
	dfsc(froot);

	//ok let's consider when the stuff is good!
	ll ans = 0;

	debug("WE HAVE szroot = %d\n", szroot);
	for (int c : cverts) {
		//all 3 are in the same component
		ll s = cy.sz[c];
		ans += s * (s - 1) * (s - 2);
		debug("s = %lld\n", s);

		//all 3 are in different component. c is the transition.
		ll ncho2 = 0;
		ncho2 += sqr(szroot - s) - sqr(szroot - sub[c]);
		debug("c = %d. sub[c] = %d\n", c, sub[c]);
		debug("ans += %lld^2\n", szroot - s);
		debug("ans -= %d^2\n", szroot - sub[c]);
		for (int y : cadj[c]) {
			ncho2 -= sqr(sub[y]);
			debug("y ans -= %d^2\n", sub[y]);
		}
		debug("all3indiff = %lld\n", ans - pans);
		ans += ncho2 * s;

		//the stuff right below this comment is actually wrong.
		/*
		//two of them are in this component. one of them is in different component
		debug("s = %lld. szroot = %d. So we add %lld\n", s, szroot, 2 * s * (s - 1) * (szroot - s));
		ans += 2 * s * (s - 1) * (szroot - s);	//ans += 4 * C(s, 2) * (szroot - s)
		*/

		//ok now this may be correct...
		ans += 2 * s * (s - 1) * (szroot - s);	//ans += 4 * C(s, 2) * (szroot - s)
		ans -= 2 * (s - 1) * (szroot - s);
	}

#warning RESET AT THE END!
	verts.clear();
	cverts.clear();
	return ans;
}

int main() {
	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);
	}

	ll ans = 0;
	for (int i = 1; i <= N; i++) {
		if (i == uf.find(i)) {
			ans += go(i);
		}
	}
	printf("%lld\n", ans);
}

Compilation message

count_triplets.cpp:146:2: warning: #warning RESET AT THE END! [-Wcpp]
 #warning RESET AT THE END!
  ^~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:153: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:156: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

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6520 KB Output is correct
2 Correct 10 ms 6756 KB Output is correct
3 Correct 10 ms 6756 KB Output is correct
4 Correct 10 ms 6840 KB Output is correct
5 Correct 9 ms 6840 KB Output is correct
6 Correct 10 ms 6840 KB Output is correct
7 Incorrect 9 ms 6840 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6520 KB Output is correct
2 Correct 10 ms 6756 KB Output is correct
3 Correct 10 ms 6756 KB Output is correct
4 Correct 10 ms 6840 KB Output is correct
5 Correct 9 ms 6840 KB Output is correct
6 Correct 10 ms 6840 KB Output is correct
7 Incorrect 9 ms 6840 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 23864 KB Output is correct
2 Correct 162 ms 23944 KB Output is correct
3 Correct 171 ms 23944 KB Output is correct
4 Correct 168 ms 23944 KB Output is correct
5 Correct 217 ms 23944 KB Output is correct
6 Correct 167 ms 23944 KB Output is correct
7 Correct 210 ms 23944 KB Output is correct
8 Correct 259 ms 23944 KB Output is correct
9 Correct 165 ms 23944 KB Output is correct
10 Correct 230 ms 23944 KB Output is correct
11 Correct 137 ms 23944 KB Output is correct
12 Correct 127 ms 23944 KB Output is correct
13 Correct 139 ms 23944 KB Output is correct
14 Correct 136 ms 23944 KB Output is correct
15 Correct 119 ms 23944 KB Output is correct
16 Correct 118 ms 23944 KB Output is correct
17 Correct 15 ms 23944 KB Output is correct
18 Correct 17 ms 23944 KB Output is correct
19 Correct 14 ms 23944 KB Output is correct
20 Correct 14 ms 23944 KB Output is correct
21 Correct 16 ms 23944 KB Output is correct
22 Correct 15 ms 23944 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23944 KB Output is correct
2 Correct 12 ms 23944 KB Output is correct
3 Correct 9 ms 23944 KB Output is correct
4 Correct 9 ms 23944 KB Output is correct
5 Correct 11 ms 23944 KB Output is correct
6 Correct 8 ms 23944 KB Output is correct
7 Correct 12 ms 23944 KB Output is correct
8 Correct 10 ms 23944 KB Output is correct
9 Correct 10 ms 23944 KB Output is correct
10 Correct 10 ms 23944 KB Output is correct
11 Correct 8 ms 23944 KB Output is correct
12 Correct 10 ms 23944 KB Output is correct
13 Correct 10 ms 23944 KB Output is correct
14 Correct 10 ms 23944 KB Output is correct
15 Correct 11 ms 23944 KB Output is correct
16 Correct 9 ms 23944 KB Output is correct
17 Correct 10 ms 23944 KB Output is correct
18 Correct 9 ms 23944 KB Output is correct
19 Correct 9 ms 23944 KB Output is correct
20 Correct 8 ms 23944 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 23944 KB Output is correct
2 Correct 177 ms 23944 KB Output is correct
3 Correct 214 ms 23944 KB Output is correct
4 Correct 276 ms 23944 KB Output is correct
5 Correct 218 ms 23944 KB Output is correct
6 Correct 248 ms 27496 KB Output is correct
7 Correct 171 ms 27496 KB Output is correct
8 Correct 161 ms 27496 KB Output is correct
9 Correct 216 ms 27496 KB Output is correct
10 Correct 219 ms 27496 KB Output is correct
11 Correct 262 ms 27496 KB Output is correct
12 Correct 275 ms 27496 KB Output is correct
13 Correct 254 ms 27496 KB Output is correct
14 Correct 204 ms 27496 KB Output is correct
15 Correct 194 ms 27496 KB Output is correct
16 Correct 107 ms 27496 KB Output is correct
17 Correct 142 ms 27496 KB Output is correct
18 Correct 173 ms 27496 KB Output is correct
19 Correct 176 ms 27496 KB Output is correct
20 Correct 153 ms 27496 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 27496 KB Output is correct
2 Correct 234 ms 27496 KB Output is correct
3 Incorrect 241 ms 27496 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6520 KB Output is correct
2 Correct 10 ms 6756 KB Output is correct
3 Correct 10 ms 6756 KB Output is correct
4 Correct 10 ms 6840 KB Output is correct
5 Correct 9 ms 6840 KB Output is correct
6 Correct 10 ms 6840 KB Output is correct
7 Incorrect 9 ms 6840 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6520 KB Output is correct
2 Correct 10 ms 6756 KB Output is correct
3 Correct 10 ms 6756 KB Output is correct
4 Correct 10 ms 6840 KB Output is correct
5 Correct 9 ms 6840 KB Output is correct
6 Correct 10 ms 6840 KB Output is correct
7 Incorrect 9 ms 6840 KB Output isn't correct
8 Halted 0 ms 0 KB -