oj.uz

답안 #223875

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
223875 2020-04-16T19:24:29 Z osaaateiasavtnl Designated Cities (JOI19_designated_cities) C++14
7 / 100
 353 ms 34040 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int N = 2e5 + 7;
vector <ii> g[N];
int sum[N];
void dfs1(int u, int p) {
    for (auto e : g[u]) {
        int v = e.f, c = e.s;
        if (v != p) {
            dfs1(v, u);
            sum[u] += sum[v] + c;
        }   
    }   
}   
const int INF = 1e18;
int ans = INF;
void dfs2(int u, int p, int up) {
    for (auto e : g[u]) {
        int v = e.f, c = e.s;
        if (v == p) {
            up += c;
        }   
    }   
    ans = min(ans, up + sum[u]);
    for (auto e : g[u]) {
        int v = e.f, c = e.s;
        if (v != p) {
            dfs2(v, u, up + sum[u] - sum[v] - c);
        }   
    }   
}   

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        g[u].app(mp(v, a));
        g[v].app(mp(u, b));
    }   
    dfs1(1, 1);
    dfs2(1, 1, 0);
    cout << ans << endl;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 228 ms 23288 KB Output is correct
3 Correct 351 ms 33784 KB Output is correct
4 Correct 208 ms 21752 KB Output is correct
5 Correct 214 ms 23148 KB Output is correct
6 Correct 281 ms 24952 KB Output is correct
7 Correct 227 ms 22632 KB Output is correct
8 Correct 353 ms 34040 KB Output is correct
9 Correct 150 ms 21020 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 228 ms 23288 KB Output is correct
3 Correct 351 ms 33784 KB Output is correct
4 Correct 208 ms 21752 KB Output is correct
5 Correct 214 ms 23148 KB Output is correct
6 Correct 281 ms 24952 KB Output is correct
7 Correct 227 ms 22632 KB Output is correct
8 Correct 353 ms 34040 KB Output is correct
9 Correct 150 ms 21020 KB Output is correct
10 Incorrect 7 ms 4992 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -