Talk is Cheap, Show Me the Code!

0%

AtCoder 187

Posted on In

A - Large Digits
Return max of S(A) and S(B).

large-digits.cppview raw
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
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <string>
#include <unordered_set>
using namespace std;

int sum(int x){
    int s = 0;
    while(x){
        s += x%10;
        x/=10;
    }
    return s;
}
int main(){
    int a, b;
    cin>>a>>b;
    int sa = sum(a), sb = sum(b);
    if(sa!=sb) cout<<max(sa, sb)<<endl;
    else cout<<sa<<endl;
    return 0;
}

B - Gentle Pairs
Return the number of points whose slope is between -1 and 1.

gentle-pairs.cppview raw
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
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <string>
#include <unordered_set>
using namespace std;

const int N = 1010;
int x[N], y[N];
int main() {
    int n;
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>x[i]>>y[i];
    }

    int res = 0;
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++){
            double t = (double)(y[j] - y[i])/ (x[j] - x[i]);
            if(t>=-1 && t<=1) res++;
        }
    cout<<res<<endl;
    return 0;

}

C - 1-SAT
Return the unsatifiable string.

1-sat.cppview raw
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
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <string>
#include <unordered_set>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    vector<string> str(n);
    for(auto &s: str) cin>>s;
    unordered_set<string> st(str.begin(), str.end());
    for(auto s: str){
        if(st.count('!' + s)) {
            cout << s << endl;
            return 0;
        }
    }
    cout<<"satisfiable"<<endl;
    return 0;
}

D - Choose Me
Choose the minimum number of speeches to make to win-over another candidate.
Use greedy method.

choose-me.cppview raw
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
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 2e5 + 10;
LL delta[N];

int main(){
    int n;
    cin>>n;
    LL sum = 0;
    for(int i=0;i<n;i++){
        LL a, b;
        scanf("%lld%lld", &a, &b);
        sum -= a;
        delta[i] = 2 * a + b;
    }

    sort(delta, delta + n, [](LL a, LL b){
        return a > b;
    });

    int cnt = 0;
    for(int i=0;i<n;i++){
        if(sum>0) break;
        cnt++;
        sum += delta[i];
    }
    cout<<cnt<<endl;
    return 0;

}

E - Through Path
There are N vertices and N-1 edges. Each edge connects ai and bi.
Perform the following 2 operations.

  1. add x to all descendants of ai without traversing bi;
  2. add x to all descendants of bi without traversing ai;

Print the value of each node at the end.

Solution1:
For operation 1, add x to global root and -x to vertex b;
For operation 2, add x to vertex b;
In order to propagate the change to its subtree, need to preprocess depths of each vertex.

through-path1.cppview raw
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
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

int main(){
    int n;
    cin>>n;
    vector<LL>G[n];
    vector<PII>edges;
    for(int i=0;i<n-1;i++){
        int a, b;
        scanf("%d%d", &a, &b);
        a--, b--;
        G[a].push_back(b);
        G[b].push_back(a);
        edges.push_back({a, b});
    }
    vector<int> depth(n, -1);
    queue<int> Q;
    depth[0] = 0;
    Q.push(0);
    while(Q.size()){
        int t = Q.front(); Q.pop();
        for(int i=0; i<G[t].size();i++){
            if(depth[G[t][i]]==-1){
                depth[G[t][i]] = depth[t] + 1;
                Q.push(G[t][i]);
            }
        }
    }

    vector<LL> s(n, 0);
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        int t, e, x;
        scanf("%d%d%d", &t, &e, &x);
        int a = edges[e-1].first, b = edges[e-1].second; // e-1
        if(depth[a] > depth[b]){
            swap(a, b);
            if(t==1) t = 2;
            else t = 1;
        }

        if(t==1){
            s[0] += x;
            s[b] -= x;
        }else s[b] += x;
    }

    Q = queue<int> ();
    Q.push(0);
    while(Q.size()){
        int t = Q.front(); Q.pop();
        for(int i=0;i<G[t].size();i++){
            if(depth[G[t][i]] > depth[t]) {
                s[G[t][i]] += s[t];
                Q.push(G[t][i]);
            }
        }
    }
    for(auto x: s) printf("%lld\n", x);
    return 0;
}

Solution2:
Solution1 doesn’t support online query and arbitrary range change between nodes.
For arbitrary range, use dfs order;
For online query, use segment tree.

