## Submission #107405

# Submission time Handle Problem Language Result Execution time Memory
107405 2019-04-24T05:55:32 Z shoemakerjo Designated Cities (JOI19_designated_cities) C++14
7 / 100
531 ms 35788 KB
```#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int maxn = 200010;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pil pair<int, pll>
#define pli pair<ll, int>
#define mp make_pair

int n, q;

ll seg[maxn*4]; //a max seg tree

//we want the seg-tree to go in euler tour order
int qus[maxn];

ll ans[maxn]; //store ans for each value
ll dep[maxn]; //distance from root to me
int par[maxn];

int rt; //some global root variable
ll esum = 0LL; //total edge sum
//barebones dfs
void dfs(int u, int p = -1) {
if (p == -1) {
dep[u] = 0LL;
par[u] = -1;
}
for (pil vp : adj[u]) {
if (vp.first == p) continue;
dep[vp.first] = dep[u] + vp.second.first; //dep is length to bot
par[vp.first] = u;
dfs(vp.first, u);
}
}

void dfs1(int u, ll msum = 0LL) {
ans[1] = min(ans[1], esum - msum);
for (pil vp : adj[u]) {
if (vp.first != par[u]) {
dfs1(vp.first, msum - vp.second.second +
vp.second.first);
}
}
}

void go1() {
//finds the answer for 1 by itself
//when I go to a child, I reverse that edge
ans[1] = esum;
ll csum = 0LL;
for (int i = 1; i <= n; i++) {
if (i != rt) csum += plink[i];
}
dfs1(rt, csum);
}

pli mdepth[maxn]; //want maxdepth

pii cg;

void dfs2(int u, ll msum) {
//msum is the sum of everything in
//consider me to be an lca
mdepth[u] = {dep[u], u};
vector<pli> ops;

for (pil vp : adj[u]) {
if (vp.first == par[u]) continue;
dfs2(vp.first, msum - vp.second.second);
ops.push_back(mdepth[vp.first]);
}

if (ops.size()) mdepth[u] = ops[0];
sort(ops.begin(), ops.end());
reverse(ops.begin(), ops.end());
if (ops.size() < 2) return;
msum += ops[0].first + ops[1].first - dep[u];
if (esum - msum < ans[2]) {
ans[2] = esum - msum;
cg = mp(ops[0].second, ops[1].second);
}
}

pii go2() {
//we  consider everything as the lca
//then we sacrifice a certain amount that "goes down"
ans[2] = esum;
//   we lose some of the par-links
ll csum = 0LL;
for (int i = 1; i <= n; i++) {
if (i != rt) csum += plink[i];
}
dfs2(rt, csum);
return cg;
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
int a, b;
ll c, d;
for (int i = 0; i < n-1; i++) {
cin >> a >> b >> c >> d;
esum += c;
esum += d;
}
cin >> q;
for (int i = 1; i <= q; i++) {
cin >> qus[i];
}
if (n == 2) {
//just bash
for (int i = 1; i <= q; i++) {
if (qus[i] == 2) {
cout << 0 << endl;
}
else {
}
}
return 0;
}

//now we want to root at a non-leaf
rt = 1;
for (int i = 2; i <= n; i++) {
if (adj[i].size() != 1) rt = i;
}
dfs(rt);

go1();
pii vp = go2();

//now we are just printing out answer (for now - 1/2)
for (int i = 1; i <= q; i++) {
cout << ans[qus[i]] << '\n';
}
cout.flush();
}

//use a dp to calculate the answer for two (root at non-leaf)
//greedily add nodes until we get to each val (if none left - do nothing)
```

### Compilation message

```designated_cities.cpp: In function 'int main()':
designated_cities.cpp:145:7: warning: variable 'vp' set but not used [-Wunused-but-set-variable]
pii vp = go2();
^~```

#### Subtask #1 0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

#### Subtask #2 7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 422 ms 25212 KB Output is correct
3 Correct 531 ms 33872 KB Output is correct
4 Correct 435 ms 25212 KB Output is correct
5 Correct 390 ms 26468 KB Output is correct
6 Correct 453 ms 27156 KB Output is correct
7 Correct 299 ms 27684 KB Output is correct
8 Correct 465 ms 35788 KB Output is correct
9 Correct 295 ms 30364 KB Output is correct

#### Subtask #3 0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4992 KB Output is correct
2 Incorrect 448 ms 25192 KB Output isn't correct
3 Halted 0 ms 0 KB -

#### Subtask #4 0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

#### Subtask #5 0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 422 ms 25212 KB Output is correct
3 Correct 531 ms 33872 KB Output is correct
4 Correct 435 ms 25212 KB Output is correct
5 Correct 390 ms 26468 KB Output is correct
6 Correct 453 ms 27156 KB Output is correct
7 Correct 299 ms 27684 KB Output is correct
8 Correct 465 ms 35788 KB Output is correct
9 Correct 295 ms 30364 KB Output is correct
10 Correct 5 ms 4992 KB Output is correct
11 Incorrect 448 ms 25192 KB Output isn't correct
12 Halted 0 ms 0 KB -

#### Subtask #6 0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -