Wy Online Judge

WyOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#957	#208. 「CSP-S2019」括号树	lzx	100	871ms	64240kb	C++14	863b	2025-07-05 09:05:13	2025-07-05 11:17:25

answer

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define fi first
#define se second
using namespace std;
const int N=5e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,ans;
vector<int> G[N];
char ch[N];
unordered_map<int,int> mp;
int cur;
int res[N];
int fa[N];
void dfs(int u)
{
	cur+=(ch[u]==')'?1:-1);
	if(ch[u]=='(') mp[cur+1]++;
	int t=mp[cur-1];
	mp[cur-1]=0;
	res[u]=mp[cur];
	res[u]+=res[fa[u]];
	for(auto v:G[u])
	{
		dfs(v);
	}
	if(ch[u]=='(') mp[cur+1]--;
	mp[cur-1]=t;
	cur-=(ch[u]==')'?1:-1);
	ans^=u*res[u];
}
signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>ch[i];
	for(int i=2;i<=n;i++)
	{
		cin>>fa[i];
		G[fa[i]].push_back(i);
	}
	dfs(1);
	cout<<ans;
	return 0;
}

源文件, 语言: C++14

详细

小提示：点击横条可展开更详细的信息

Test #1:

score: 5

Accepted

time: 2ms

memory: 19284kb

input:

7
(()()((
1 2 3 4 5 6

output:

result:

ok "15"

Test #2:

score: 5

Accepted

time: 4ms

memory: 19268kb

input:

8
)())((()
1 2 3 4 5 6 7

output:

result:

ok "19"

Test #3:

score: 5

Accepted

time: 2ms

memory: 19220kb

input:

198
)))())(())())(()))(()))))()(()(()()))())(()()(()()())()()))(())(())())((()((()((()(((())((()()))...

output:

result:

ok "3273"

Test #4:

score: 5

Accepted

time: 2ms

memory: 19324kb

input:

200
))((())())())(())))()))())(((()()((((()((()(((((())())(()))())()))((((())((()()(())()()()())(()(...

output:

result:

ok "21364"

Test #5:

score: 5

Accepted

time: 5ms

memory: 19540kb

input:

1949
(())))((()))(()))()()((())()(()))())((()()))(())))((())))()()(())((())(())()(()((()((((()((())(...

output:

result:

ok "1098479"

Test #6:

score: 5

Accepted

time: 4ms

memory: 19512kb

input:

1926
())(((()()()))(()))())()))((((()(((())())())((((())()()))((())(())))))))(())))()))()(()()()))()...

output:

result:

ok "531389"

Test #7:

score: 5

Accepted

time: 3ms

memory: 19360kb

input:

2000
))())())()())))(()()(())))))(()((((()(()())())())))(()())))(()))()()())(())()((()()(()()))(())(...

output:

result:

ok "63861"

Test #8:

score: 5

Accepted

time: 4ms

memory: 19268kb

input:

1998
()))((()((()(()))))()((())()())())((((()))((((()()((((((())())))((()))()()))(())()((()))))()(()...

output:

result:

ok "1416"

Test #9:

score: 5

Accepted

time: 4ms

memory: 19224kb

input:

1999
)))(((()(()()()(()))())((()()()(()))(((()())()))))))))(()()))(((())((()))))())((()(())()(((()))...

output:

result:

ok "27926"

Test #10:

score: 5

Accepted

time: 3ms

memory: 19432kb

input:

2000
()((()()(((()(()()))()()(((()))((()))()()()(((()()(())((()(((())(()()))()))(((((())()(()()()())...

output:

result:

ok "10983"

Test #11:

score: 5

Accepted

time: 38ms

memory: 34620kb

input:

99997
()(((()()))()()(())(()))(((()(((())()((())((()))))))))()(((())((())())())())()()(()())()(((()(...

output:

3818846184119

result:

ok "3818846184119"

Test #12:

score: 5

Accepted

time: 31ms

memory: 34548kb

input:

99998
(((()((((()(()))()((()))))))))(()())()()()()()()((()))(()(())()((())((((()((()())()))()((())((...

output:

6201171476965

result:

ok "6201171476965"

Test #13:

score: 5

Accepted

time: 29ms

memory: 34624kb

input:

99999
()(())()(())()()()()(()())()()(())()(()()()()(()()()()(()())(())((((()((()()))((()))())))(()((...

output:

242124759663

result:

ok "242124759663"

Test #14:

score: 5

Accepted

time: 32ms

memory: 34588kb

input:

100000
()(()())()()((((())((())()(((()))))()())()(()((())()))()()))(((()(((()(())))))))((()()()))()(...

output:

5113850219609

result:

ok "5113850219609"

Test #15:

score: 5

Accepted

time: 30ms

memory: 30260kb

input:

99999
((()()()(((()())(()))()((())))))(((())())()()())(()()(()))()()()()(()((()()((((())))))))()()()...

output:

2085082970032

result:

ok "2085082970032"

Test #16:

score: 5

Accepted

time: 33ms

memory: 30600kb

input:

100000
()((())(()()())(()()))(()())(())()((()()((())(()((()()(()))))((())))))()((()((()((())())((()(...

output:

2112798541955

result:

ok "2112798541955"

Test #17:

score: 5

Accepted

time: 167ms

memory: 64096kb

input:

500000
(())()((()))(((())))()()()()(())()()(())()(())()(((())))(((())))(())()()()()(())((()()))(((()...

output:

487466589970316

result:

ok "487466589970316"

Test #18:

score: 5

Accepted

time: 161ms

memory: 63808kb

input:

500000
()()()()((((()))))((()))(())(()(()))()(())(())()()(()()(()))()(()())()((()(())))(())(())()(()...

output:

1047922056418682

result:

ok "1047922056418682"

Test #19:

score: 5

Accepted

time: 162ms

memory: 64116kb

input:

500000
()()(())(())()()()(((())((()(()()(()))(()))((()())))))(()(()((((()))()()((()(()(())(((()(((((...

output:

1616950739745800

result:

ok "1616950739745800"

Test #20:

score: 5

Accepted

time: 155ms

memory: 64240kb

input:

500000
()((()(())))()((()())((())()())(())())((())())()((()))(())((()()()))()(()())(()(()))()(()((((...

output:

1464802790801058

result:

ok "1464802790801058"