Solutions

Problem A

1
#include <bits/stdc++.h>
14 collapsed lines
2
using namespace std;
3

4
#define int long long
5
#define rep(i, a, b) for(int i = a; i < (b); ++i)
6
#define all(x) begin(x), end(x)
7
#define sz(x) (int)(x).size()
8
#define eb emplace_back
9
#define pb push_back
10
#define vc vector
11
#define fs first
12
#define sd second
13
typedef pair<int, int> pii;
14
typedef vector<int> vi;
15

16
signed main() {
17
    cin.tie(0)->sync_with_stdio(0);
18
    cin.exceptions(cin.failbit);
19

20
    int n;
21
    cin >> n;
22
    double total = 0;
23
    double extras = 0;
24
    rep(i, 0, n) {
25
        string s;
26
        cin >> s;
27

28
        int numericScore = 4 - (s[0] - 'A');
29
        total += numericScore;
30

31
        if (s[0] <= 'C') {
32
            extras += ('3' - s[1]) * 0.025;
33
        }
34
    }
35

36
    cout << fixed << setprecision(9) << ((total / n) + extras) << endl;
37
}

1
#include <bits/stdc++.h>
14 collapsed lines
2
using namespace std;
3

4
#define int long long
5
#define rep(i, a, b) for(int i = a; i < (b); ++i)
6
#define all(x) begin(x), end(x)
7
#define sz(x) (int)(x).size()
8
#define eb emplace_back
9
#define pb push_back
10
#define vc vector
11
#define fs first
12
#define sd second
13
typedef pair<int, int> pii;
14
typedef vector<int> vi;
15

16
vc<vc<char>> read_in() {
17
    vc<vc<char>> ret(3, vc<char>(3));
18
    string s;
19
    rep(i, 0, 3) {
20
        cin >> s;
21
        rep(j, 0, 3) {
22
            ret[i][j] = s[j];
23
        }
24
    }
25

26
    return ret;
27
}
28

29
signed main() {
30
    cin.tie(0)->sync_with_stdio(0);
31
    cin.exceptions(cin.failbit);
32

33
    vc<vc<vc<char>>> cube(6, vc<vc<char>>(3, vc<char>(3, '?')));
34
        // 0 = front, 1 = R, 2 = rear, 3 = L, 4 = top, 5 = bottom
35
    vc<vc<char>> in = read_in();
36
    rep(i, 0, 3) rep(j, 0, 3) cube[0][i][j] = in[i][j];
37

38
    rep(i, 1, 4) {
39
        cout << "U" << endl; read_in(); cout << "D'" << endl;
40
        in = read_in();
41

42
        if (i != 2) {
43
            rep(j, 0, 3) cube[i][0][j] = in[0][j];
44
            rep(j, 0, 3) cube[i][2][j] = in[2][j];
45
        } else {
46
            rep(j, 0, 3) cube[i][2][2-j] = in[0][j];
47
            rep(j, 0, 3) cube[i][0][2-j] = in[2][j];
48
        }
49
    }
50

51
    // reset cube
52
    cout << "U" << endl; read_in(); cout << "D'" << endl; read_in();
53

54
    for (auto &i : {4, 2, 5, -1}) {
55
        cout << "L" << endl; read_in(); cout << "R'" << endl;
56
        in = read_in();
57

58
        if (i != -1) {
59
            rep(j, 0, 3) cube[i][j][0] = in[j][0];
60
            rep(j, 0, 3) cube[i][j][2] = in[j][2];
61
        }
62
    }
63

64
    // top
65
    cout << "U" << endl; read_in();
66
    cout << "R'" << endl; read_in();
67
    cout << "L" << endl;
68
    in = read_in();
69
    cube[4][2][1] = in[1][0];
70
    cube[4][0][1] = in[1][2];
71

72
    cout << "R" << endl; read_in();
73
    cout << "L'" << endl; read_in();
74
    cout << "U'" << endl; read_in();
75

76
    // right
77
    cout << "R" << endl; read_in();
78
    cout << "U" << endl; read_in();
79
    cout << "D'" << endl;
80
    in = read_in();
81
    cube[1][1][0] = in[0][1];
82
    cube[1][1][2] = in[2][1];
83

84
    cout << "U'" << endl; read_in();
85
    cout << "D" << endl; read_in();
86
    cout << "R'" << endl; read_in();
87

88
    // left
89
    cout << "L" << endl; read_in();
90
    cout << "U'" << endl; read_in();
91
    cout << "D" << endl;
92
    in = read_in();
93
    cube[3][1][0] = in[0][1];
94
    cube[3][1][2] = in[2][1];
95

96
    cout << "U" << endl; read_in();
97
    cout << "D'" << endl; read_in();
98
    cout << "L'" << endl; read_in();
99

100
    // bottom
101
    cout << "D" << endl; read_in();
102
    cout << "R" << endl; read_in();
103
    cout << "L'" << endl;
104
    in = read_in();
105
    cube[5][2][1] = in[1][0];
106
    cube[5][0][1] = in[1][2];
107

108
    cout << "R'" << endl; read_in();
109
    cout << "L" << endl; read_in();
110
    cout << "D'" << endl; read_in();
111

112
    cout << "A" << endl;
113
    rep(i, 0, 3) {
114
        cout << "   ";
115
        rep(j, 0, 3) cout << cube[4][i][j];
116
        cout << "   " << endl;
117
    }
118

119
    rep(i, 0, 3) {
120
        rep(j, 0, 3) cout << cube[3][i][j];
121
        rep(j, 0, 3) cout << cube[0][i][j];
122
        rep(j, 0, 3) cout << cube[1][i][j];
123
        cout << endl;
124
    }
125

126
    rep(i, 0, 3) {
127
        cout << "   ";
128
        rep(j, 0, 3) cout << cube[5][i][j];
129
        cout << "   " << endl;
130
    }
131
    rep(i, 0, 3) {
132
        cout << "   ";
133
        rep(j, 0, 3) cout << cube[2][i][j];
134
        cout << "   " << endl;
135
    }
136

137
}