through-path2.cppview raw
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
#define ls rt << 1
#define rs rt << 1 | 1
#define lson l , mid , rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define lr2 (l + r) >> 1
using namespace std;
typedef long long ll;
const int maxn = 4e5 + 50;
ll sum[maxn << 2], lazy[maxn << 2];
int L[maxn], R[maxn];
void push_up(int rt){
    sum[rt] = sum[ls] + sum[rs];
}
void push_down(int rt, int m){
    if(lazy[rt])
	{
		lazy[ls] += lazy[rt];
		lazy[rs] += lazy[rt];
		sum[ls] += lazy[rt] * (m - (m >> 1));
		sum[rs] += lazy[rt] * (m >> 1);
		lazy[rt] = 0;
	}
}
void update(int a, int b, ll v, int l, int r, int rt){
    if(a <= l && b >= r){
        sum[rt] += 1LL * (r - l + 1) * v;
        lazy[rt] += v;
        return;
    }
    push_down(rt, r - l + 1);
    int mid = lr2;
    if(a <= mid) update(a, b, v, lson);
    if(b > mid) update(a, b, v, rson);
    push_up(rt);
}
ll query(int a, int b, int l, int r, int rt){
    if(a <= l && b >= r){
        return sum[rt];
    }
    int mid = lr2;
    push_down(rt, r - l + 1);
    ll ans = 0;
    if(a <= mid) ans += query(a, b, lson);
    if(b > mid) ans += query(a, b, rson);
    return ans;
    push_up(rt);
}
int a[maxn], b[maxn];
int cnt, n;
vector<int> G[maxn];
int d[maxn];
void dfs(int v, int fa){
    L[v] = ++cnt;
    d[v] = d[fa] + 1;
    for(auto u : G[v]){
        if(u != fa){
            dfs(u, v);
        }
    }
    R[v] = cnt;
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 1;i < n;i++){
        cin >> a[i] >> b[i];
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
    }
    dfs(1, 0);
    int q;
    cin >> q;
    ll ans = 0;
    while(q--){
        int t, id;
        ll x;
        cin >> t >> id >> x;
        if(t == 1){
            if(d[a[id]] < d[b[id]]){
                ans += x;
                update(L[b[id]], R[b[id]], -x, 1, n, 1);
            }
            else update(L[a[id]], R[a[id]], x, 1, n, 1);
        }
        else{
            if(d[b[id]] < d[a[id]]){
                ans += x;
                update(L[a[id]], R[a[id]], -x, 1, n, 1);
            }
            else update(L[b[id]], R[b[id]], x, 1, n, 1);
        }
    }
    for(int i = 1;i <= n;i++) cout << query(L[i], L[i], 1, n ,1) + ans << endl;
    return 0;
}

F - Close Group
Given a graph of N nodes and M edges. A satisfied connected component is one where each pair of nodes within it are directly connected.
Can remove zero or more edges on the graph.
Return the minimum number of satisfied connected components.

Idea: For each set S, which is a subset of V, calculate dp[S] from its subset, using dynamic programming.
specifically, dp[S] = min(dp[T] + dp[S\T]), for all S’s subsets.
if {T} satisfies, the dp[T] = 1.
The satisfying condition can be pre-processed using O(2^N * N^2);
The transition takes O(3^N) time.
Time complexity: O(2^N * N^2 + 3^N).

close-group.cppview raw
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
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int N = 18, INF = 0x3f3f3f3f;
bool valid[1<<N];
bool adj[N][N];
int dp[1<<N];

int main(){
    int n, m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a, b;
        scanf("%d%d", &a, &b);
        a--, b--;
        adj[a][b] = adj[b][a] = 1;
    }

    for(int i=1;i<1<<n;i++){
        vector<int> vec;
        for(int j=0;j<n;j++){
            if(i>>j&1) vec.push_back(j);
        }
        bool flag = true;
        for(int u=0;u<vec.size();u++) {
            for (int v = u + 1; v < vec.size(); v++) {
                if (!adj[vec[u]][vec[v]]) { //error
                    flag = false;
                    break;
                }
            }
            if(!flag) break;
        }

        if(flag) valid[i] = true;
    }
    memset(dp, INF, sizeof dp);
    for(int i=1;i<1<<n;i++){
        if(valid[i]) dp[i] = 1;
        else {
            for (int j = i; j; j = (j - 1) & i) {
                dp[i] = min(dp[i], dp[j] + dp[i^j]);
            }
        }
    }
    cout<<dp[(1<<n)-1]<<endl;
    return 0;
}