QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#751537#5659. Watching Cowflix_8_8_0 91ms24844kbC++234.9kb2024-11-15 19:17:302024-11-15 19:17:34

Judging History

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

  • [2024-11-15 19:17:34]
  • 评测
  • 测评结果：0
  • 用时：91ms
  • 内存：24844kb
查看
  • [2024-11-15 19:17:30]
  • 提交

answer

#include <bits/stdc++.h>    

using namespace std;

typedef long long ll;

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

int n, dp[N][2], up[N][20], tin[N], tout[N], timer, b = 20, par[N], w[N], dep[N];
bool ok[N];
set<int> g[N];  
vector<pair<int, int>> e[N];

int root;
void build(int v, int pr) {
    tin[v] = ++timer;
    up[v][0] = pr;
    for(int i = 1; i < b; i++) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for(int to:g[v]) {
        if(to != pr) {
            dep[to] = dep[v] + 1;
            build(to, v);
        }
    }
    tout[v] = ++timer;
}
bool is(int v, int u) {
    return  (tin[v] <= tin[u] && tout[u] <= tout[v]);
}
int lca(int v, int u) {
    if(is(v, u)) return v;
    if(is(u, v)) return u;
    for(int i = b - 1; i >= 0; i--) {
        if(!is(up[v][i], u)) {
            v = up[v][i];
        }
    }
    return up[v][0];
}
bool cmp(int x, int y) {
    return tin[x] < tin[y];
}
set<int> cur;
int p[N];
vector<int> er[N];
int get(int v) {
    if(p[v] == v) return v;
    int f = get(p[v]);
    return p[v] = f;
}
void make() {
    vector<int> t, t1;
    for(int i = 1; i <= n; i++) {
        if(ok[i]) {
            t.push_back(i);
        }
    }
    t1 = t;
    sort(t.begin(), t.end(), cmp);
    for(int i = 1; i < (int)t.size(); i++) {
        t1.push_back(lca(t[i], t[i - 1]));
    }
    sort(t1.begin(), t1.end());
    t1.resize(unique(t1.begin(), t1.end()) - t1.begin());
    sort(t1.begin(), t1.end(), cmp);
    vector<int> st;
    for(int i:t1) {
        cur.insert(i);
        p[i] = i;
        while(!st.empty() && !is(st.back(), i)) {
            st.pop_back();
        }
        if(!st.empty()) {
            e[st.back()].push_back({i, dep[i] - dep[st.back()] - 1});
            par[i] = st.back();
            w[i] = dep[i] - dep[st.back()] - 1;
        }
        st.push_back(i);
    }
}
void prec() {
    vector<int> u(n + 1), d(n + 1, 0);
    function<void(int)> go = [&](int v){
        d[v] = (ok[v] ? 0 : (int)1e9);
        for(auto [to, w] : e[v]) {
            go(to);
            d[v] = min(d[to] + w + 1, d[v]);
        }
    };
    function<void(int)> recalc = [&](int v) {
        multiset<int> vals;
        vals.insert(u[v]);
        for(auto [to, w] : e[v]) {
            vals.insert(d[to] + w);
        }
        for(auto [to, w] : e[v]) {
            if(ok[to]) {
                u[to] = 0;
                recalc(to);
            } else {
                vals.erase(vals.find(d[to] + w));
                u[to] = (*vals.begin()) + 1 + w;
                vals.insert(d[to] + w);
            }
        }
    };
    go(root);
    recalc(root);
    for(int i:cur) if(!ok[i]) {
        int mn = u[i] - 1, mn1 = (int)1e9;
        for(auto [to, f] : e[i]) {
            if(d[to] + f < mn) {
                mn1 = mn;
                mn = d[to] + f;
            } else if(d[to] + f < mn1) {
                mn1 = d[to] + f;
            }
        }
        if(mn == u[i] - 1 || mn1 == u[i] - 1) er[mn + mn1 + 1].push_back(i);
        else {
            assert(mn1 < u[i] - 1);
            er[u[i] + mn].push_back(i);
        }
    }
}

