QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#128995#5445. VulpeculazhoukangyangTL 980ms69540kbC++113.5kb2023-07-21 18:36:022023-07-21 18:36:04

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 18:36:04]
  • 评测
  • 测评结果:TL
  • 用时:980ms
  • 内存:69540kb
  • [2023-07-21 18:36:02]
  • 提交

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];
lb operator & (lb a, lb b) {
	int ma = a.mxp(), mb = b.mxp();
	if(ma > mb) swap(a, b), swap(ma, mb);
	if(ma == -1) return a;
	if(ma != mb) return b[mb] = 0, a & b;
	ull xay = a[ma] ^ b[mb], sw = a[ma];
	a[ma] = b[mb] = 0;
	auto ns = a & b;
	int pn = 0;
	R(i, 63, 0) if(a[i]) X[++pn] = a[i]; 
	R[pn + 1] = b;
	R(i, pn, 1) 
		R[i] = R[i + 1], R[i].insert(X[i]);
	if(!R[1].check(xay)) return ns;
	L(i, 1, pn) if(!R[i + 1].check(xay)) xay ^= X[i], sw ^= X[i];
	ns[ma] = sw;
	return ns;
}
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);
	} 
}
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	L(i, 2, n) {
		cin >> fa[i];
		e[fa[i]].emplace_back(i);
		e[i].emplace_back(fa[i]);
	}
	L(i, 1, n) {
		int cnt;
		cin >> cnt;
		while(cnt--) {
			ull w;
			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);
	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);
		cout << ans << '\n';
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 11ms
memory: 57728kb

input:

2
1
2 2 3
2 1 1

output:

4
2

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 10ms
memory: 57744kb

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: 5ms
memory: 57796kb

input:

2
1
0
0

output:

0
0

result:

ok 2 lines

Test #4:

score: 0
Accepted
time: 980ms
memory: 69540kb

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: -100
Time Limit Exceeded

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:


result: