Shawn's Blog

Posted on Edited on In 
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
class Solution {
public:
    int maximumMinutes(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size(), ds[] = {0, 1, 0, -1, 0};
        queue<pair<int, int>> q;
        vector<vector<int>> dis(m, vector<int>(n, -1));
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == 1)
                    dis[i][j] = 0, q.emplace(i, j);
        while (q.size()) {
            auto [x, y] = q.front(); q.pop();
            for (int i = 0; i < 4; ++i) {
                int nx = x + ds[i], ny = y + ds[i + 1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || dis[nx][ny] != -1 || grid[nx][ny] == 2) continue;
                dis[nx][ny] = dis[x][y] + 1;
                q.emplace(nx, ny);
            }
        }
        auto check = [&](int k) {
            if (dis[0][0] != -1 && dis[0][0] <= k) return false;
            queue<pair<int, int>> q;
            q.emplace(0, 0);
            vector<vector<int>> dep(m, vector<int>(n, -1));
            dep[0][0] = 0;
            while (q.size()) {
                auto [x, y] = q.front(); q.pop();
                for (int i = 0; i < 4; ++i) {
                    int nx = x + ds[i], ny = y + ds[i + 1];
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n || dep[nx][ny] != -1 || grid[x][y] == 2) continue;
                    if (dis[nx][ny] != -1 && 
                        dep[x][y] + 1 + k >= dis[nx][ny] + (nx == m - 1 && ny == n - 1)) continue;
                    dep[nx][ny] = dep[x][y] + 1;
                    q.emplace(nx, ny);
                }
            }
            return dep[m - 1][n - 1] != -1;
        };
        int ans = -1, l = 0, r = 1e9;
        while (l <= r) {
            int mid = l + r >> 1;
            if (check(mid)) ans = mid, l = mid + 1;
            else r = mid - 1;
        }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int longestPath(vector<int>& parent, string s) {
        int n = parent.size();
        vector<vector<int>> g(n, vector<int>());
        for (int i = 1; i < n; ++i) {
            g[parent[i]].emplace_back(i);
        }
        int ans = 0;
        function<int(int)> dfs = [&](int u) {
            int maxLen = 0;
            for (int v : g[u]) {
                int len = dfs(v) + 1;
                if (s[v] != s[u]) {
                    ans = max(ans, maxLen + len);
                    maxLen = max(maxLen, len);
                }
            }
            return maxLen;
        };
        dfs(0);
        return ans + 1;
    }
};

Posted on Edited on In 
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
class Solution {
public:
    int maximumScore(vector<int>& scores, vector<vector<int>>& edges) {
        int n = scores.size();
        vector<vector<int>> g(n, vector<int>());
        for (auto &e : edges) {
            g[e[0]].emplace_back(e[1]);
            g[e[1]].emplace_back(e[0]);
        }
        int ans = -1;
        for (int i = 0; i < n; ++i) {
            sort(g[i].begin(), g[i].end(), [&](int x, int y) {
                return scores[x] > scores[y];
            });
        }
        for (auto &e : edges) {
            int x = e[0], y = e[1];
            for (int i = 0; i < 4 && i < g[x].size(); ++i) {
                if (g[x][i] != y) {
                    for (int j = 0; j < 4 && j < g[y].size(); ++j) {
                        if (g[y][j] != x && g[x][i] != g[y][j]) {
                            ans = max(ans, scores[g[x][i]] + scores[x] + scores[y] + scores[g[y][j]]);
                        }
                    }
                }
            }
        }
        return ans;
    }
};

Posted on Edited on In 
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
class Encrypter {
private:
    unordered_map<char, string> k2v;
    unordered_map<string, int> encrypted_dict;
public:
    Encrypter(vector<char>& keys, vector<string>& values, vector<string>& dictionary) {
        for (int i = 0; i < keys.size(); ++i)
            k2v[keys[i]] = values[i];
        unordered_map<string, string> dict;
        for (string &s : dictionary) {
            if (dict.count(s)) {
                ++encrypted_dict[dict[s]];
            } else {
                string encryptedStr = "";
                for (char c : s) encryptedStr += k2v[c];
                ++encrypted_dict[encryptedStr];
                dict[s] = encryptedStr;
            }
        }
    }
    
    string encrypt(string word1) {
        string ans;
        for (char &c : word1) ans += k2v[c];
        return ans;
    }
    
    int decrypt(string word2) {
        return encrypted_dict[word2];
    }
};

/**
 * Your Encrypter object will be instantiated and called as such:
 * Encrypter* obj = new Encrypter(keys, values, dictionary);
 * string param_1 = obj->encrypt(word1);
 * int param_2 = obj->decrypt(word2);
 */

Posted on Edited on In 
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
class Solution {
public:
    long long sumScores(string s) {
        int n = s.size(), l = 0, r = 0;
        vector<int> z(n);
        z[0] = n;
        for (int i = 1; i < n; ++i) {
            if (i > r) {
                l = r = i;
                while (r < n && s[r] == s[r - l] ) ++r;
                z[i] = r - l;
                --r;
            } else {
                int i1 = i - l;
                if (z[i1] + i <= r) {
                    z[i] = z[i1];
                } else {
                    l = i;
                    while (r < n && s[r] == s[r - l]) ++r;
                    z[i] = r - l;
                    --r;
                }
            }
        }
        return accumulate(z.begin(), z.end(), (long long) 0);
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        vector<vector<int>> g(n), ans(n);
        for (auto &e : edges)
            g[e[0]].emplace_back(e[1]);
        function<void(int, int)> dfs = [&](int f, int u) {
            for (int v : g[u]) {
                if (ans[v].empty() || ans[v].back() != f) {
                    ans[v].emplace_back(f);
                    dfs(f, v);
                }
            }
        };
        for (int i = 0; i < n; ++i)
            dfs(i, i);
        return ans;
    }
}; 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        bitset<1000> a[1000];
        for (auto &e : edges)
            a[e[0]][e[1]] = 1;
        for (int v = 0; v < n; ++v)
            for (int u = 0; u < n; ++u)
                if (a[u][v])
                    a[u] |= a[v];
        vector<vector<int>> ans;
        for (int v = 0; v < n; ++v) {
            vector<int> f;
            for (int u = 0; u < n; ++u)
                if (a[u][v])
                    f.emplace_back(u);
            ans.emplace_back(f);
        }
        return ans;
    }
}; 
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
class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        vector<vector<int>> g(n), ans(n);
        vector<int> d(n);
        vector<set<int>> f(n);
        for (auto &e : edges) {
            g[e[0]].emplace_back(e[1]);
            ++d[e[1]];
        }
        queue<int> q;
        for (int i = 0; i < n; ++i)
            if (d[i] == 0)
                q.emplace(i);
        while (q.size()) {
            int u = q.front(); q.pop();
            for (int v : g[u]) {
                f[v].insert(u);
                f[v].insert(f[u].begin(), f[u].end());
                if (--d[v] == 0) {
                    q.emplace(v);
                }
            }
        }
        for (int i = 0; i < n; ++i)
            ans[i].assign(f[i].begin(), f[i].end());
        return ans;
    }
};

Posted on Edited on In 
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
#include <iostream>
using namespace std;
using LL = long long;
const int N = 1000002;
int n, root;
int h[N], w[N], e[N], ne[N], idx, fa[N];
bool vis[N];
LL f[N][2], ans = 0;
void add(int u, int v) {
    e[++idx] = v, ne[idx] = h[u], h[u] = idx;
}
void dp(int u) {
    vis[u] = true;
    f[u][0] = 0, f[u][1] = w[u];
    for (int i = h[u]; i; i = ne[i]) {
        int v = e[i];
        if (v != root) {
            dp(v);
            f[u][0] += max(f[v][0], f[v][1]);
            f[u][1] += f[v][0];
        } else {
            f[v][1] = -N;
        }
    }
}
void dfs(int u) {
    vis[u] = true;
    root = u;
    while (!vis[fa[root]]) {
        root = fa[root];
        vis[root] = true;
    }
    dp(root);
    LL tmp = max(f[root][0], f[root][1]);
    vis[root] = true;
    root = fa[root];
    dp(root);
    ans += max(tmp, max(f[root][0], f[root][1]));
}
int main() {
    scanf("%d", &n);
    for (int v = 1, u; v <= n; ++v) {
        scanf("%d%d", &w[v], &u);
        add(u, v);
        fa[v] = u;
    }
    for (int i = 1; i <= n; ++i) {
        if (vis[i]) continue;
        dfs(i);
    }
    printf("%lld\n", ans);
    return 0;
}
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
#include <iostream>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
const int N = 1000002, M = N * 2;
int n, c, p[N];
PII root[N / 2];
int h[N], w[N], e[M], ne[M], idx;
LL f[N][2], ans;
int find(int x) {
    return x == p[x] ? x : p[x] = find(p[x]);
}
void add(int u, int v) {
    e[++idx] = v, ne[idx] = h[u], h[u] = idx;
}
LL dp(int u, int fa) {
    f[u][0] = 0, f[u][1] = w[u];
    for (int i = h[u]; i; i = ne[i]) {
        int v = e[i];
        if (v == fa) continue;
        dp(v, u);
        f[u][0] += max(f[v][0], f[v][1]);
        f[u][1] += f[v][0];
    }
    return f[u][0];
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) p[i] = i;
    for (int u = 1, v; u <= n; ++u) {
        scanf("%d%d", &w[u], &v);
        if (find(u) != find(v)) {
            p[find(u)] = find(v);
            add(u, v), add(v, u);
        } else {
            root[c++] = {u, v};
        }
    }
    for (int i = 0; i < c; ++i) {
        auto [u, v] = root[i];
        ans += max(dp(u, 0), dp(v, 0));
    }
    printf("%lld\n", ans);
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> canSeePersonsCount(vector<int>& heights) {
        int n = heights.size();
        vector<int> ans(n);
        stack<int> stk;
        for (int i = 0; i < n; ++i) {
            int h = heights[i];
            while (!stk.empty() && heights[stk.top()] <= h)
                ++ans[stk.top()], stk.pop();
            if (!stk.empty())
                ++ans[stk.top()];
            stk.emplace(i);
        }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    using LL = long long;
public:
    vector<vector<long long>> splitPainting(vector<vector<int>>& segments) {
        vector<LL> diff(100001);
        unordered_map<int, set<int>> m;
        for (auto &s : segments) {
            diff[s[0]] += s[2];
            diff[s[1]] -= s[2];
            m[s[0]].insert(s[2]);
        }
        vector<vector<LL>> ans;
        LL s = 0, prev = 0;
        for (int i = 0; i < 100001; ++i)
            if (diff[i] != 0 || (m.count(i) && m[i] != m[i - 1])) {
                if (prev != 0 && s != 0)
                    ans.push_back({prev, i, s});
                s += diff[i];
                prev = i;
            }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    using PII = pair<int, int>;
public:
    int smallestChair(vector<vector<int>>& times, int targetFriend) {
        int n = times.size(), tt = times[targetFriend][0];
        sort(times.begin(), times.end());
        priority_queue<int, vector<int>, greater<int>> q1; // available
        priority_queue<PII, vector<PII>, greater<PII>> q2; // unavailable
        for (int i = 0; i < n; ++i) q1.emplace(i);
        for (int i = 0; i < n; ++i) {
            while (!q2.empty() && q2.top().first <= times[i][0]) {
                q1.emplace(q2.top().second);
                q2.pop();
            }
            if (times[i][0] == tt) return q1.top();
            q2.emplace(times[i][1], q1.top());
            q1.pop();
        }
        return 0;
    }
};
0%