oj.uz

Submission #1030736

# Submission time Handle Problem Language Result Execution time Memory
1030736 2024-07-22T09:18:08 Z 변재우(#10959) Designated Cities (JOI19_designated_cities) C++17
7 / 100
 127 ms 32848 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int Nmax=200010;
int N, Q, tot, ans, sum, P[Nmax];
vector<pair<int, pair<int, int>>> adj[Nmax];

void DFS(int curr, int prev) {
    for(auto [next, w]:adj[curr]) if(next!=prev) P[next]=curr, DFS(next, curr);
}

void DFS2(int curr, int prev, int val) {
    ans=max(ans, val);
    for(auto [next, w]:adj[curr]) if(next!=prev) DFS2(next, curr, val-w.second+w.first);
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N;
    for(int i=1; i<N; i++) {
        int u, v, a, b; cin>>u>>v>>a>>b;
        tot+=a+b;
        adj[u].push_back({v, {a, b}}), adj[v].push_back({u, {b, a}});
    }
    DFS(1, 0);
    for(int i=1; i<=N; i++) {
        for(auto [j, w]:adj[i]) if(P[i]==j) sum+=w.first;
    }
    DFS2(1, 0, sum);
    cout<<tot-ans;
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4956 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 1 ms 4956 KB Output is correct
2 Correct 99 ms 24688 KB Output is correct
3 Correct 127 ms 32596 KB Output is correct
4 Correct 113 ms 23860 KB Output is correct
5 Correct 92 ms 24584 KB Output is correct
6 Correct 98 ms 26044 KB Output is correct
7 Correct 96 ms 24064 KB Output is correct
8 Correct 118 ms 32848 KB Output is correct
9 Correct 69 ms 23792 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 99 ms 24688 KB Output is correct
3 Correct 127 ms 32596 KB Output is correct
4 Correct 113 ms 23860 KB Output is correct
5 Correct 92 ms 24584 KB Output is correct
6 Correct 98 ms 26044 KB Output is correct
7 Correct 96 ms 24064 KB Output is correct
8 Correct 118 ms 32848 KB Output is correct
9 Correct 69 ms 23792 KB Output is correct
10 Incorrect 2 ms 4956 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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