Submission #303583

#	Time	Username	Problem	Language	Result	Execution time	Memory
303583		nickmet2004	Designated Cities (JOI19_designated_cities)	C++11	0 / 100	444 ms	23800 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 , B , C , D;
ll dpD[N] , dpU[N] , cnt[N] ,was[N] , ans[N] ,dp[N];
struct Edge{
    int v , c, d;
    Edge(int v , int c , int d){this->v =v; this->c= c; this->d= d;}
};
int sumc , sum ;
vector<Edge> adj[N];
void dfs (int u = 1, int p = 0) {
	for (auto x : adj[u])
		if (x.v != p) {
			dp[x.v] = dp[u] + x.c - x.d;
			dfs(x.v, u);
			sumc += x.d;
		}
}
void dfsD(int u = 1, int p = 0){
    for(Edge X : adj[u]){
        int v = X.v;
        if(v==p) continue;
        dfsD(v , u);
        dpD[u] += dpD[v] + X.c;
    }
}
void dfsU(int u = 1 , int p = 0){
    for(Edge X : adj[u]){
        int v = X.v;
        if(v==p) continue;
        dpU[v] += dpU[u];
        dpU[v] += dpD[u] - (dpD[v] + X.c) + X.d;
        dfsU(v , u);
    }
}
ipair Find(int u){
    for(auto X : adj[u])if(!was[X.v]) return {X.v , X.d};
}
int main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i = 1; i < n; ++i){
        cin >> A >> B >> C >> D;
        adj[A].emplace_back(Edge(B , C , D)); adj[B].emplace_back(Edge(A , D , C));
        cnt[A]++; cnt[B]++;
        sum  += C; sum += D;
    }
   // dfsD();
    //dfsU();
    dfs();
    ans[1] = sum - (sumc + *max_element(dp + 1 , dp + 1 + n));
    //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:44:1: warning: control reaches end of non-void function [-Wreturn-type]
   44 | }
      | ^

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