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
|
#include <algorithm>
#include <iostream>
#include <limits>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
class
Directory
{
public:
Directory *parent = nullptr;
unordered_map<string, Directory*> dirs;
long direct_size = 0;
void
mkdir(string name)
{
dirs[name] = new Directory();
dirs[name]->parent = this;
}
void
mkfile(string name, long size)
{
(void) name;
direct_size += size;
}
Directory*
cd(string path)
{
return parent;
}
};
template<typename F>
long
getSizes(Directory *dir, F&& fn)
{
long size = dir->direct_size;
for (auto &c : dir->dirs) {
size += getSizes(c.second, fn);
}
fn(size);
return size;
}
int
main()
{
Directory root;
Directory *pwd = &root;
for (string line; getline(cin, line); ) {
if (line.compare(0, 4, "$ cd") == 0) {
string path = line.substr(5);
if (path == "/") {
pwd = &root;
} else if (path == "..") {
pwd = pwd->parent;
} else {
pwd = pwd->dirs[path];
}
if (pwd == nullptr) throw "bad input";
}
if (line[0] != '$') {
int pos = line.find(" ");
string meta = line.substr(0, pos);
string name = line.substr(pos + 1);
if (meta == "dir") {
pwd->mkdir(name);
} else {
pwd->mkfile(name, stol(meta));
}
}
}
long total1 = 0;
long used = getSizes(&root, [&](long size){
if (size <= 100000)
total1 += size;
});
cout << total1 << endl;
long diskSize = 70000000;
long updateSize = 30000000;
long smallest = numeric_limits<long>::max();
getSizes(&root, [&](long size){
if (used - size + updateSize <= diskSize)
smallest = min(smallest, size);
});
cout << smallest << endl;
}
|
