Codeforces Round 408 Div2 Problem C

Posted on | In ,

Bank Hacking

Solution sketch

跟 binary search 無關，還有，時間複雜度如果亂估會以為會 TLE 的好題。

這題題解寫得很清楚，我只補充一下我當初有另外想通的地方。

為何只有 $m$, $m+1$, 和 $m+2$ 三種可能答案呢？因為這其實是一個 tree。所以說，如果我們把樹吊起來想，對於每個node來說，他至多就只可能被自己的parent和parent’s parent加到。

實作上，就是先建立一個總數表（我是對於$m+2$建表）。對於所有的點枚舉，只處理自己和他的鄰居這兩層後，求取minimax。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
vector<int> g[300010];
int main()
{
    int n;
    scanf("%d", &n);
    int inp[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &inp[i]);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        u--;
        v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int ans = INT_MAX;
    map<int, int> cnt;
    for (int i = 0; i < n; i++) {
        cnt[inp[i] + 2]++;
    }
    for (int i = 0; i < n; i++) {
        stack<ii> s;
        // self
        cnt[inp[i]]++;
        cnt[inp[i] + 2]--;
        s.push(ii(inp[i], -1));
        s.push(ii(inp[i] + 2, 1));
        // neighbor
        for (auto v : g[i]) {
            cnt[inp[v] + 1]++;
            cnt[inp[v] + 2]--;
            s.push(ii(inp[v] + 1, -1));
            s.push(ii(inp[v] + 2, 1));
        }
        // update ans
        for (auto i = cnt.rbegin(); i != cnt.rend(); i++) {
            if (i->second != 0) {
                ans = min(ans, i->first);
                break;
            }
        }
        // recover
        while (s.empty() == false) {
            ii cur = s.top();
            s.pop();
            cnt[cur.first] += cur.second;
        }
    }
    printf("%d\n", ans);
    return 0;
}