void remove(int i) {
    p[i] = par[i];
    cur.erase(i);
}
void solve(int v, int k) {
    dp[v][1] = 1 + k;
    for(auto [to, w] : e[v]) {
        solve(to, k);
        dp[v][0] += min(dp[to][0], dp[to][1]);
        dp[v][1] += min(dp[to][0], min(dp[to][1], dp[to][1] + w - k));
    }
    if(ok[v]) {
        dp[v][0] = (int)1e9;
    }
}
void test() {
    cin >> n;
    if(n > 5000) return;
    for(int i = 1; i <= n; i++) {
        char x;cin >> x;
        if(x == '1') {
            ok[i] = 1; 
            root = i;
        }
    }

    for(int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].insert(v);
        g[v].insert(u);
    }
    // root = 6;
    build(root, root);
    make();
    prec();
    for(int i = 1; i <= n;  i++) {
        e[i].clear();
    }
    int col = 0;
    for(int k = 1; k <= n; k++) {
        vector<int> rr;
        // for(int j:er[k]) {
        //     remove(j);
        //     col += w[j] + 1;
        // }
        for(int f:cur) if(f != root) {
            int t = get(par[f]);
            if(ok[f] && ok[t] && w[f] + 1 <= k) {
                cout << "x\n";
                rr.push_back(f);
                col += w[f] + 1;
            }
        }
        for(int f : rr) {
            remove(f);
        }
        for(int f:cur) {        
            if(f == root) continue;   
            int t = get(par[f]);
            e[t].push_back({f, w[f]});
        }
        solve(root, k);
        cout << min(dp[root][0], dp[root][1]) + col << '\n';
        for(int f:cur) {
            e[f].clear();
            dp[f][0] = dp[f][1] = 0;
        }
    }
}

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: 0
Wrong Answer
time: 4ms
memory: 20268kb

input:

5
10001
1 2
2 3
3 4
4 5

output:

4
6
8
x
9
10

result:

wrong output format Expected integer, but "x" found

Test #2:

score: 0
Wrong Answer
time: 2ms
memory: 20232kb

input:

7
0001010
7 4
5 6
7 2
5 1
6 3
2 5

output:

4
6
8
x
9
10
11
12

result:

wrong output format Expected integer, but "x" found

Test #3:

score: 0
Wrong Answer
time: 50ms
memory: 24844kb

input:

5000
0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000010000000...

output:

x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
711
x
x
x
837
x
944
1040
x
1121
x
1192
1249
x
1303
x
1352
1398
x
1439
1479
x
1518
1557
1596
x
1634
x
1671
x
1707
1742
x
1775
x
1807
1839
1871
x
1902
x
1932
x
1961
1990
x
2018
2046
x
2073
x
2099
2125
x
2150
x
2174
x
2197
2220
x
2242
2264
2286
...

result:

wrong output format Expected integer, but "x" found

Test #4:

score: 0
Wrong Answer
time: 91ms
memory: 22872kb

input:

5000
0100000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000...

output:

x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
890
x
x
x
1226
x
1433
x
1547
x
1619
x
1676
x
1727
x
1775
x
1821
x
1865
x
1908
x
1950
x
1989
x
2027
x
2064
x
2100
2136
x
2171
2206
x
2240
x
2273
x
2305
x
2336
x
2366
x
2395
2424
x
2452
x
2479
2506
...

result:

wrong output format Expected integer, but "x" found

Test #5:

score: 0
Wrong Answer
time: 48ms
memory: 20848kb

input:

5000
0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000001000000000000000001000000000000000000000000000000000000000000000000...

output:

x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
794
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
...

result:

wrong output format Expected integer, but "x" found

Test #6:

score: 0
Wrong Answer
time: 3ms
memory: 17904kb

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements

Test #7:

score: 0
Wrong Answer
time: 0ms
memory: 15924kb

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements

Test #8:

score: 0
Wrong Answer
time: 3ms
memory: 15800kb

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements

Test #9:

score: 0
Wrong Answer
time: 0ms
memory: 17976kb

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements

Test #10:

score: 0
Wrong Answer
time: 0ms
memory: 17908kb

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements

Test #11:

score: 0
Wrong Answer
time: 2ms
memory: 16120kb

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements

Test #12:

score: 0
Wrong Answer
time: 2ms
memory: 17916kb

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements

Test #13:

score: 0
Wrong Answer
time: 2ms
memory: 17912kb

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements

Test #14:

score: 0
Wrong Answer
time: 2ms
memory: 18164kb

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements

Test #15:

score: 0
Wrong Answer
time: 2ms
memory: 15832kb

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements

Test #16:

score: 0
Wrong Answer
time: 0ms
memory: 18136kb

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements

Test #17:

score: 0
Wrong Answer
time: 4ms
memory: 17976kb

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements

Test #18:

score: 0
Wrong Answer
time: 0ms
memory: 17972kb

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements

Test #19:

score: 0
Wrong Answer
time: 3ms
memory: 17852kb

input:

100000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements

Test #20:

score: 0
Wrong Answer
time: 2ms
memory: 17908kb

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements

Test #21:

score: 0
Wrong Answer
time: 2ms
memory: 17944kb

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements

Test #22:

score: 0
Wrong Answer
time: 2ms
memory: 17856kb

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements

Test #23:

score: 0
Wrong Answer
time: 2ms
memory: 17976kb

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements

Test #24:

score: 0
Wrong Answer
time: 0ms
memory: 16120kb

input:

200000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements
English 繁體中文 简体中文

服务器时间: 2024-12-05 06:41:35 | 开源项目