QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #320439 | #8213. Graffiti | ucup-team052# | WA | 189ms | 58272kb | C++23 | 4.6kb | 2024-02-03 16:51:18 | 2024-02-03 16:51:19 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define mod 998244353
#define ll long long
#define int long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
if(nega==-1) return -ans;
return ans;
}
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
#define N 300005
char _str[5];
int str[3],m;
vector<int> G[N];
int n;
ll f[N][3][3],g[N][3],w12[N],w[N];
int a[N],b[N],dpos[N],reva[N];
vector<int> d[N];
ll solve(int n)
{
// for(int i=0;i<n;i++) printf("%d%c",g[i][0]," \n"[i==n-1]);
// for(int i=0;i<n;i++) printf("%d%c",g[i][1]," \n"[i==n-1]);
// for(int i=0;i<n;i++) printf("%d%c",g[i][2]," \n"[i==n-1]);
for(int i=0;i<=n;i++) w12[i]=0;
for(int i=0;i<n;i++)
{
int dpos=g[i][1]-g[i][2];
dpos=min(dpos,n+1);
dpos=max(dpos,0LL);
w[i]=g[i][0]-max(g[i][1],g[i][2]);
w12[dpos+1]++;
::dpos[i]=dpos;
d[dpos].push_back(i);
}
for(int i=1;i<=n;i++) w12[i]+=w12[i-1];
for(int i=0;i<n;i++) w12[0]+=max(g[i][1],g[i][2]);
for(int i=1;i<=n;i++) w12[i]+=w12[i-1];
for(int i=1;i<=n;i++) a[i]=b[i]=i-1;
sort(a+1,a+n+1,[&](int x,int y){
return w[x]>w[y];
});
for(int i=1;i<=n;i++) reva[a[i]]=i;
sort(b+1,b+n+1,[&](int x,int y){
return w[x]+dpos[x]>w[y]+dpos[y];
});
ll ans=w12[0]; int posa=0,posb=0,inb=0;
auto gval=[&](int i,int u)
{
if(i<=dpos[u]) return w[u];
else return w[u]-(i-dpos[u]);
};
// for(int i=0;i<=n;i++) printf("%d%c",w12[i]," \n"[i==n]);
// for(int i=0;i<n;i++) printf("%d %d\n",w[i],dpos[i]);
ll suma=0;
for(int i=1;i<=n;i++)
{
// while(posb>=1&&dpos[b[posb]]>i) posb--;
while(posb>=1&&posa<n&&gval(i,b[posb])<gval(i,a[posa+1]))
{
if(dpos[b[posb]]>=i) assert(0);
else if(dpos[a[posa+1]]<i) posa++;
else
{
posb--,inb--,posa++;
suma++;
}
}
suma-=inb;
while(posb<n&&dpos[b[posb+1]]>=i) posb++;
while(posa<n&&dpos[a[posa+1]]<i) posa++;
if(posb<n&&(posa==n||gval(i,b[posb+1])>gval(i,a[posa+1])))
{
// printf("b : %d\n",b[posb+1]);
inb++; posb++;
suma+=gval(i,b[posb]);
}
else
{
// printf("a : %d * %d\n",a[posa+1],gval(i,a[posa+1]));
posa++;
suma+=gval(i,a[posa]);
}
// printf("* %d : %d\n",i,suma);
ans=max(ans,w12[i]+suma);
for(int j:d[i]) if(reva[j]<=posa) inb++;
}
for(int i=0;i<=n+1;i++) d[i].clear();
return ans;
}
void dfs(int u,int fa)
{
for(int v:G[u]) if(v!=fa) dfs(v,u);
for(int c=0;c<m;c++) for(int d=0;d<m;d++)
{
if(u==1) d=m;
if(str[1]==c)
{
vector<ll> tw[m];
for(int v:G[u]) if(v!=fa) for(int j=0;j<m;j++) tw[j].push_back(f[v][j][c]);
for(int j=0;j<m;j++)
{
if(str[0]==j&&str[2]==d) for(int i=0;i<(int)tw[j].size();i++) tw[j][i]++;
if(str[0]==d&&str[2]==j) for(int i=0;i<(int)tw[j].size();i++) tw[j][i]++;
}
ll ans=0;
if(str[0]==str[2])
{
if(m==1)
{
ans=1LL*(int)tw[0].size()*((int)tw[0].size()-1);
for(int i=0;i<(int)tw[0].size();i++) ans+=tw[0][i];
}
else
{
priority_queue<ll> q;
ll cur=0;
for(int i=0;i<(int)tw[0].size();i++) q.push(tw[0][i]-tw[1][i]),cur+=tw[1][i];
ans=cur;
for(int i=1;i<=(int)tw[0].size();i++)
{
cur+=q.top(); q.pop();
ans=max(ans,cur+1LL*i*(i-1));
}
}
}
else
{
for(int j=0;j<3;j++)
{
for(int i=0;i<(int)tw[0].size();i++) g[i][j]=tw[str[j]][i];
}
ans=solve(tw[0].size());
}
f[u][c][min(d,m-1)]=ans;
}
else
{
ll w=0;
for(int v:G[u]) if(v!=fa)
{
ll mx=0;
for(int j=0;j<m;j++) mx=max(mx,f[v][j][c]);
w+=mx;
}
f[u][c][min(d,m-1)]=w;
}
}
// printf("%d :\n",u);
// for(int i=0;i<m;i++) for(int j=0;j<m;j++) printf("%d%c",f[u][i][j]," \n"[j==m-1]);
}
signed main()
{
cin>>n; scanf("%s",_str);
for(int i=1;i<n;i++)
{
int u=read(),v=read();
G[u].pb(v),G[v].pb(u);
}
if(strlen(_str)==1) cout<<n<<endl,exit(0);
if(strlen(_str)==2)
{
ll ans=0;
for(int i=1;i<=n;i++) ans+=G[i].size();
if(_str[0]==_str[1]) cout<<ans<<endl;
else cout<<ans/2<<endl;
return 0;
}
for(int i=0;i<3;i++)
{
int ok=0;
for(int j=0;j<i;j++) if(_str[i]==_str[j]) str[i]=str[j],ok=1;
if(!ok) str[i]=m++;
}
dfs(1,0);
ll ans=0;
for(int c=0;c<m;c++) ans=max(ans,f[1][c][m-1]);
cout<<ans<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 6028kb
input:
1 a
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 22132kb
input:
3 orz 1 2 2 3
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 2ms
memory: 5988kb
input:
2 ab 1 2
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 2ms
memory: 7752kb
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: 22052kb
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: 4ms
memory: 22412kb
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: 2ms
memory: 22128kb
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: 22084kb
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: 0ms
memory: 22380kb
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: 22376kb
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: 0
Accepted
time: 0ms
memory: 22048kb
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:
54
result:
ok 1 number(s): "54"
Test #12:
score: 0
Accepted
time: 0ms
memory: 22088kb
input:
51 abb 4 33 29 28 44 34 31 46 46 17 27 48 25 35 45 19 36 40 35 51 22 36 43 9 26 47 21 36 12 17 51 50 13 44 3 34 19 36 15 32 47 28 1 3 2 40 33 46 5 30 48 39 41 15 8 20 14 46 34 27 40 17 24 2 38 10 9 17 30 19 32 17 16 21 23 9 42 34 6 15 10 31 11 28 18 34 49 40 37 34 50 19 28 17 39 40 20 19 7 24
output:
57
result:
ok 1 number(s): "57"
Test #13:
score: 0
Accepted
time: 0ms
memory: 22116kb
input:
51 abb 27 37 40 37 33 22 3 29 9 28 14 28 38 17 49 47 36 29 46 10 6 11 11 47 37 18 20 22 39 28 29 28 1 7 32 42 24 30 2 45 16 7 45 29 42 39 43 42 5 37 22 49 34 31 4 29 30 22 41 29 18 22 50 22 25 28 7 42 26 30 51 14 19 13 8 49 35 22 48 14 12 42 21 35 23 50 44 42 31 22 13 39 17 37 10 31 15 37 28 49
output:
70
result:
ok 1 number(s): "70"
Test #14:
score: 0
Accepted
time: 0ms
memory: 22152kb
input:
51 abb 7 43 11 39 8 5 47 44 25 49 9 30 40 3 36 17 13 41 16 50 44 10 12 7 33 44 5 2 35 7 22 45 19 43 18 32 42 19 31 10 45 29 3 19 46 48 39 2 34 25 14 43 2 19 21 7 32 16 51 27 6 24 43 41 27 32 48 15 23 43 17 16 50 43 24 28 1 13 38 19 37 19 49 2 26 10 28 43 30 19 4 22 20 42 15 19 29 44 10 19
output:
63
result:
ok 1 number(s): "63"
Test #15:
score: 0
Accepted
time: 0ms
memory: 8088kb
input:
51 aba 44 6 9 7 1 50 24 38 26 11 30 2 6 21 34 43 49 11 13 4 42 21 5 38 22 3 18 3 45 34 28 26 38 43 27 21 37 27 16 42 2 23 43 21 32 21 29 28 19 13 51 13 15 40 20 1 36 46 10 3 12 11 25 21 47 6 33 7 39 22 4 38 8 27 35 38 48 50 41 31 50 21 31 26 23 26 17 24 40 21 46 44 7 32 3 8 11 43 14 11
output:
132
result:
ok 1 number(s): "132"
Test #16:
score: 0
Accepted
time: 2ms
memory: 7848kb
input:
52 aba 19 7 11 48 4 6 5 27 46 50 6 37 50 23 12 40 37 23 13 23 32 38 22 44 52 5 34 50 26 38 35 10 51 20 7 26 41 6 15 26 39 10 10 40 3 50 33 29 30 14 45 50 14 27 21 27 42 29 49 44 31 27 18 5 36 42 16 11 29 28 24 12 8 50 38 5 43 10 48 52 1 52 47 26 40 32 2 3 44 27 28 38 20 26 23 5 17 27 9 43 25 46
output:
116
result:
ok 1 number(s): "116"
Test #17:
score: 0
Accepted
time: 0ms
memory: 7792kb
input:
52 aba 10 43 2 40 24 9 47 35 42 44 1 18 7 18 3 40 28 4 52 25 6 13 33 18 35 19 49 2 16 39 26 3 32 8 4 44 50 22 11 30 41 6 19 39 18 39 14 36 34 44 36 4 17 34 45 21 12 17 25 36 51 39 29 8 30 23 9 8 46 11 37 2 23 13 20 13 44 51 15 37 43 27 40 51 31 3 5 10 22 18 8 44 21 23 27 30 38 28 13 39 48 25
output:
88
result:
ok 1 number(s): "88"
Test #18:
score: 0
Accepted
time: 2ms
memory: 7752kb
input:
52 aba 48 38 40 22 49 23 37 3 6 12 43 42 26 22 30 39 8 7 25 7 47 41 44 11 52 1 13 1 41 14 19 41 23 39 35 13 32 19 38 13 39 41 2 27 51 21 31 19 21 9 29 36 9 39 16 27 15 22 24 42 18 30 42 9 36 30 4 7 27 9 17 5 22 9 50 30 20 16 46 52 28 21 5 16 3 1 33 22 7 28 10 21 12 34 34 39 11 39 1 11 45 11
output:
112
result:
ok 1 number(s): "112"
Test #19:
score: 0
Accepted
time: 2ms
memory: 7800kb
input:
52 aba 46 45 42 45 18 27 3 44 16 25 39 24 40 10 33 32 19 31 13 1 27 45 25 9 23 2 29 14 24 8 21 52 14 37 17 24 15 9 41 24 43 31 38 7 4 52 45 7 50 1 6 40 49 22 37 52 11 23 48 7 5 2 10 1 2 48 8 7 36 22 26 28 44 23 34 13 9 7 31 26 12 8 52 48 47 3 30 40 20 25 7 22 1 26 28 52 51 26 32 45 35 30
output:
106
result:
ok 1 number(s): "106"
Test #20:
score: 0
Accepted
time: 0ms
memory: 7780kb
input:
52 aba 36 34 23 29 28 11 2 47 33 26 16 37 27 46 52 3 8 14 44 15 51 47 37 7 34 29 50 27 12 47 6 18 20 21 17 14 18 13 10 3 49 17 13 3 42 22 30 13 46 43 5 19 9 18 11 14 38 51 21 46 40 50 39 19 48 22 43 19 24 19 19 14 22 41 45 37 15 41 26 11 31 46 4 43 35 15 3 19 41 43 32 11 29 47 1 7 47 43 7 14 25 28
output:
104
result:
ok 1 number(s): "104"
Test #21:
score: 0
Accepted
time: 60ms
memory: 22584kb
input:
300000 z 180011 260532 271217 191245 41791 255746 290587 278534 218547 277068 139010 241751 243632 263417 248223 222193 89717 215179 251082 231639 117314 8572 245286 297248 168750 266280 80957 255206 73540 12700 170796 282744 214088 139101 299056 232065 3541 39425 245901 203384 4354 21447 106700 295...
output:
300000
result:
ok 1 number(s): "300000"
Test #22:
score: 0
Accepted
time: 65ms
memory: 22288kb
input:
300000 aa 145612 276393 88541 108216 226040 100484 260244 139556 150893 213849 85295 33531 270499 248769 5250 51884 24539 76804 254304 165858 85779 118908 183955 155461 5230 80950 80213 95224 58182 122060 46066 288552 138127 46553 186220 182641 21451 14106 193341 35522 269820 212259 208311 40745 229...
output:
599998
result:
ok 1 number(s): "599998"
Test #23:
score: 0
Accepted
time: 17ms
memory: 12032kb
input:
123234 ab 5333 65911 93667 3824 117784 113995 122335 34180 100563 13017 2356 55265 68248 30680 67326 55966 55450 2923 86794 12061 49667 54440 46800 106814 4840 7419 53069 122499 34188 99215 18873 90062 115319 82268 1093 52619 108703 107429 40381 14308 91251 53870 7680 94995 90630 57256 78084 11866 3...
output:
123233
result:
ok 1 number(s): "123233"
Test #24:
score: 0
Accepted
time: 124ms
memory: 43616kb
input:
300000 aaa 286864 6103 13963 130993 193857 266146 21588 192178 60950 206316 57174 172746 83177 159553 274512 266893 1479 82701 149984 220249 66444 38360 164961 269188 90561 160425 48372 223724 176008 89731 146829 119384 4625 131173 271552 74420 258647 63612 101816 202418 73996 284875 167169 62661 18...
output:
1202694
result:
ok 1 number(s): "1202694"
Test #25:
score: 0
Accepted
time: 174ms
memory: 44448kb
input:
300000 wow 33050 101378 38107 258970 169311 109231 147923 297962 291294 116868 35054 53343 198452 192697 213787 257591 188731 256973 281711 199138 234546 68112 204998 251624 97110 216134 250244 200876 285877 202008 173953 211734 40140 26823 71958 217939 219546 251422 128294 208345 55792 155 162308 2...
output:
691046
result:
ok 1 number(s): "691046"
Test #26:
score: 0
Accepted
time: 167ms
memory: 44820kb
input:
300000 bob 3546 155583 136408 83861 111087 14272 247003 298086 108933 172420 164224 266023 111269 244728 113434 88159 133416 293100 147988 29901 261668 83495 56261 94204 102384 32287 226850 127102 206891 175776 943 283177 269178 25048 239910 24108 129685 205836 12217 98902 256855 9020 289624 267084 ...
output:
691252
result:
ok 1 number(s): "691252"
Test #27:
score: -100
Wrong Answer
time: 189ms
memory: 58272kb
input:
300000 oop 262845 173800 283177 94631 297757 21360 86111 283443 104846 44242 146147 80602 172254 3094 18207 36330 116034 170256 241960 205186 70178 78225 70995 118475 205702 210175 286804 82561 5920 218263 217010 270658 109005 165733 173532 245803 234143 242996 183220 280923 42808 252787 103082 6893...
output:
368273
result:
wrong answer 1st numbers differ - expected: '348991', found: '368273'