1
#include <bits/stdc++.h>
14 collapsed lines
2
using namespace std;
3

4
#define int long long
5
#define rep(i, a, b) for(int i = a; i < (b); ++i)
6
#define all(x) begin(x), end(x)
7
#define sz(x) (int)(x).size()
8
#define eb emplace_back
9
#define pb push_back
10
#define vc vector
11
#define fs first
12
#define sd second
13
typedef pair<int, int> pii;
14
typedef vector<int> vi;
15

16
signed main() {
17
    cin.tie(0)->sync_with_stdio(0);
18
    cin.exceptions(cin.failbit);
19

20
    vc<vc<string>> arr(10, vc<string>(10));
21
    rep(i, 0, 10) rep(j, 0, 10) cin >> arr[i][j];
22

23
    reverse(all(arr));
24

25
    rep(i, 0, 10) {
26
        if (i % 2 == 1) {
27
            reverse(all(arr[i]));
28
        }
29
    }
30

31
    // row then col
32
    priority_queue<pair<int, pii>, vc<pair<int, pii>>, greater<>> pq;
33
    pq.push({0, {0, 0}});
34
    vc<vi> seen(10, vi(10, 0));
35
    while (!pq.empty()) {
36
        auto entry = pq.top();
37
        pq.pop();
38

39
        pii cur = entry.sd;
40

41
        // cout << "at square " << cur.fs << " " << cur.sd << endl;
42

43
        if (cur.fs >= 10 || (cur.fs == 9 && cur.sd == 9)) {
44
            cout << "Win in " << entry.fs << endl;
45
            exit(0);
46
        }
47

48
        if (seen[cur.fs][cur.sd]) continue;
49
        seen[cur.fs][cur.sd] = 1;
50

51
        // cout << "first time " << cur.fs << " " << cur.sd << endl;
52
        // cout << entry.fs << endl;
53

54
        string s = arr[cur.fs][cur.sd];
55
        if (s[0] == 'S') continue;
56

57
        if (s[0] == 'L') {
58
            pii target;
59
            if (sz(s) == 4) {
60
                cout << "Win in " << entry.fs << endl;
61
                exit(0);
62
            }
63

64
            if (sz(s) == 2) {
65
                target = {0, s[1] - '0' - 1};
66
            } else {
67
                target = {s[1] - '0', s[2] - '0' - 1};
68
                if (s[2] == '0') {
69
                    target = {s[1] - '0' - 1, 9};
70
                }
71
            }
72
            // cout << "climbing ladder to " << target.fs << " " << target.sd << endl;
73
            // cout << entry.fs << endl;
74
            pq.push({entry.fs, target});
75
            continue;
76
        }
77

78
        pii tmp = cur;
79
        rep(i, 0, 6) {
80
            tmp.sd++;
81
            if (tmp.sd >= 10) {
82
                tmp.sd -= 10;
83
                tmp.fs++;
84
            }
85
            // cout << cur.fs << " " << cur.sd << endl;
86
            // cout << "move to " << tmp.fs << " " << tmp.sd << endl;
87
            pq.push({entry.fs + 1, tmp});
88
        }
89
    }
90

91
    cout << "Snakes awaiting" << endl;
92
}

