oj.uz

답안 #834791

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
834791 2023-08-22T19:31:45 Z Ozy Designated Cities (JOI19_designated_cities) C++17
0 / 100
 153 ms 26080 KB 
    #include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,b) for(int i = (a); i <= (b); i++)
    #define repa(i,a,b) for(int i = (a); i >= (b); i--)
    #define lli long long int
    #define debug(a) cout << #a << " = " << a << endl
    #define debugsl(a) cout << #a << " = " << a << ", "
     
    #define MAX 200000
     
    struct x {
        lli des;
        lli w;
        lli comp;
    };
     
    lli n,a,b,c,d,raiz,op,total,q;
    vector<x> hijos[MAX+2];
    lli sub[MAX+2],h_op[MAX+2];
     
    void pre_dfs(lli pos, lli padre) {
        for(auto h : hijos[pos]) {
            if(h.des == padre) continue;
            pre_dfs(h.des,pos);
            sub[pos] += sub[h.des] + (h.comp-h.w);
        }
    }
     
    void busca_raiz(lli pos, lli padre,lli carga) {
        lli a;
        vector<lli> mejores;
     
        for(auto h : hijos[pos]){
            if(h.des == padre) continue;
            a = carga + sub[pos] - sub[h.des];
            a -= (h.comp-h.w);
            a += h.w;
            busca_raiz(h.des,pos,a);
            
            mejores.push_back(h_op[h.des]+h.w);
        }
        sort(mejores.begin(), mejores.end());
        reverse(mejores.begin(), mejores.end());

        lli cont = 0;
        a = carga + sub[pos];
        for(auto m : mejores) {
            if (cont == 2) break;
            cont++;
            a += m;
        }

        op = max(a,op);
    }
     
    int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
     
        cin >> n;
        rep(i,1,n-1) {
            cin >> a >> b >> c >> d;
            hijos[a].push_back({b,c,c+d});
            hijos[b].push_back({a,d,c+d});
            total += (c+d);
        }
     
        pre_dfs(1,0);
        busca_raiz(1,0,0);
     
        cin >> q >> a;
        cout << (total-op);
     
        return 0;  
    }

Subtask #1
0 / 6.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 153 ms 26080 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

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

Subtask #6
0 / 44.0

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