Submission #834791

#	Time	Username	Problem	Language	Result	Execution time	Memory
834791		Ozy	Designated Cities (JOI19_designated_cities)	C++17	0 / 100	153 ms	26080 KiB

designated_cities

    #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
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44