QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #334234 | #8213. Graffiti | Dualqwq | WA | 218ms | 33672kb | C++17 | 2.9kb | 2024-02-21 15:32:09 | 2024-02-21 15:32:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
typedef long long ll;
template<typename T> inline bool ckmax(T &x,const T &y) { return (x < y) && (x = y,true);}
int n;
vector<int> G[N];
char s[5];
namespace SolveA {
inline void Main() { printf("%d\n",n);exit(0);}
}
namespace SolveAB {
inline void Main() { printf("%d\n",n - 1);exit(0);}
}
namespace SolveAA {
inline void Main() { printf("%d\n",n + n - 2);exit(0);}
}
namespace SolveABC {
ll f[N][2],g[N]; // g 表示 u 点上方还有一个 1/3，当前是 2 的代价
void dfs0(int x,int fa) {
for(auto y : G[x]) if(y != fa) dfs0(y,x);
vector<ll> V;ll sum1 = 0;
for(auto y : G[x])
if(y != fa) f[x][0] += max({g[y],f[y][0]}),V.push_back(f[y][0] - f[y][1]),sum1 += f[y][1];
sort(V.begin(),V.end(),greater<ll>());
f[x][1] = g[x] = sum1;
for(int i = 0;i < V.size();i++) {
sum1 += V[i];
ll val = sum1 + 1ll * (i + 2 >> 1) * (i + 1 >> 1);
ckmax(f[x][1],val);ckmax(g[x],val + (i + 2 >> 1));
}
// printf("%d %d %d\n",f[x][0],f[x][1],g[x]);
}
void Main() { dfs0(1,0); printf("%lld\n",max(f[1][0],f[1][1]));exit(0);}
}
namespace SolveABA {
ll f[N][2],g[N];
void dfs0(int x,int fa) {
for(auto y : G[x]) if(y != fa) dfs0(y,x);
vector<ll> V;ll sum1 = 0;
for(auto y : G[x])
if(y != fa) f[x][0] += max({g[y],f[y][0]}),V.push_back(f[y][0] - f[y][1]),sum1 += f[y][1];
sort(V.begin(),V.end(),greater<ll>());
f[x][1] = g[x] = sum1;
for(int i = 0;i < V.size();i++) {
sum1 += V[i];
ll val = sum1 + 1ll * (i + 1) * i / 2;
ckmax(f[x][1],val);ckmax(g[x],val + (i + 1));
}
}
void Main() { dfs0(1,0); printf("%lld\n",2 * max(f[1][0],f[1][1]));exit(0);}
}
namespace SolveAAB {
ll f[N][2],g[N][2]; // g 表示 x = A，上面还有一个 A/B
void dfs0(int x,int fa) {
for(auto y : G[x]) if(y != fa) dfs0(y,x);
vector<ll> V;ll sum1 = 0;
for(auto y : G[x]) if(y != fa) f[x][0] += g[y][0],V.push_back(f[y][1] - g[y][0]),sum1 += g[y][0];
sort(V.begin(),V.end(),greater<ll>());
f[x][0] = g[x][0] = sum1;g[x][1] = sum1 + V.size();
for(int i = 0;i < V.size();i++) {
sum1 += V[i];
ll val = sum1 + 1ll * (i + 1) * ((int)V.size() - i - 1);
ckmax(f[x][0],val);ckmax(g[x][0],val + (i + 1));ckmax(g[x][1],val + ((int)V.size() - i - 1));
}
for(auto y : G[x]) if(y != fa) f[x][1] += max({f[y][1],g[y][1]});
}
void Main() { dfs0(1,0);printf("%lld\n",max(f[1][0],f[1][1]));exit(0);}
}
int main() {
cin >> n;cin >> (s + 1);
for(int i = 1,u,v;i < n;i++) cin >> u >> v,G[u].push_back(v),G[v].push_back(u);
int len = strlen(s + 1);
if(len == 1) SolveA::Main();
if(len == 2 && s[1] == s[2]) SolveAA::Main();
if(len == 2 && s[1] != s[2]) SolveAB::Main();
if(s[1] != s[3] && s[1] != s[2] && s[2] != s[3]) SolveABC::Main();
if(s[1] == s[2] || s[2] == s[3]) SolveAAB::Main();
if(s[1] == s[3]) SolveABA::Main();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 12012kb
input:
1 a
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 17164kb
input:
3 orz 1 2 2 3
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 3ms
memory: 11768kb
input:
2 ab 1 2
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 14964kb
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: 16436kb
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: 0ms
memory: 16680kb
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: 15664kb
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: 15152kb
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: 16868kb
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: 15620kb
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: 14220kb
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: 3ms
memory: 14952kb
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: 13708kb
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: 14584kb
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: 17116kb
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: 0ms
memory: 16844kb
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: 4ms
memory: 15348kb
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: 0ms
memory: 17148kb
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: 3ms
memory: 16072kb
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: 3ms
memory: 16660kb
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: 167ms
memory: 20544kb
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: 172ms
memory: 21092kb
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: 61ms
memory: 15380kb
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: -100
Wrong Answer
time: 218ms
memory: 33672kb
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:
350143
result:
wrong answer 1st numbers differ - expected: '1202694', found: '350143'