1
#include <bits/stdc++.h>
14 collapsed lines
2
using namespace std;
3

4
#define int long long
5
#define rep(i, a, b) for(int i = a; i < (b); ++i)
6
#define all(x) begin(x), end(x)
7
#define sz(x) (int)(x).size()
8
#define eb emplace_back
9
#define pb push_back
10
#define vc vector
11
#define fs first
12
#define sd second
13
typedef pair<int, int> pii;
14
typedef vector<int> vi;
15

16
signed main() {
17
    cin.tie(0)->sync_with_stdio(0);
18
    cin.exceptions(cin.failbit);
19

20
    set<int> s;
21
    int n; cin >> n;
22
    vector<set<int>> adj(10005);
23
    for (int i = 0; i < n; i++) {
24
        int a, b; cin >> a >> b;
25
        s.insert(a);
26
        s.insert(b);
27
        adj[a].insert(b);
28
        adj[b].insert(a);
29
    }
30

31
    int closed = 0, open = 0;
32

33
    for (auto &one : s) {
34
        for (auto &two : adj[one]) {
35
            for (auto &three : adj[two]) {
36
                if (three == one) continue;
37
                if (adj[one].count(three)) {
38
                    closed++;
39
                } else {
40
                    open++;
41
                }
42
            }
43
        }
44
    }
45
    cout << closed / 6 << " " << open / 2 << endl;
46

47

48
}

1
#include <bits/stdc++.h>
15 collapsed lines
2
using namespace std;
3

4
#define int long long
5
#define rep(i, a, b) for(int i = a; i < (b); ++i)
6
#define all(x) begin(x), end(x)
7
#define sz(x) (int)(x).size()
8
#define eb emplace_back
9
#define pb push_back
10
#define vc vector
11
#define fs first
12
#define sd second
13
#define ar array
14
typedef pair<int, int> pii;
15
typedef vector<int> vi;
16

17
signed main() {
18
    cin.tie(0)->sync_with_stdio(0);
19
    cin.exceptions(cin.failbit);
20

21
    int a, b, p;
22
    cin >> a >> b >> p;
23
    //vc<vi> dp(a+1, vi(b+1));
24
    int o = min(a, b);
25
    vector<ar<int, 2>> dp(o + 1, ar<int, 2>());
26
    // rep(i, 0, a+1) dp[i][0] = 0;
27
    // rep(i, 0, b+1) dp[0][i] = 0;
28
    // dp[1][1] = 1;
29
    // rep(i, 1, a+1) {
30
    //     rep(j, 1, b+1) {
31
    //         if (i == 1 && j == 1) continue;
32
    //
33
    //         dp[i][j] = (dp[i-1][j] + dp[i][j-1] + dp[i-1][j] * (i + j - 2)) % p;
34
    //     }
35
    // }
36
    dp[0][0] = 0;
37
    dp[0][1] = 0;
38
    for (int i = 0; i < o; i++) for (int k = 0; k < 2; k++) {
39
        (dp[i + 1][1] += dp[i][0]) %= p;
40
        (dp[i + 1][1] += dp[i][1]) %= p;
41
        (dp[i + 1][0] += dp[i][0]) %= p;
42
        (dp[i + 1][0] += dp[i][1]) %= p;
43
    }
44

45
    cout << (dp[o][0]) % p << endl;
46
}

1
#include <bits/stdc++.h>
14 collapsed lines
2
using namespace std;
3

4
#define int long long
5
#define rep(i, a, b) for(int i = a; i < (b); ++i)
6
#define all(x) begin(x), end(x)
7
#define sz(x) (int)(x).size()
8
#define eb emplace_back
9
#define pb push_back
10
#define vc vector
11
#define fs first
12
#define sd second
13
typedef pair<int, int> pii;
14
typedef vector<int> vi;
15

16
signed main() {
17
    cin.tie(0)->sync_with_stdio(0);
18
    cin.exceptions(cin.failbit);
19

20
    int t;
21
    cin >> t;
22
    while (t--) {
23
        pii a, b, c;
24
        cin >> a.fs >> a.sd >> b.fs >> b.sd >> c.fs >> c.sd;
25

26
        int aLen = a.fs * a.fs + a.sd * a.sd;
27
        int bLen = (b.fs - a.fs) * (b.fs - a.fs) + (b.sd - a.sd) * (b.sd - a.sd);
28
        int cLen = (c.fs - a.fs) * (c.fs - a.fs) + (c.sd - a.sd) * (c.sd - a.sd);
29

30
        bool possible = true;
31
        if (bLen > aLen || cLen > aLen) {
32
            possible = false;
33
        } else if (bLen < aLen && cLen < aLen) {
34
            possible = true;
35
        } else {
36
            // are A and B on same line, or A and C on same line, AND is equal to length?
37
            if (((b.fs == a.fs * 2 && b.sd == a.sd * 2) && aLen == bLen) || ((c.fs == a.fs * 2 && c.sd == a.sd * 2) && aLen == cLen)) {
38
                possible = false;
39
            } else {
40
                if (aLen == cLen && aLen == bLen) {
41
                    // are any 2 segments intersecting?
42
                    if ((b.fs == 0 && b.sd == 0) || (c.fs == 0 && c.sd == 0) || (b.fs == c.fs && b.sd == c.sd)) {
43
                        possible = true;
44
                    } else {
45
                        possible = false;
46
                    }
47
                } else {
48
                    possible = true;
49
                }
50
            }
51
        }
52

53
        cout << (possible ? "YES" : "NO") << endl;
54
    }
55
}

1
#include <bits/stdc++.h>
14 collapsed lines
2
using namespace std;
3

4
#define int long long
5
#define rep(i, a, b) for(int i = a; i < (b); ++i)
6
#define all(x) begin(x), end(x)
7
#define sz(x) (int)(x).size()
8
#define eb emplace_back
9
#define pb push_back
10
#define vc vector
11
#define fs first
12
#define sd second
13
typedef pair<int, int> pii;
14
typedef vector<int> vi;
15

16
signed main() {
17
    cin.tie(0)->sync_with_stdio(0);
18
    cin.exceptions(cin.failbit);
19

20
    int result = 0;
21
    int n;
22
    cin >> n;
23
    int prev = -1;
24
    rep(i, 0, n) {
25
        int x;
26
        cin >> x;
27
        int larger = max(prev, x), smaller = min(prev, x);
28

29
        if (prev != -1)
30
            result += larger * larger - smaller * smaller;
31
        prev = x;
32

33
        result += 4 * x * x;
34

35
        if (i == 0) {
36
            result += x * x;
37
        }
38
        if (i == n - 1) {
39
            result += x * x;
40
        }
41
    }
42

43
    cout << result << endl;
44
}

1
#include <bits/stdc++.h>
14 collapsed lines
2
using namespace std;
3

4
#define int long long
5
#define rep(i, a, b) for(int i = a; i < (b); ++i)
6
#define all(x) begin(x), end(x)
7
#define sz(x) (int)(x).size()
8
#define eb emplace_back
9
#define pb push_back
10
#define vc vector
11
#define fs first
12
#define sd second
13
typedef pair<int, int> pii;
14
typedef vector<int> vi;
15

