QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#129031#5445. VulpeculazhoukangyangML 2370ms225064kbC++113.7kb2023-07-21 19:39:262023-07-21 19:39:27

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-21 19:39:27]
  • 评测
  • 测评结果:ML
  • 用时:2370ms
  • 内存:225064kb
  • [2023-07-21 19:39:26]
  • 提交

answer

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long 
#define vi vector < int > 
#define sz(a) ((int) (a).size())
#define ll long long 
#define ull unsigned long long
#define me(a, x) memset(a, x, sizeof(a)) 
using namespace std;
const int N = 5e4 + 7;
struct lb {
	ull f[64];
	lb() {
		me(f, 0);
	}
	ull & operator [] (int x) {
		return f[x];
	}
	void insert (ull x) {
		R(i, 63, 0) if(x >> i & 1) {
			if(!f[i]) f[i] = x;
			x ^= f[i];
		}
	}
	bool check(ull x) {
		R(i, 63, 0) if(x >> i & 1) {
			if(!f[i]) return false;
			x ^= f[i];
		}
		return true;
	}
	void clear () {
		me(f, 0);
	}
	int size () {
		int cnt = 0;
		L(i, 0, 63) if(f[i]) cnt += 1;
		return cnt;
	}
	int mxp () {
		R(i, 63, 0) if(f[i]) return i;
		return -1;
	}
	ull mxv() {
		ull ret = 0;
		R(i, 63, 0) if((ret ^ f[i]) > ret) ret ^= f[i];
		return ret;
	} 
} pre[100], now, F[N];
lb operator | (lb a, lb b) {
	R(i, 63, 0) if(a[i]) b.insert(a[i]);
	return b;
}
ull X[66];
lb R[66];
ull iF[64], ID[64];
lb operator & (const lb &a, const lb &b) {
	lb qwq;
	int top = 0;
	me(iF, 0), me(ID, 0);
	L(i, 0, 63) iF[i] = a.f[i]; 
	R(t, 63, 0) if(b.f[t]) {
		ull w = b.f[t];
		ull ids = 1ull << top;
		R(i, 63, 0) if(w >> i & 1) {
			if(!iF[i]) {
				iF[i] = w, ID[i] = ids;
			}
			w ^= iF[i];
			ids ^= ID[i];
		}
		if(ids) {
			w = b.f[t];
			L(i, 0, top - 1) 
				if(ids >> i & 1) 
					w ^= X[i];
			qwq.insert(w);
		} else {
			X[top] = b.f[t], ++top;
		}
	}
	return qwq;
}
lb ans[N];
int dep[N];
vi e[N];
ull ANS[N];
vi fn[N];
void dfs(int x, int f) {
	fn[dep[x]].emplace_back(x);
	for(auto v : e[x]) if(v != f) {
		dep[v] = dep[x] + 1, ans[v] = ans[x] & F[v], dfs(v, x);
	}
}
struct Depu {
	vector < pair < int, lb > > Fun;
	void reduce() {
		int p = 0;
		L(i, 0, sz(Fun) - 1) {
			if(!i || Fun[i].second.size() != Fun[i - 1].second.size()) {
				swap(Fun[p], Fun[i]);
				++p;
			}
		}
		if(p != sz(Fun)) {
			Fun.resize(p); 
		}
	}
	friend Depu operator & (Depu u, Depu v) {
		int x = 0, y = 0;
		Depu ans;
		while(x < sz(u.Fun) && y < sz(v.Fun)) {
			if(u.Fun[x].first <= v.Fun[y].first) {
				ans.Fun.emplace_back(u.Fun[x].first, 
					y > 0 ? u.Fun[x].second & v.Fun[y - 1].second : 
						u.Fun[x].second);
				++x;
			} else {
				ans.Fun.emplace_back(v.Fun[y].first, 
					x > 0 ? u.Fun[x - 1].second & v.Fun[y].second : 
						v.Fun[y].second);
				++y;
			}
		}
		ans.reduce();
		return ans;
	}
	Depu shift(int k) {
		Depu qwq = (*this);
		for(auto&u : qwq.Fun)
			u.first += k;
		return qwq;
	}
};
Depu dp[N];

