Submission #303565

#	Time	Username	Problem	Language	Result	Execution time	Memory
303565		nickmet2004	Designated Cities (JOI19_designated_cities)	C++11	13 / 100	527 ms	35044 KiB

designated_cities

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;

typedef pair<int, int> ipair;
const int N = 2e5 + 5;
int n , q ,A[N] , B[N] , C[N] , D[N];
ll dpD[N] , dpU[N] , cnt[N] ,was[N] , ans[N];
vector<ipair> adj[N];
void dfsD(int u = 1, int p = 0){
    for(ipair X : adj[u]){
        int v = X.f , id = X.s;
        if(v==p) continue;
        dfsD(v , u);
        int W = 0; if(A[id] == u) W = C[id]; else W = D[id];
        dpD[u] += dpD[v] + W;
    }
}
void dfsU(int u = 1 , int p = 0){
    for(ipair X : adj[u]){
        int v = X.f , id = X.s;
        if(v==p) continue;
        dpU[v] += dpU[u];
        int W = 0; if(A[id] == v) W = C[id]; else W = D[id];
        int E = 0; if(C[id] == W) E = D[id]; else E = C[id];
        dpU[v] += dpD[u] - (dpD[v] + E) + W;
        dfsU(v , u);
    }
}
ipair Find(int u){
    for(ipair X : adj[u]){
        int W = 0; if(A[X.s] == X.f) W = C[X.s]; else W = D[X.s];
        if(!was[X.f]) return {X.f , W};
    }
}
int main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i = 1; i < n; ++i){
        cin >> A[i] >> B[i] >> C[i] >> D[i];
        adj[A[i]].emplace_back(B[i] , i); adj[B[i]].emplace_back(A[i] , i);
        cnt[A[i]]++; cnt[B[i]]++;
    }
    dfsD(); dfsU();
    //cout << ans[1] << " ans 1" << endl;
    ans[1] = 1e18;
    for(int i = 1; i <= n; ++i) ans[1] = min(ans[1] , dpD[i] + dpU[i]);
    set<pair<ll , int>> D;
    for(int i = 1; i <= n; ++i) if(cnt[i]==1) D.insert({Find(i).s , i});
    while(D.size() > 2){
        int u = D.begin()->s , w = D.begin()->f;
        D.erase(D.begin());
        was[u] = 1;
        int p = Find(u).f;
        --cnt[p];
        if(cnt[p] == 1){
            int x = Find(p).s;
            D.insert({w + x ,p});
        } else ans[D.size()] = ans[D.size() + 1] + w;
    }
    //for(int i = 1; i <= n; ++i) cout << dpD[i] << " "; cerr << endl;
    //for(int i = 1; i <= n; ++i) cout << dpU[i] << " "; cerr << endl;
    int q;
    cin >> q;
    while(q--){
        int k; cin >> k;
        cout << ans[k] << endl;
    }
return 0;
}

Compilation message (stderr)

designated_cities.cpp: In function 'ipair Find(int)':
designated_cities.cpp:37:1: warning: control reaches end of non-void function [-Wreturn-type]
   37 | }
      | ^

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44