oj.uz

Submission #384804

# Submission time Handle Problem Language Result Execution time Memory
384804 2021-04-02T10:02:40 Z kostia244 Designated Cities (JOI19_designated_cities) C++17
7 / 100
 301 ms 35444 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 12;
int n, cst[2*maxn];
ll edgesum = 0;
vector<array<int, 2>> g[maxn];

ll sub[maxn];
void sub_cost(int v, int p) {
    for(auto [i, id] : g[v]) if(i != p) {
        sub_cost(i, v);
        sub[v] += sub[i] + cst[id];
    }
}
ll arb[maxn];
void reroot_cost(int v, int p, ll sum) {
    arb[v] = sum;
    for(auto [i, id] : g[v]) if(i!=p) {
        reroot_cost(i, v, sum-cst[id]+cst[id^1]);
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int f, t, x, y, i = 1; i < n; i++) {
        cin >> f >> t >> cst[2*i-1] >> cst[2*i-2];
        edgesum += cst[2*i-1];
        edgesum += cst[2*i-2];
        g[f].push_back({t, 2*i-2});
        g[t].push_back({f, 2*i-1});
    }
    sub_cost(1, 0);
    reroot_cost(1, 0, sub[1]);
    int q;
    cin >> q;
    for(int t; q--;) {
        cin >> t;
        if(t == 1) {
            cout << edgesum-*max_element(arb+1, arb+n+1) << '\n';
        }
    }
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:26:19: warning: unused variable 'x' [-Wunused-variable]
   26 |     for(int f, t, x, y, i = 1; i < n; i++) {
      |                   ^
designated_cities.cpp:26:22: warning: unused variable 'y' [-Wunused-variable]
   26 |     for(int f, t, x, y, i = 1; i < n; i++) {
      |                      ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 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 5 ms 5100 KB Output is correct
2 Correct 245 ms 20032 KB Output is correct
3 Correct 277 ms 35344 KB Output is correct
4 Correct 234 ms 21996 KB Output is correct
5 Correct 235 ms 23524 KB Output is correct
6 Correct 259 ms 25304 KB Output is correct
7 Correct 214 ms 23560 KB Output is correct
8 Correct 301 ms 35444 KB Output is correct
9 Correct 160 ms 22492 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 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 5 ms 5100 KB Output is correct
2 Correct 245 ms 20032 KB Output is correct
3 Correct 277 ms 35344 KB Output is correct
4 Correct 234 ms 21996 KB Output is correct
5 Correct 235 ms 23524 KB Output is correct
6 Correct 259 ms 25304 KB Output is correct
7 Correct 214 ms 23560 KB Output is correct
8 Correct 301 ms 35444 KB Output is correct
9 Correct 160 ms 22492 KB Output is correct
10 Incorrect 4 ms 5100 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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