제출 #303643

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
303643		nickmet2004	Designated Cities (JOI19_designated_cities)	C++11	13 / 100	487 ms	32548 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 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]++;
    }
    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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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