16
signed main() {
17
    cin.tie(0)->sync_with_stdio(0);
18
    cin.exceptions(cin.failbit);
19

20
    int m, n, t;
21
    cin >> m >> n >> t;
22
    map<int, int> counts;
23
    counts[t / 2] = 0;
24
    counts[0] = 0;
25

26
    rep(i, 0, m) {
27
        int x;
28
        cin >> x;
29
        if (counts.count(x)) {
30
            counts[x]++;
31
        } else {
32
            counts[x] = 1;
33
        }
34
    }
35

36
    int extra = n - m;
37
    int already = 0, best = 0;
38

39
    set<int> seen;
40

41
    for (auto &cnt : counts) {
42
        if (seen.count(cnt.fs)) continue;
43
        int counterpart = t - cnt.fs;
44
        seen.insert(counterpart);
45
        if (cnt.fs < 0 || counterpart < 0) continue;
46
        int counterCount = counts.count(counterpart) ? counts[counterpart] : 0;
47

48
        if (cnt.fs == counterpart) {
49
            int contrib = (cnt.sd * (cnt.sd - 1)) / 2;
50
            already += contrib;
51
            int maxedOut = cnt.sd + extra;
52
            best = max(best, (maxedOut * (maxedOut - 1)) / 2 - contrib);
53
            continue;
54
        }
55

56
        already += cnt.sd * counterCount;
57

58
        int larger = max(counterCount, cnt.sd), smaller = min(counterCount, cnt.sd);
59
        int ogLarger = larger, ogSmaller = smaller;
60
        int myExtra = extra;
61
        if (larger - smaller >= myExtra) {
62
            smaller += myExtra;
63
        } else {
64
            myExtra -= (larger - smaller);
65
            smaller = larger;
66
            smaller += myExtra / 2;
67
            larger += (myExtra + 1) / 2;
68
        }
69
        best = max(best, smaller * larger - ogSmaller * ogLarger);
70

71
        // cout << cnt.fs << " " << cnt.sd << " " << best << endl;
72
    }
73

74
    cout << (already + best) << endl;
75
}

1
#include <bits/stdc++.h>
14 collapsed lines
2
using namespace std;
3

4
#define int long long
5
#define rep(i, a, b) for(int i = a; i < (b); ++i)
6
#define all(x) begin(x), end(x)
7
#define sz(x) (int)(x).size()
8
#define eb emplace_back
9
#define pb push_back
10
#define vc vector
11
#define fs first
12
#define sd second
13
typedef pair<int, int> pii;
14
typedef vector<int> vi;
15

16
signed main() {
17
    cin.tie(0)->sync_with_stdio(0);
18
    // cin.exceptions(cin.failbit);
19

20
    double n;
21
    while (cin >> n) {
22
        int cents = (int) round(n * 20);
23
        double res = cents / 20.0;
24
        cout << fixed << setprecision(2) << res << endl;
25
    }
26

27
}

1
#include <bits/stdc++.h>
14 collapsed lines
2
using namespace std;
3

4
#define int long long
5
#define rep(i, a, b) for(int i = a; i < (b); ++i)
6
#define all(x) begin(x), end(x)
7
#define sz(x) (int)(x).size()
8
#define eb emplace_back
9
#define pb push_back
10
#define vc vector
11
#define fs first
12
#define sd second
13
typedef pair<int, int> pii;
14
typedef vector<int> vi;
15

16
double manh(double x1, double x2, double y1, double y2) {
17
    return abs(x2 - x1) + abs(y2 - y1);
18
}
19

20
pair<double, double> umbrella(double x, double y) {
21
    return {sqrt(2) * -y, sqrt(2) * x};
22
}
23

24
void solve() {
25
    int x1, y1, x2, y2;
26
    char d1, d2;
27
    cin >> x1 >> y1 >> d1 >> x2 >> y2 >> d2;
28

29
    if (d1 == d2) {
30
        if (d1 == 'N') {
31
            double ret = manh(x1, x2, y1, y2);
32
            pair<double, double> a1 = umbrella(x1, y1), a2 = umbrella(x2, y2);
33
            double low = min(min(manh(x1, a1.fs / sqrt(2), y1, -a1.fs / sqrt(2)) + abs(a1.fs - a2.fs) + manh(x2, a2.fs / sqrt(2), y2, -a2.fs / sqrt(2)),
34
                                    manh(x1, a1.fs / sqrt(2), y1, -a1.fs / sqrt(2)) + abs(a1.fs - a2.sd) + manh(x2, a2.sd / sqrt(2), y2, -a2.sd / sqrt(2))),
35
                             min(manh(x1, a1.sd / sqrt(2), y1, -a1.sd / sqrt(2)) + abs(a1.sd - a2.fs) + manh(x2, a2.fs / sqrt(2), y2, -a2.fs / sqrt(2)),
36
                                    manh(x1, a1.sd / sqrt(2), y1, -a1.sd / sqrt(2)) + abs(a1.sd - a2.sd) + manh(x2, a2.sd / sqrt(2), y2, -a2.sd / sqrt(2))));
37
            ret = min(ret, low);
38
            cout << setprecision(16) << ret << endl;
39
        } else {
40
            cout << setprecision(16) << manh(x1, x2, y1, y2) << endl;
41
        }
42
        return;
43
    } else if (d1 == 'N') {
44
        swap(x1, x2);
45
        swap(y1, y2);
46
        swap(d1, d2);
47
    }
48

49
    pair<double, double> a1 = umbrella(x2, y2);
50
    double ret = manh(x1, a1.fs, y1, 0) + x2 + y2;
51
    ret = min(ret, manh(x1, a1.sd, y1, 0) + x2 + y2);
52
    ret = min(ret, manh(ceil(x1 / sqrt(2)), x2, -ceil(x1 / sqrt(2)), y2) + abs(y1) + abs(ceil(x1 / sqrt(2)) * sqrt(2) - x1));
53
    ret = min(ret, manh(floor(x1 / sqrt(2)), x2, -floor(x1 / sqrt(2)), y2) + abs(y1) + abs(floor(x1 / sqrt(2)) * sqrt(2) - x1));
54

55
    cout << setprecision(16) << ret << endl;
56
}
57

58
signed main() {
59
    cin.tie(0)->sync_with_stdio(0);
60
    cin.exceptions(cin.failbit);
61

62
    int q;
63
    cin >> q;
64
    while (q--) solve();
65
}

1
#pragma GCC optimize("Ofast")
19 collapsed lines
2

3
#include <bits/stdc++.h>
4
using namespace std;
5

6
#define int long long
7
#define rep(i, a, b) for(int i = a; i < (b); ++i)
8
#define all(x) begin(x), end(x)
9
#define sz(x) (int)(x).size()
10
#define eb emplace_back
11
#define pb push_back
12
#define vc vector
13
#define fs first
14
#define sd second
15
typedef pair<int, int> pii;
16
typedef vector<int> vi;
17

18
const int inf = 1e9;
19

20
struct Tree {
21
    typedef int T;
22
    static constexpr T unit = LLONG_MIN;
23
    T f(T a, T b) {
24
        return max(a, b);
25
    }
26
    vc<T> s; int n;
27
    Tree(int n = 0, T def = unit) : s(2 * n, def), n(n) {}
28

29
    void update(int pos, T val) {
30
        for (s[pos += n] = val; pos /= 2;)
31
            s[pos] = f(s[pos * 2], s[pos * 2] + 1);
32
    }
33

34
    T query(int b, int e) {
35
        T ra = unit, rb = unit;
36
        for (b += n, e += n; b < e; b /= 2, e/= 2) {
37
            if (b % 2) ra = f(ra, s[b++]);
38
            if (e % 2) rb = f(s[--e], rb);
39
        }
40
        return f(ra, rb);
41
    }
42
};
43

44
signed main() {
45
    cin.tie(0)->sync_with_stdio(0);
46
    cin.exceptions(cin.failbit);
47

48
    int n;
49
    cin >> n;
50
    vc<vc<pii>> neighbors(n);
51
    rep(i, 0, n) {
52
        int u, v, d;
53
        cin >> u >> v >> d;
54
        u--;
55
        v--;
56
        neighbors[u].pb({v, d});
57
        neighbors[v].pb({u, d});
58
    }
59

60
    vi prev(n, -1);
61
    int cycleEnd = -1;
62

63
    function<void(int, int)> dfs;
64
    dfs = [&](int cur, int par) {
65
        if (cycleEnd != -1) return;
66

67
        if (prev[cur] != -1) {
68
            cycleEnd = cur;
69
            return;
70
        }
71
        prev[cur] = par;
72

73
        for (auto &neighbor : neighbors[cur]) {
74
            if (neighbor.fs == par) continue;
75
            if (cycleEnd != -1) return;
76

77
            dfs(neighbor.fs, cur);
78
        }
79
    };
80
    dfs(0, -1);
81

82
    assert(cycleEnd != -1);
83
    vi cycleList = {cycleEnd};
84
    int cur = prev[cycleEnd];
85
    while (cur != cycleEnd) {
86
        cycleList.pb(cur);
87
        cur = prev[cur];
88
    }
89

90
    for (int num : cycleList) {
91
        cout << num << ' ';
92
    }
93
    cout << endl;
94

95
    int numTrees = sz(cycleList);
96
    vi subtreeDepths(numTrees, 0);
97
    vi distToRoot(n, 0), rootId(n);
98
    rep(i, 0, numTrees) {
99
        function<void(int, int, int)> dfs;
100
        dfs = [&](int cur, int par, int dist) {
101
            rootId[cur] = cycleList[i];
102
            distToRoot[cur] = dist;
103

104
            subtreeDepths[i] = max(subtreeDepths[i], dist);
105

106
            for (auto &neighbor : neighbors[cur]) {
107
                if (neighbor.fs == cycleList[(i + 1) % numTrees] || neighbor.fs == cycleList[(i - 1 + numTrees) % numTrees] || neighbor.fs == par) {
108
                    continue;
109
                }
110
                dfs(neighbor.fs, cur, dist + neighbor.sd);
111
            }
112
        };
113
        dfs(cycleList[i], -1, 0);
114
    }
115

116
    vi cycleDists(numTrees, 0);
117

118
    int totalAroundCycle = 0;
119
    rep(i, 0, numTrees) {
120
        int node = cycleList[i];
121
        for (auto &neighbor : neighbors[node]) {
122
            if (neighbor.fs == cycleList[(i + 1) % numTrees]) {
123
                cycleDists[i] = neighbor.sd;
124
                break;
125
            }
126
        }
127
        totalAroundCycle += cycleDists[i];
128
    }
129

130
    Tree cwDist(numTrees), ccwDist(numTrees);
131
    int cwPrefix = 0;
132
    rep(i, 0, numTrees) {
133
        cout << "sub depth: " << subtreeDepths[i] << endl;
134
        cwDist.update(i, cwPrefix + subtreeDepths[i]);
135
        ccwDist.update(i, totalAroundCycle - cwPrefix + subtreeDepths[i]);
136
        cwPrefix += cycleDists[i];
137
    }
138

139
    int cwOffset = 0, ccwOffset = 0;
140

141
    int x = 0;
142
    vi maxDists(n, 0);
143
    rep(i, 0, numTrees) {
144
        cout << "offsets " << cwOffset << " " << ccwOffset << endl;
145

146
        cwDist.update(i,  subtreeDepths[i] -cwOffset);
147
        ccwDist.update(i, subtreeDepths[i] -ccwOffset);
148

149
        while (cwDist.query(x, x + 1) + cwOffset <= ccwDist.query(x, x + 1) + ccwOffset) {
150
            x = (x + 1) % numTrees;
151
        }
152
        x = (x + numTrees - 1) % numTrees;
153

154
        int mMax = 0;
155
        if (i <= x) {
156
            mMax = max(mMax, cwDist.query(i, x + 1) + cwOffset);
157
        } else {
158
            mMax = max(mMax, cwDist.query(0, x + 1) + cwOffset);
159
            mMax = max(mMax, cwDist.query(i, numTrees) + cwOffset);
160
        }
161
        if (i <= x) {
162
            mMax = max(mMax, ccwDist.query(0, i) + ccwOffset);
163
            mMax = max(mMax, ccwDist.query(x + 1, numTrees) + ccwOffset);
164
        } else {
165
            mMax = max(mMax, ccwDist.query(x + 1, i) + ccwOffset);
166
        }
167

168
        maxDists[cycleList[i]] = mMax;
169

170
        cwOffset -= cycleDists[i];
171
        ccwOffset += cycleDists[i];
172

173
        if (cwOffset >= totalAroundCycle) {
174
            cwOffset -= totalAroundCycle;
175
        }
176
        if (cwOffset < 0) {
177
            cwOffset += totalAroundCycle;
178
        }
179

180
        if (ccwOffset >= totalAroundCycle) {
181
            ccwOffset -= totalAroundCycle;
182
        }
183
        if (ccwOffset < 0) {
184
            ccwOffset += totalAroundCycle;
185
        }
186

187
        cwDist.update(i, totalAroundCycle + subtreeDepths[i] - cycleDists[i] - cwOffset);
188
        ccwDist.update(i,cycleDists[i] + subtreeDepths[i] - ccwOffset);
189
    }
190

191
    rep(i, 0, n) {
192
        int res = distToRoot[i] + maxDists[rootId[i]];
193

194
        cout << res << ' ';
195
    }
196
    cout << endl;
197
}

