QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#360278#8213. GraffitiinstallbRE 1ms3740kbC++233.6kb2024-03-21 16:42:532024-03-21 16:42:54

Judging History

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

  • [2024-03-21 16:42:54]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3740kb
  • [2024-03-21 16:42:53]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define M 300005
int n,m,ty;
char S[5];
vector<int>edge[M];
using ll = long long;
ll f[M][3][3];
using pll = pair<ll,ll>;
vector<pll>A;
ll solve1(){//C(#a,2) + sum
    vector<ll>p;
    ll ret = 0, s = 0;
    for(auto [x,y]: A) 
        s += y, p.push_back(x-y);
    sort(p.begin(),p.end());
    reverse(p.begin(),p.end());
    ret = s;
    for(int i=0;i<p.size();i++){
        s += p[i];
        ret = max(ret,(1ll*i*(i+1)>>1)+s);
    }
    return ret;
}
using tll = tuple<ll,ll,ll>;
vector<tll>B;
const ll inf = 1e16;
ll solve2(){
    if(B.empty()) return 0ll;
    vector<ll>p;
    ll ret = 0, sumz = 0,v = -inf;
    for(auto [x,y,z]: B){
        sumz += z;
        if(v == -inf) v = x - z;
        else assert(v == x - z);
        p.push_back(y - z);
    }
    sort(p.begin(),p.end());
    reverse(p.begin(),p.end());
    static ll pre[M];
    pre[0]=0;
    for(int i=0;i<p.size();i++)pre[i+1] += pre[i] + p[i];
    ret = sumz;
    for(int i=1;i<p.size();i++){
        int l = (int)p.size() - i;
        ret = max(ret,1ll*(l>>1)*(l+1>>1) + sumz + max(pre[l>>1] + (l+1>>1)*v,pre[l+1>>1] + (l>>1)*v));
    }
    return ret;
}
void dfs(int F,int now){
    for(int &to:edge[now])if(to!=F){
        dfs(now,to);
    }
    if(ty == 2){
        for(int a=0;a<2;a++)
            for(int b=0;b<2;b++){
                if(a == 0){
                    A.clear();
                    for(int &to:edge[now])if(to!=F)
                        A.push_back(pll(f[to][0][a]+(a==0&&b==1),f[to][1][a]+(a==0&&b==0)));
                    f[now][a][b] = solve1();
                }else {
                    for(int &to:edge[now])if(to!=F)
                        f[now][a][b] += max(f[to][0][a],f[to][1][a]);
                }
            }
    }else{
        for(int a=0;a<3;a++)
            for(int b=0;b<3;b++){
                if(a == 1){
                    B.clear();
                    for(int &to:edge[now])if(to!=F)
                        B.push_back(tll(f[to][0][a]+(b==2),f[to][1][a],f[to][2][a]+(b==0)));
                    f[now][a][b] = solve2();
                }else {
                    for(int &to:edge[now])if(to!=F)
                        f[now][a][b] += max(f[to][0][a],f[to][1][a]);
                }
            }
    }
}
ll redfs(int F,int now,int flg){
    ll ret = 0,sz=edge[now].size();
    // if(flg)cout<<now<<' '<<sz<<endl;
    if(flg) ret += sz*(sz-1);
    for(int &to:edge[now])if(to!=F)
        ret += redfs(now,to,!flg);
    return ret;
}
int main(){
    cin>>n;
    scanf("%s",S+1);
    m=strlen(S+1);
    if(m==1)cout<<n<<endl;
    else if(m==2)cout<<n-1<<endl;
    if(m<=2)return 0;
    for(int a,b,i=1;i<n;i++){
        scanf("%d%d",&a,&b);
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    if(S[1] == S[3]){
        cout<<max(redfs(0,1,0),redfs(0,1,1))<<endl;
        return 0;
    }
    if(S[1]!=S[2] && S[2]!=S[3] && S[1]!=S[3])S[1]='a',S[2]='b',S[3]='c',ty=1;
    else S[1]='a',S[2]='a',S[3]='b',ty=2;
    dfs(0,1);
    if(ty == 1){
        cout<<max(f[1][0][1],max(f[1][1][1],f[1][2][1]))<<endl;
    }else{
        ll ans = 0;
        int a = 0;
        {
            A.clear();
            for(int &to:edge[1])
                A.push_back(pll(f[to][0][a],f[to][1][a]));
            ans = solve1();
        }
        a = 1;
        {
            ll s = 0;
            for(int &to:edge[1])
                s += max(f[to][0][a],f[to][1][a]);
            ans = max(ans,s);
        }
        cout<<ans<<endl;
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3596kb

input:

1
a

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

3
orz
1 2
2 3

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

2
ab
1 2

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

input:

5
bob
3 2
5 1
1 4
2 4

output:

4

result:

ok 1 number(s): "4"

Test #5:

score: -100
Runtime Error

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:


result: