1017D - The Wu

I write a solution of O(4^n), and it gets TLE on test 4. I found a code which is also O(4^n) and passed in 300ms, deleted three blocks of my code, and insert 3 blocks from another code and then, a miracle happened — it gets TLE.

My code is here:

// Problem: D. The Wu
// Contest: Codeforces - Codeforces Round 502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2)
// URL: https://codeforces.me/problemset/problem/1017/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

int w[15], cnt[4100];
int ans[4100][105];

void dfs(int u, int v, int n, int pos, int sum) {
	if (pos == n) {
		ans[u][min(sum, 101)] += cnt[v];
		return;
	}
	int x = (u >> pos) & 1;
	dfs(u, v | (x << pos), n, pos + 1, sum + w[pos]);
	dfs(u, v | ((x ^ 1) << pos), n, pos + 1, sum);
}

int main() {
	int n, m, q;
	scanf("%d %d %d", &n, &m, &q);
	for (int i = 0; i < n; i++) {
		scanf("%d", &w[n - i - 1]);
	}
	for (int i = 0; i < m; i++) {
		string s;
		cin >> s;
		int x = 0;
		for (char ch : s) {
			x = (x << 1) + (ch == '1');
		}
		cnt[x]++;
	}
	for (int i = 0; i < (1 << n); i++) {
		dfs(i, 0, n, 0, 0);
		for (int j = 1; j <= 100; j++) {
			ans[i][j] += ans[i][j - 1];
		}
	}
	while (q--) {
		string s;
		int lim;
		cin >> s >> lim;
		int x = 0;
		for (char ch : s) {
			x = (x << 1) + (ch == '1');
		}
		printf("%d\n", ans[x][lim]);
	}
}

and sand when I am 6

and toys when I am 7

and TV when I am 8

and video games when I am 9

and programming on Codeforces and Atcoder when I am 10 and 11 (now)

Problem: ABC188E

#include <bits/stdc++.h>
using namespace std;

int a[200005], f[200005];
vector<int> pre[200005];

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = 0; i < m; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		x--, y--;
		pre[y].push_back(x);
	}
	memset(f, 0x3f, sizeof f);
	int ans = -0x3f3f3f3f;
	for (int i = 0; i < n; i++) {
		for (int j : pre[i]) {
			f[i] = min(f[i], f[j]);
			f[i] = min(f[i], a[j]);
		}
		ans = max(ans, a[i] - f[i]);
	}
	printf("%d", ans);
	return 0;
}

I had increase the "infinity" in array f, and I found that when f[i] = 0x3f3f3f3f + 0x3f3f2f2f, it passed , when f[i] = 0x3f3f3f3f + 0x2f2f2f2f, it WA on test #6. I had no idea about it. Could anyone give a test to hack it?

Today, I find some topics in this form......

This type of topics always say a lot of things of ******, and at last post a drawing of him/her.

So who started this type of topics???

So this is my code to ABC279F:

#include <bits/stdc++.h>
using namespace std;

int fa[600005];

void init() {
	memset(fa, -1, sizeof fa);
}

int find_root(int x) {
	if (fa[x] == -1) {
		return x;
	}
	return fa[x] = find_root(fa[x]);
}

void unite(int x, int y) {
	if (find_root(x) != find_root(y) && find_root(x) != -1) {
		fa[find_root(x)] = find_root(y);
	}
}

int now[300005], idx[300005], past[600005];

int main() {
	init();
	int n, q;
	scanf("%d %d", &n, &q);
	for (int i = 0; i < n; i++) {
		now[i] = i;
		past[i] = i;
		idx[i] = i;
	}
	int cntn = n - 1;
	int cnt = n - 1;
	while (q--) {
		int tp;
		scanf("%d", &tp);
		if (tp == 1) {
			int x, y;
			scanf("%d %d", &x, &y);
			x--, y--;
			unite(now[y], now[x]);
			now[y] = ++cntn;
			past[cntn] = y;
		} else if (tp == 2) {
			int x;
			scanf("%d", &x);
			x--;
			idx[++cnt] = now[x];
		} else {
			int x;
			scanf("%d", &x);
			x--;
			printf("%d\n", past[find_root(idx[x])] + 1);
		}
//		for (int i = 0; i < n; i++) {
//			cerr << now[i] << " ";
//		}
//		cerr << endl;
	}
	return 0;
}

It should be RE (Though the size of "idx" is 300005), but it judged as WA.

Why?

And it wasted me a lot of time :(