oj.uz

Submission #61411

# Submission time Handle Problem Language Result Execution time Memory
61411 2018-07-25T20:51:11 Z kingpig9 Duathlon (APIO18_duathlon) C++11
31 / 100
 251 ms 44644 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 cpar[MAXN];
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));
		cpar[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 pans = ans;
		ans += 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]) {
			ans -= sqr(sub[y]);
			debug("y ans -= %d^2\n", sub[y]);
		}
		debug("all3indiff = %lld\n", ans - pans);

		//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:147:2: warning: #warning RESET AT THE END! [-Wcpp]
 #warning RESET AT THE END!
  ^~~~~~~
count_triplets.cpp: In function 'll go(int)':
count_triplets.cpp:124:6: warning: unused variable 'pans' [-Wunused-variable]
   ll pans = ans;
      ^~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:154: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:157: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 8 ms 6612 KB Output is correct
2 Correct 9 ms 6632 KB Output is correct
3 Correct 10 ms 6816 KB Output is correct
4 Correct 10 ms 6816 KB Output is correct
5 Correct 10 ms 6816 KB Output is correct
6 Correct 10 ms 6816 KB Output is correct
7 Incorrect 11 ms 6916 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6612 KB Output is correct
2 Correct 9 ms 6632 KB Output is correct
3 Correct 10 ms 6816 KB Output is correct
4 Correct 10 ms 6816 KB Output is correct
5 Correct 10 ms 6816 KB Output is correct
6 Correct 10 ms 6816 KB Output is correct
7 Incorrect 11 ms 6916 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 237 ms 23992 KB Output is correct
2 Correct 209 ms 25312 KB Output is correct
3 Correct 214 ms 25312 KB Output is correct
4 Correct 251 ms 26256 KB Output is correct
5 Correct 184 ms 26256 KB Output is correct
6 Correct 199 ms 26904 KB Output is correct
7 Correct 220 ms 26904 KB Output is correct
8 Correct 203 ms 26904 KB Output is correct
9 Correct 236 ms 26904 KB Output is correct
10 Correct 242 ms 27228 KB Output is correct
11 Correct 180 ms 27228 KB Output is correct
12 Correct 187 ms 27228 KB Output is correct
13 Correct 167 ms 27768 KB Output is correct
14 Correct 114 ms 28516 KB Output is correct
15 Correct 127 ms 29020 KB Output is correct
16 Correct 108 ms 29432 KB Output is correct
17 Correct 16 ms 29432 KB Output is correct
18 Correct 17 ms 29432 KB Output is correct
19 Correct 16 ms 29432 KB Output is correct
20 Correct 13 ms 29432 KB Output is correct
21 Correct 12 ms 29432 KB Output is correct
22 Correct 15 ms 29432 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 33000 KB Output is correct
2 Correct 212 ms 33000 KB Output is correct
3 Correct 219 ms 33128 KB Output is correct
4 Correct 175 ms 33132 KB Output is correct
5 Correct 157 ms 33132 KB Output is correct
6 Correct 234 ms 44644 KB Output is correct
7 Correct 185 ms 44644 KB Output is correct
8 Correct 220 ms 44644 KB Output is correct
9 Correct 229 ms 44644 KB Output is correct
10 Correct 176 ms 44644 KB Output is correct
11 Correct 169 ms 44644 KB Output is correct
12 Correct 180 ms 44644 KB Output is correct
13 Correct 216 ms 44644 KB Output is correct
14 Correct 148 ms 44644 KB Output is correct
15 Correct 170 ms 44644 KB Output is correct
16 Correct 95 ms 44644 KB Output is correct
17 Correct 112 ms 44644 KB Output is correct
18 Correct 156 ms 44644 KB Output is correct
19 Correct 112 ms 44644 KB Output is correct
20 Correct 201 ms 44644 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 44644 KB Output is correct
2 Correct 189 ms 44644 KB Output is correct
3 Incorrect 200 ms 44644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6612 KB Output is correct
2 Correct 9 ms 6632 KB Output is correct
3 Correct 10 ms 6816 KB Output is correct
4 Correct 10 ms 6816 KB Output is correct
5 Correct 10 ms 6816 KB Output is correct
6 Correct 10 ms 6816 KB Output is correct
7 Incorrect 11 ms 6916 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6612 KB Output is correct
2 Correct 9 ms 6632 KB Output is correct
3 Correct 10 ms 6816 KB Output is correct
4 Correct 10 ms 6816 KB Output is correct
5 Correct 10 ms 6816 KB Output is correct
6 Correct 10 ms 6816 KB Output is correct
7 Incorrect 11 ms 6916 KB Output isn't correct
8 Halted 0 ms 0 KB -