QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #471638 | #8213. Graffiti | PhantomThreshold | WA | 3ms | 12196kb | C++17 | 4.7kb | 2024-07-10 23:56:50 | 2024-07-10 23:56:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
const int maxn=300000;
int n;
string str;
int __TP=-1;
vector<int> g[maxn+50];
ll dp[maxn+50][2][2];
inline void upd(ll &A,ll B){if (A<=B) A=B;}
void dfs(int u,int fa){
int sz=0;
for (auto v:g[u]){
if (v==fa) continue;
sz++;
dfs(v,u);
}
if (sz==0){
for (int j=0;j<=1;j++){
for (int k=0;k<=1;k++){
dp[u][j][k]=0;
}
}
return;
}
if (__TP==0){
// abb
{
// ?aa && ?ab
ll base=0;
for (auto v:g[u]) if (v!=fa) base+=max(dp[v][0][0],dp[v][1][0]);
dp[u][0][0]=dp[u][0][1]=base;
}
{
//?ba
vector<ll> tmp;
ll base=0;
for (auto v:g[u]) if (v!=fa){
tmp.push_back((dp[v][0][1])-(dp[v][1][1]+1));
base+=(dp[v][1][1]+1);
}
sort(tmp.begin(),tmp.end(),greater<ll>());
dp[u][1][0]=base;
ll presum=0;
for (ll i=1;i<=sz;i++){
presum=presum+tmp[i-1];
upd(dp[u][1][0],base+presum+i*(sz-i));
}
}
{
//?bb
vector<ll> tmp;
ll base=0;
for (auto v:g[u]) if (v!=fa){
tmp.push_back((dp[v][0][1]+1)-(dp[v][1][1]));
base+=(dp[v][1][1]);
}
sort(tmp.begin(),tmp.end(),greater<ll>());
dp[u][1][1]=base;
ll presum=0;
for (ll i=1;i<=sz;i++){
presum=presum+tmp[i-1];
upd(dp[u][1][1],base+presum+i*(sz-i));
}
}
}
else if (__TP==1){
//aba
{
// ?aa && ?ab
ll base=0;
for (auto v:g[u]) if (v!=fa) base+=max(dp[v][0][0],dp[v][1][0]);
dp[u][0][0]=dp[u][0][1]=base;
}
{
//?ba
vector<ll> tmp;
ll base=0;
for (auto v:g[u]) if (v!=fa){
tmp.push_back((dp[v][0][1]+1)-(dp[v][1][1]));
base+=(dp[v][1][1]);
}
sort(tmp.begin(),tmp.end(),greater<ll>());
dp[u][1][0]=base;
ll presum=0;
for (ll i=1;i<=sz;i++){
presum=presum+tmp[i-1];
upd(dp[u][1][0],base+presum+i*(i-1)/2);
}
}
{
//?bb
vector<ll> tmp;
ll base=0;
for (auto v:g[u]) if (v!=fa){
tmp.push_back((dp[v][0][1])-(dp[v][1][1]));
base+=(dp[v][1][1]);
}
sort(tmp.begin(),tmp.end(),greater<ll>());
dp[u][1][1]=base;
ll presum=0;
for (ll i=1;i<=sz;i++){
presum=presum+tmp[i-1];
upd(dp[u][1][1],base+presum+i*(i-1)/2);
}
}
}
else{
//abc
{
// ?aa && ?ab
ll base=0;
for (auto v:g[u]) if (v!=fa) base+=max(dp[v][0][0],dp[v][1][0]);
dp[u][0][0]=dp[u][0][1]=base;
}
{
//?ba
vector<ll> tmp;
ll base=0;
for (auto v:g[u]) if (v!=fa){
tmp.push_back((dp[v][0][1])-(dp[v][1][1]));
base+=(dp[v][1][1]);
}
sort(tmp.begin(),tmp.end(),greater<ll>());
dp[u][1][0]=base;
ll presum=0;
for (ll i=1;i<=sz;i++){
presum=presum+tmp[i-1];
upd(dp[u][1][0],base+presum+((i+1)/2)*(i+1-(i+1)/2));
}
}
{
//?bb
vector<ll> tmp;
ll base=0;
for (auto v:g[u]) if (v!=fa){
tmp.push_back((dp[v][0][1])-(dp[v][1][1]));
base+=(dp[v][1][1]);
}
sort(tmp.begin(),tmp.end(),greater<ll>());
dp[u][1][1]=base;
ll presum=0;
for (ll i=1;i<=sz;i++){
presum=presum+tmp[i-1];
upd(dp[u][1][1],base+presum+(i/2)*(i-i/2));
}
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin >> n;
cin >> str;
for (int i=1;i<n;i++){
int x,y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
if (str.size()==1){
cout << n << "\n";
return 0;
}
if (str.size()==2){
if (str[0]!=str[1]) cout << n-1 << "\n";
else cout << 2*(n-1) << "\n";
return 0;
}
if (str[0]==str[1] && str[1]==str[2]){
long long sum=0;
for (int i=1;i<=n;i++){
long long sz=g[i].size();
sum=sum+sz*(sz-1)/2;
}
cout << 2*sum << "\n";
return 0;
}
if (str[0]==str[1]) __TP=0,str="abb";
else if (str[0]==str[2]) __TP=1,str="aba";
else __TP=2,str="abc";
for (int i=0;i<=n;i++){
for (int j=0;j<=1;j++){
for (int k=0;k<=1;k++){
dp[i][j][k]=-INF;
}
}
}
dfs(1,0);
ll ans=0;
if (__TP==0){
//abb
ans=max(ans,dp[1][0][0]);
ans=max(ans,dp[1][0][1]);
{
//?bb
int u=1;
int sz=g[1].size();
ll dp1=0;
vector<ll> tmp;
ll base=0;
for (auto v:g[u]) if (v!=0){
tmp.push_back((dp[v][0][1])-(dp[v][1][1]));
base+=(dp[v][1][1]);
}
sort(tmp.begin(),tmp.end(),greater<ll>());
dp1=base;
ll presum=0;
for (ll i=1;i<=sz;i++){
presum=presum+tmp[i-1];
upd(dp1,base+presum+i*(sz-i));
}
ans=max(ans,dp1);
}
}
else if (__TP==1){
//aba
ans=max(ans,2*dp[1][0][0]);
ans=max(ans,2*dp[1][0][1]);
ans=max(ans,2*dp[1][1][1]);
}
else{
//abc
ans=max(ans,dp[1][0][0]);
ans=max(ans,dp[1][0][1]);
ans=max(ans,dp[1][1][1]);
}
cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 11560kb
input:
1 a
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 12056kb
input:
3 orz 1 2 2 3
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 2ms
memory: 11204kb
input:
2 ab 1 2
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 2ms
memory: 11356kb
input:
5 bob 3 2 5 1 1 4 2 4
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 0ms
memory: 11116kb
input:
50 abc 23 14 24 25 1 3 47 46 2 26 22 41 34 19 7 14 50 24 29 38 17 25 4 26 35 37 21 14 11 4 13 27 8 25 5 10 20 27 44 27 15 39 19 9 30 12 38 27 39 27 41 40 14 48 32 7 16 37 3 13 42 5 48 27 49 25 6 5 26 9 31 17 36 7 43 29 9 5 45 9 18 9 40 42 27 5 25 42 46 10 37 42 12 48 28 26 33 5
output:
37
result:
ok 1 number(s): "37"
Test #6:
score: 0
Accepted
time: 2ms
memory: 12196kb
input:
50 abc 14 26 46 47 10 13 30 19 33 46 32 50 39 6 35 13 8 5 28 3 2 21 17 22 22 6 5 20 19 3 38 3 16 2 18 34 13 6 47 6 9 28 1 2 37 47 50 10 12 34 40 19 42 19 26 46 43 3 44 47 31 47 49 18 45 34 27 13 7 34 6 34 3 45 11 44 21 13 29 24 15 40 48 39 24 6 41 47 23 27 36 21 25 21 4 20 20 44
output:
37
result:
ok 1 number(s): "37"
Test #7:
score: 0
Accepted
time: 0ms
memory: 10808kb
input:
50 abc 11 3 14 46 37 47 18 33 12 46 40 41 23 17 49 48 27 26 13 5 26 41 43 16 25 47 46 9 39 13 38 4 36 18 28 40 50 26 10 38 9 50 15 6 24 16 19 16 48 26 6 50 31 16 29 16 7 26 35 14 17 46 21 5 22 38 2 15 4 17 30 34 16 41 45 17 47 50 44 16 33 26 32 34 1 25 3 46 20 16 5 32 42 14 8 48 41 34
output:
44
result:
ok 1 number(s): "44"
Test #8:
score: 0
Accepted
time: 0ms
memory: 12088kb
input:
50 abc 9 7 43 49 26 3 14 11 17 43 23 35 19 25 44 25 2 1 10 28 4 46 21 22 15 43 39 25 16 38 38 23 34 29 47 49 46 35 5 39 25 35 32 23 27 37 3 32 37 24 20 13 33 25 1 29 30 11 31 34 18 31 50 37 13 48 22 23 8 10 41 24 42 46 36 37 48 43 49 31 40 41 12 35 24 34 45 7 35 31 7 31 11 44 28 1 6 19
output:
34
result:
ok 1 number(s): "34"
Test #9:
score: 0
Accepted
time: 2ms
memory: 11552kb
input:
50 abc 31 6 36 20 32 42 47 14 24 21 27 39 14 22 26 47 44 45 30 28 15 18 1 14 42 38 20 35 17 25 4 18 25 47 40 3 28 7 48 33 2 41 10 33 22 38 41 38 9 40 35 41 16 45 49 32 19 28 21 32 34 29 46 25 13 14 23 15 3 38 18 12 45 35 29 20 43 18 6 3 8 12 12 41 50 12 7 42 5 36 33 36 39 16 11 16 37 41
output:
30
result:
ok 1 number(s): "30"
Test #10:
score: 0
Accepted
time: 0ms
memory: 11464kb
input:
50 abc 50 18 10 32 38 18 47 13 31 6 49 18 45 47 42 4 7 18 18 27 36 13 12 13 41 12 35 8 6 40 16 8 4 22 14 44 25 2 28 18 3 27 34 32 5 27 43 5 33 11 23 24 2 18 21 39 46 5 8 49 32 19 20 28 22 12 11 5 15 38 44 7 9 5 19 49 1 16 30 50 48 25 40 11 24 27 26 5 37 50 17 24 13 5 39 26 29 27
output:
38
result:
ok 1 number(s): "38"
Test #11:
score: -100
Wrong Answer
time: 0ms
memory: 11188kb
input:
51 abb 7 35 1 48 32 42 45 15 13 39 14 43 9 2 34 37 23 24 47 36 36 35 41 22 50 49 49 44 28 42 48 43 20 37 22 21 10 38 6 35 29 17 35 24 19 51 21 44 38 4 11 17 33 42 37 50 44 38 12 17 43 38 3 49 8 12 16 49 5 15 40 31 24 4 15 50 39 44 42 35 27 21 51 50 18 13 30 4 26 29 31 22 46 49 17 38 25 49 2 26
output:
35
result:
wrong answer 1st numbers differ - expected: '54', found: '35'