제출 #592334

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
592334	2022-07-09 00:04:35	shrimb	경주 (Race) (IOI11_race)	C++17	100 / 100	300 ms	78456 KiB

race

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
#include "bits/stdc++.h"
#include "race.h"
using namespace std;
const int maxn = 200001;
vector<pair<int,int>> adj[maxn];
int k;
unordered_map<long long,int> *maps[maxn];
void Check (int cur, int x, int y, int& ret, int dep2, int dep) {
    if (maps[cur] -> count(k + 2 * dep - x)) {
        ret = min(ret, y + (*maps[cur])[k + 2 * dep - x] - 2 * dep2);
    }
}
void Insert (int cur, int x, int y) {
    if (maps[cur] -> count(x)) (*maps[cur])[x] = min((*maps[cur])[x], y);
    else (*maps[cur])[x] = y;
}
int dfs (int cur, int par, int dep, int dep2) { // dep = sum of weights // dep2 = number of edges from root
    if ((adj[cur].empty()) || (adj[cur].size() == 1 and cur != 0)) {
        maps[cur] = new unordered_map<long long, int>();
        maps[cur] -> insert({dep, dep2});
        return INT_MAX;
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57