int n, fa[N];
void dfs1(int x, int fa) {
	for(auto &v : e[x]) if(v != fa) {
		dfs1(v, x), dp[x] = dp[x] & dp[v].shift(1);
	} 
}
void dfs2(int x, int fa) {
	for(auto &v : e[x]) if(v != fa) {
		dp[v] = dp[v] & dp[x].shift(1), dfs2(v, x);
	} 
}
mt19937_64 orz;
int main() {
//	freopen("tree.in", "r", stdin);
//	freopen("tree.out", "w", stdout);
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	n = 100;
	cin >> n;
	L(i, 2, n) {
		fa[i] = i - 1;
		cin >> fa[i];
		e[fa[i]].emplace_back(i);
		e[i].emplace_back(fa[i]);
	}
	L(i, 1, n) {
		int cnt;
		cnt=63;
		cin >> cnt;
		while(cnt--) {
			ull w=orz();
			cin >> w;
			F[i].insert(w);
		} 
		dp[i].Fun.emplace_back(0, F[i]);
		dp[i].Fun.emplace_back(n, lb());
	}
	dfs1(1, 0); 
	dfs2(1, 0);
	ull sim = 0;
	L(i, 1, n) {
		ull ans = 0;
		L(j, 0, sz(dp[i].Fun) - 2) 
			ans += dp[i].Fun[j].second.mxv() * (dp[i].Fun[j + 1].first - dp[i].Fun[j].first);
//		sim += ans;
		cout << ans << '\n';
	}
//	cout << sim << endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 9ms
memory: 57672kb

input:

2
1
2 2 3
2 1 1

output:

4
2

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 57904kb

input:

5
1 2 2 3
3 83 75 58
4 125 124 58 16
4 39 125 71 112
3 69 66 5
4 48 73 69 6

output:

171
125
183
142
243

result:

ok 5 lines

Test #3:

score: 0
Accepted
time: 1ms
memory: 57688kb

input:

2
1
0
0

output:

0
0

result:

ok 2 lines

Test #4:

score: 0
Accepted
time: 102ms
memory: 69408kb

input:

500
1 2 3 2 1 2 6 2 4 6 6 10 7 12 7 9 8 10 12 20 12 19 15 24 25 23 25 22 29 29 28 26 31 25 34 31 35 33 39 37 36 42 37 37 41 43 42 46 45 45 49 52 53 50 46 50 49 52 58 57 57 61 57 59 56 65 63 59 66 65 63 70 70 68 72 71 73 72 72 76 72 75 80 76 76 82 83 80 89 89 91 85 85 90 89 89 89 92 93 91 92 93 98 96...

output:

18434153946472599289
17931933346714042066
17916198204903720383
17916198204176061148
17931933346710961779
18445169471807930489
17931926407666058065
18445169471807930348
17931933346714042064
17916198204176061019
18445169471807930488
18446738828973977865
17916198204176061018
17931926407666058064
184467...

result:

ok 500 lines

Test #5:

score: 0
Accepted
time: 1836ms
memory: 191116kb

input:

49999
1 1 3 1 1 5 2 4 1 8 7 6 3 13 4 12 12 1 19 8 2 16 23 6 21 3 11 1 21 7 14 6 3 28 31 24 6 22 27 11 17 25 41 5 17 13 1 48 17 14 31 18 43 30 53 27 7 39 4 2 11 55 48 17 32 15 24 44 53 63 70 31 21 17 74 37 34 48 15 33 14 53 8 9 72 10 65 77 69 36 32 61 51 63 77 25 71 47 59 94 39 41 77 24 5 33 43 18 72...

output:

18446744063446965319
18316893942693974299
18446744073709548919
18355577725686532847
18446744073709551614
18446744073709551615
18446744073709551614
18446744073709551615
18446736549671322125
12348860911474380074
18446744072601433415
18446744073709551615
17335313836902106838
18446744073709551576
184467...

result:

ok 49999 lines

Test #6:

score: 0
Accepted
time: 2370ms
memory: 225064kb

input:

50000
1 1 1 2 2 2 3 4 4 5 5 5 6 6 8 8 8 8 8 8 9 9 10 10 11 11 12 12 13 13 13 14 14 14 15 15 15 16 18 18 19 19 20 20 20 20 21 23 24 24 24 24 26 26 27 27 28 29 29 29 30 30 30 31 31 32 32 32 32 33 33 33 34 34 35 35 36 36 36 36 37 38 38 38 38 39 39 39 40 41 42 43 44 44 45 45 45 46 46 47 47 47 47 47 48 4...

output:

17388026687988753207
18446123107769912009
18433598785516292263
18446483694069646475
18446744073700722557
18446743950305151556
18446123107769912008
18446170606667738311
18446744071353497819
18446744065870877991
18446744073709531050
18446744073709231216
18446546425974411728
18446744073709533965
184467...

result:

ok 50000 lines

Test #7:

score: -100
Memory Limit Exceeded

input:

50000
1 1 3 4 5 6 5 7 3 10 6 12 12 12 5 8 17 4 19 20 17 22 22 22 25 25 27 27 28 22 31 31 31 34 34 35 37 38 38 40 41 42 43 42 44 46 40 42 47 50 50 40 53 41 42 56 57 58 59 59 61 62 59 64 65 65 59 61 69 62 71 72 73 72 72 74 58 62 79 80 79 82 74 84 84 84 46 72 89 90 90 34 93 94 94 96 94 95 95 100 101 10...

output:


result: