ICPC 2019-2020 North-Western Russia Regional Contest | JorbanS

A - Accurate Movement

#include 

using namespace std;
#define FastIO cin.tie(nullptr) -> sync_with_stdio(false);

int solve() {
    int a, b, n; cin >> a >> b >> n;
    int dx = b - a;
    int A = (n - a + dx - 1) / dx;
    int B = (n - b + dx - 1) / dx;
    return A + B;
}

int main() {
    FastIO
    cout << solve() << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

E - Equidistant

#include 
#include 
#include 

using namespace std;
#define FastIO cin.tie(nullptr) -> sync_with_stdio(false);
#define Cases int __; cin >> __; for (int _ = 1; _ <= __; _ ++)
const string yes = "YES";
const string no = "NO";

typedef long long ll;
const int N = 2e5 + 2;
int n, m;
int deg[N];
vector<vector<int>> e(N);
vector<int> eee;
bool del[N], used[N], vis[N];
int dis[N];

int d1[N], d2[N], p1[N], up[N];

int dfs_d(int u, int fa = 0) {
    d1[u] = d2[u] = 0;
    for (auto v : e[u]) {
        if (v == fa || del[v]) continue;
        int d = dfs_d(v, u) + 1;
        if (d >= d1[u]) d2[u] = d1[u], d1[u] = d, p1[u] = v;
        else if (d > d2[u]) d2[u] = d;
    }
    return d1[u];
}

void dfs_u(int u, int fa = 0) {
    for (auto v : e[u]) {
        if (v == fa || del[v]) continue;
        if (v == p1[u]) up[v] = max(up[u], d2[u]) + 1;
        else up[v] = max(up[u], d1[u]) + 1;
        dfs_u(v, u);
    }
}

int main() {
    FastIO
    cin >> n >> m;
    for (int i = 1; i < n; i ++) {
        int u, v; cin >> u >> v;
        e[u].push_back(v), e[v].push_back(u);
        deg[u] ++, deg[v] ++;
    }
    for (int i = 1; i <= m; i ++) {
        int x; cin >> x;
        used[x] = true;
        eee.push_back(x);
    }
    queue<int> q;
    for (int i = 1; i <= n; i ++)
        if (deg[i] == 1 && !used[i]) q.push(i);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        del[u] = true;
        for (auto v : e[u]) {
            if (-- deg[v] == 1 && !used[v]) q.push(v);
        }
    }
    int st;
    for (int i = 1; i <= n; i ++)
        if (!del[i]) st = i;
    dfs_d(st);
    dfs_u(st);
    vector<int> ans;
    int minn = n;
    for (int i = 1; i <= n; i ++) {
        if (del[i]) continue;
        int l = max(d1[i], up[i]);
        if (l < minn) minn = l, ans.clear(), ans.push_back(i);
        else if (l == minn) ans.push_back(i);
    }
    for (auto i : ans) {
        for (int i = 1; i <= n; i ++) vis[i] = false;
        queue<int> q;
        q.push(i);
        dis[i] = 0;
        vis[i] = true;
        bool ok = true;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto v : e[u]) {
                if (!del[v] && !vis[v]) {
                    vis[v] = true;
                    q.push(v);
                    dis[v] = dis[u] + 1;
                }
            }
        }
        for (int i = 1; i < eee.size(); i ++)
            if (dis[eee[i - 1]] != dis[eee[i]]) {
                ok = false;
                break;
            }
        if (ok) {
            cout << yes << endl << i << endl;
            return 0;
        }
    }
    cout << no << endl;
    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
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
98
99
100
101
102
103
104
105
106
107
108
109

I - Ideal Pyramid

#include 

using namespace std;
#define FastIO cin.tie(nullptr) -> sync_with_stdio(false);
const int N = 1e3 + 2;
int n;
int x[N], y[N], z[N];

struct Point {
    int x, y;
    Point(int x, int y): x(x), y(y) {}
};

int main() {
    FastIO
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> x[i] >> y[i] >> z[i];
    int c1 = -1e9, c2 = 1e9, c3 = -1e9, c4 = 1e9;
    for (int i = 0; i < n; i ++) {
        // x - z + c1 >= 0, c1 >= z - x
        c1 = max(c1, z[i] - x[i]);
        // x + z + c2 >= 0, c2 >= -z - x
        c2 = min(c2, -z[i] - x[i]);
        // y - z + c3 >= 0, c3 >= z - y
        c3 = max(c3, z[i] - y[i]);
        // y + z + c4 >= 0, c4 >= -z - y
        c4 = min(c4, -z[i] - y[i]);
    }
    Point A(-c1, -c3), B(-c2, -c3), C(-c2, -c4), D(-c1, -c4);
    int ab = B.x - A.x, bc = C.y - B.y;
    if (ab & 1) ab ++;
    if (bc & 1) bc ++;
    int x, y, z;
    int l = max(ab, bc);
    z = l / 2;
    x = A.x + z, y = A.y + z;
    cout << x << ' ' << y << ' ' << z << endl;
    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

M - Managing Difficulties

#include 
#include 

using namespace std;
#define FastIO cin.tie(nullptr) -> sync_with_stdio(false);
#define Cases int __; cin >> __; for (int _ = 1; _ <= __; _ ++)
#define endl '\n'

typedef long long ll;
const int N = 2e5 + 2;
int n, m;

int a[N];

ll solve() {
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    ll res = 0;
    unordered_map<int, int> mp;
    for (int j = 1; j < n; j ++) {
        for (int i = j + 1; i <= n; i ++)
            res += mp[2 * a[j] - a[i]];
        mp[a[j]] ++;
    }
    return res;
}

int main() {
    FastIO
    Cases
    cout << solve() << endl;
    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