QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#779192#7684. Sweet SugarliliwaWA 122ms7812kbC++231.8kb2024-11-24 17:52:552024-11-24 17:52:56

Judging History

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

  • [2024-11-24 17:52:56]
  • 评测
  • 测评结果:WA
  • 用时:122ms
  • 内存:7812kb
  • [2024-11-24 17:52:55]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> PLL;

#define x first
#define y second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define lep(i,a,b) for(int i=(a);i>=(b);i--)
#define sci(x) cin >> (x)
#define pli(x) cout << (x) << " ";
#define pll(x) cout << (x) << '\n';
#define yes cout << "Yes" << '\n';
#define no cout << "No" << '\n';
#define ls u << 1
#define rs u << 1 | 1
//cout << "? " << << ' ';
//printf("case:%d %d\n", );

const int N = 1e6 + 10;
//const ll p = 1e9 + 7;
ll n, m, k, res;

ll a[N], b[N], f[N][2], ne[N];
char s1[N], s2[N], t[N];
vector<int> e[N];

void add(ll &o, ll &j, ll v)
{
    ll to = 0, tj = 0;
    if((v + o) & 1) tj = max(tj, v + o); else to = max(to, v + o);
    if((v + j) & 1) tj = max(tj, v + j); else to = max(to, v + j);
    
    o = max(o, to), j = max(j, tj);
}

void dfs(int u, int fa)
{
    if(a[u] == 1) f[u][1] = 1, f[u][0] = 0; else if(a[u] == 2) f[u][1] = 0, f[u][0] = 2;
    for(auto j : e[u]) if(j != fa)
    {
        dfs(j, u);
        ll u1 = f[u][0], u2 = f[u][1], u3 = f[u][0], u4 = f[u][1];
        add(u1, u2, f[j][0]), add(u3, u4, f[j][1]);
        f[u][0] = max(u1, u3), f[u][1] = max(u2, u4);
    }
    
    //cout << u << ' ' << f[u][0] << ' ' << f[u][1] << '\n';
    if(k % 2 == 1 && f[u][1] >= k) res++, f[u][0] = f[u][1] = 0;
    if(k % 2 == 0 && f[u][0] >= k) res++, f[u][0] = f[u][1] = 0;
}

void solve()
{
    cin >> n >> k;
    rep(i, 1, n) sci(a[i]), f[i][0] = f[i][1] = 0, e[i].clear();
    for(int i = 1, u, v; i <= n - 1; i++) {cin >> u >> v; e[u].push_back(v), e[v].push_back(u);}
    
    res = 0; dfs(1, -1); pll(res)
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T; T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 7740kb

input:

4
7 5
1 2 1 2 2 1 2
1 2
2 3
3 4
3 5
5 6
5 7
2 2
1 0
1 2
1 1
1
1 2
1

output:

2
0
1
0

result:

ok 4 number(s): "2 0 1 0"

Test #2:

score: 0
Accepted
time: 2ms
memory: 7812kb

input:

12
1 1
0
1 1
1
1 1
2
1 2
0
1 2
1
1 2
2
1 3
0
1 3
1
1 3
2
1 2000000
0
1 2000000
1
1 2000000
2

output:

0
1
0
0
0
1
0
0
0
0
0
0

result:

ok 12 numbers

Test #3:

score: -100
Wrong Answer
time: 122ms
memory: 7688kb

input:

200000
5 2
1 1 0 0 1
2 4
5 2
4 1
3 2
5 1
0 0 0 0 0
5 1
1 2
3 2
5 4
5 3
1 0 0 0 1
1 4
4 2
3 4
5 2
5 9
1 0 0 0 2
4 3
2 1
3 1
5 1
5 3
0 1 1 0 1
5 4
2 1
4 3
5 1
5 1
0 2 1 1 1
5 3
2 4
3 4
1 4
5 1
1 0 1 1 0
1 5
4 2
1 3
5 2
5 7
0 2 1 1 2
5 1
2 3
2 5
5 4
5 5
0 1 0 1 0
2 4
4 3
5 2
1 5
5 1
0 0 1 0 1
4 1
4 5
2...

output:

1
0
0
0
1
3
3
0
0
2
0
0
2
1
0
0
1
1
0
2
0
1
0
2
1
0
0
0
0
0
1
2
0
0
2
2
0
1
0
0
0
0
3
3
0
0
1
1
2
1
2
0
4
0
1
1
0
1
0
0
1
5
0
1
1
1
0
1
1
1
1
1
2
0
1
1
1
0
3
1
0
1
0
0
4
0
0
0
1
1
0
0
1
0
2
0
5
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
0
0
0
0
0
1
0
0
1
1
0
1
0
1
1
1
2
0
1
2
0
0
2
0
0
1
0
0
0
0
0
...

result:

wrong answer 73rd numbers differ - expected: '1', found: '2'