1
#include <bits/stdc++.h>
14 collapsed lines
2
using namespace std;
3

4
#define int long long
5
#define rep(i, a, b) for(int i = a; i < (b); ++i)
6
#define all(x) begin(x), end(x)
7
#define sz(x) (int)(x).size()
8
#define eb emplace_back
9
#define pb push_back
10
#define vc vector
11
#define fs first
12
#define sd second
13
#define ar array
14
typedef pair<int, int> pii;
15

16
signed main() {
17
    cin.tie(0)->sync_with_stdio(0);
18
    cin.exceptions(cin.failbit);
19
    int n; cin >> n;
20

21
    multiset<int> endCounts;
22
    // first is x-coord, second is x-coord of end
23
    vc<pii> starts;
24
    int pairs = 0;
25

26
    rep(i, 0, n) {
27
        int x, r;
28
        cin >> x >> r;
29
        int start = x - r, end = x + r;
30
        starts.pb({start, end});
31
    }
32
    sort(all(starts));
33
    rep(i, 0, n) {
34
        // process pending ends, pairing together as needed
35
        while (!endCounts.empty() && *endCounts.begin() < starts[i].fs) {
36
            if (sz(endCounts) == 1) {
37
                endCounts.erase(endCounts.begin());
38
            } else {
39
                endCounts.erase(endCounts.begin());
40
                endCounts.erase(endCounts.begin());
41
                pairs++;
42
            }
43
        }
44

45
        // process this start
46
        endCounts.insert(starts[i].sd);
47
    }
48

49
    // end parsing
50
    while (!endCounts.empty()) {
51
        if (sz(endCounts) == 1) {
52
            endCounts.erase(endCounts.begin());
53
        } else {
54
            endCounts.erase(endCounts.begin());
55
            endCounts.erase(endCounts.begin());
56
            pairs++;
57
        }
58
    }
59

60
    cout << (n - 2 * pairs) << endl;
61
}

1
#include <bits/stdc++.h>
14 collapsed lines
2
using namespace std;
3

4
#define int long long
5
#define rep(i, a, b) for(int i = a; i < (b); ++i)
6
#define all(x) begin(x), end(x)
7
#define sz(x) (int)(x).size()
8
#define eb emplace_back
9
#define pb push_back
10
#define vc vector
11
#define fs first
12
#define sd second
13
typedef pair<int, int> pii;
14
typedef vector<int> vi;
15

16
signed main() {
17
    cin.tie(0)->sync_with_stdio(0);
18
    cin.exceptions(cin.failbit);
19

20
    int r, c, s;
21
    cin >> r >> c >> s;
22
    vc<vi> slots(s, vi(3));
23
}