QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#129032#5445. VulpeculazhoukangyangWA 326ms45660kbC++113.5kb2023-07-21 19:45:452023-07-21 19:45:45

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:45:45]
  • 评测
  • 测评结果:WA
  • 用时:326ms
  • 内存:45660kb
  • [2023-07-21 19:45:45]
  • 提交

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;
lb operator | (lb a, lb b) {
	R(i, 63, 0) if(a[i]) b.insert(a[i]);
	return b;
}
ull X[66], xo[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);
	R(tp, 63, 0) L(o, 0, 1) {
		ull W = o == 0 ? a.f[tp] : b.f[tp];
		ull w = W;
		
		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 = W;
			L(i, 0, top - 1) 
				if((ids >> i & 1) && xo[i] == o) 
					w ^= X[i];
			qwq.insert(w);
		} else {
			X[top] = W, xo[top] = o, ++top;
		}
	}
	return qwq;
}
lb ans[N];
int dep[N];
vi e[N];
ull ANS[N];
vi fn[N];
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;
		lb F;
		while(cnt--) {
			ull w=orz();
			cin >> w;
			F.insert(w);
		} 
		dp[i].Fun.emplace_back(0, F);
		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;
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 32740kb

input:

2
1
2 2 3
2 1 1

output:

4
2

result:

ok 2 lines

Test #2:

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

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: 0ms
memory: 32748kb

input:

2
1
0
0

output:

0
0

result:

ok 2 lines

Test #4:

score: -100
Wrong Answer
time: 326ms
memory: 45660kb

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:

8779027715387561351
5216860202369640988
18394763710447274879
18385604738535651945
5207784842923561555
18446742668234539211
5216493656431066004
18446742668160117177
5216860202369580683
18385604738534448875
18446742668225074088
18446742015604218286
18276547845459911999
5244344978716907048
183573374989...

result:

wrong answer 1st lines differ - expected: '18434153946472599289', found: '8779027715387561351'