QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#749124	#5659. Watching Cowflix	_8_8_	20.833333	287ms	6200kb	C++23	1.0kb	2024-11-14 22:46:10	2024-11-14 22:46:10

Judging History

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

[2024-11-14 22:46:10]
评测

测评结果：20.833333
用时：287ms
内存：6200kb

查看

[2024-11-14 22:46:10]
提交

answer

#include <bits/stdc++.h>    

using namespace std;

typedef long long ll;

const int N = (int)2e5 + 12, MOD = (int)1e9 + 7;

int n, dp[N][2];
bool ok[N];
vector<int> g[N];

void dfs(int v, int pr, int k) {
    dp[v][1] = 1 + k;
    dp[v][0] = 0;
    for(int to:g[v]) {
        if(to == pr) continue;
        dfs(to, v, k);
        dp[v][0] += min(dp[to][0], dp[to][1]);
        dp[v][1] += min(dp[to][0], dp[to][1] - k);
    }
    if(ok[v]) {
        dp[v][0] = (int)1e9;
    }
}
void test() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        char x;cin >> x;
        if(x == '1') {
            ok[i] = 1; 
        }
    }

    for(int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for(int i = 1; i <= n; i++) {
        dfs(1, 1, i);
        cout << min(dp[1][0], dp[1][1]) << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    // cin >> t;
    
    while(t--)
        test();
}

源文件, 语言: C++23

详细

Pretests

Final Tests

Test #1:

score: 4.16667

Accepted

time: 1ms

memory: 3648kb

input:

output:

result:

ok 5 number(s): "4 6 8 9 10"

Test #2:

score: 4.16667

Accepted

time: 2ms

memory: 5688kb

input:

output:

result:

ok 7 numbers

Test #3:

score: 4.16667

Accepted

time: 264ms

memory: 6200kb

input:

5000
0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000010000000...

output:

result:

ok 5000 numbers

Test #4:

score: 4.16667

Accepted

time: 287ms

memory: 6132kb

input:

5000
0100000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

ok 5000 numbers

Test #5:

score: 4.16667

Accepted

time: 275ms

memory: 6036kb

input:

5000
0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000001000000000000000001000000000000000000000000000000000000000000000000...

output:

result:

ok 5000 numbers

Test #6:

score: 0

Time Limit Exceeded

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

Test #7:

score: 0

Time Limit Exceeded

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

Test #8:

score: 0

Time Limit Exceeded

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

Test #9:

score: 0

Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

Test #10:

score: 0

Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

Test #11:

score: 0

Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

Test #12:

score: 0

Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

Test #13:

score: 0

Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

Test #14:

score: 0

Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

Test #15:

score: 0

Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

Test #16:

score: 0

Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

Test #17:

score: 0

Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

Test #18:

score: 0

Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

Test #19:

score: 0

Time Limit Exceeded

input:

100000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

Test #20:

score: 0

Time Limit Exceeded

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

Test #21:

score: 0

Time Limit Exceeded

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

Test #22:

score: 0

Time Limit Exceeded

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

Test #23:

score: 0

Time Limit Exceeded

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

Test #24:

score: 0

Time Limit Exceeded

input:

200000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...