Submission #223986

#	Time	Username	Problem	Language	Result	Execution time	Memory
223986		osaaateiasavtnl	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	529 ms	59112 KiB

designated_cities

#include<bits/stdc++.h>
using namespace std;
 
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
 
const int N = 2e5 + 7;
const ll INF = 1e18;
int n;
vector <ii> g[N];
vector <ii> tree[N];
void build(int u, int p) {  
    tree[u].clear();
    for (auto e : g[u]) {
        int v = e.f, c = e.s;
        if (v != p) {
            tree[u].app(mp(v, c));
            build(v, u);
        }       
    }   
}
int to[N];
ll h[N];
void ladder(int u, ll cur, ll &sum) {
    h[u] = cur;
    to[u] = -1;
    for (auto e : tree[u]) {
        ladder(e.f, cur + e.s, sum);
        sum += e.s;
        h[u] = max(h[u], h[e.f]);
        if (to[u] == -1 || h[to[u]] < h[e.f])
            to[u] = e.f;
    }   
}   
void print(int u, int ded, ll cur, vector <pair <ll, int> > &a, bool root) {
    if (tree[u].empty())
        a.app(mp(cur, ded));
    else
        a.app(mp(0, ded));
                    
    for (auto e : tree[u]) {
        int d = ded;
        if (root) 
            d = e.f;
 
        ll c = cur;
        if (to[u] != e.f)
            c = 0;
        c += e.s;            
 
        print(e.f, d, c, a, 0);
    }   
}   
 
ll ans[N];
vector <pair <ll, int> > a;
void solve(int c) {    
    build(c, c);
    ll sum = 0;
    ladder(c, 0, sum);
    a.clear();
    print(c, c, 0, a, 1);
    sort(all(a)); reverse(all(a));
 
    ans[1] = min(ans[1], sum);
 
    int l = -1;
    for (int i = 1; i < a.size(); ++i) {
        if (a[i].s != a[0].s) {
            l = i;
            break;
        }   
    }   
    sum -= a[0].f;
    for (int i = 1; i < a.size(); ++i) {
        sum -= a[i].f;
        if (l <= i) {
            ans[i + 1] = min(ans[i + 1], sum);
        }       
        else {
            ans[i + 1] = min(ans[i + 1], sum + a[i].f - a[l].f);
        }   
    }   
}
 
namespace Root {
ll sum[N];
void dfs1(int u, int p) {
    for (auto e : g[u]) {
        int v = e.f, c = e.s;
        if (v != p) {
            dfs1(v, u);
            sum[u] += sum[v] + c;
        }   
    }   
}   
ll diam = INF;
int root = 1;
pair <ll, int> h[N];
void dfs2(int u, int p, ll up) {
    for (auto e : g[u]) {
        int v = e.f, c = e.s;
        if (v == p) {
            up += c;
        }   
    }   
    ans[1] = min(ans[1], up + sum[u]);
    h[u] = mp(0, u);
    for (auto e : g[u]) {
        int v = e.f, c = e.s;
        if (v != p) {
            dfs2(v, u, up + sum[u] - sum[v] - c);
            auto t = h[v];
            t.f += c;
                        
            ll nn = up + sum[u] - h[u].f - t.f;
            if (nn < diam) {
                diam = nn;
                root = t.s;
            }   

            h[u] = max(h[u], t);
        }   
    }   
}
int getroot() {
    dfs1(1, 1);
    dfs2(1, 1, 0);
    return root;
} 
};
 
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        g[u].app(mp(v, a));
        g[v].app(mp(u, b));
    }   
    for (int i = 0; i < N; ++i)
        ans[i] = INF;
 
    int root = Root::getroot();    
    solve(root);

    #ifdef HOME
    cout << "root " << root << endl;
    #endif
       
    int q;
    cin >> q;
    while (q--) {
        int k;
        cin >> k;
        cout << ans[k] << endl;
    }   
    
    #ifdef HOME
    cerr << Time << endl;
    #endif
}

Compilation message (stderr)

designated_cities.cpp: In function 'void solve(int)':
designated_cities.cpp:75:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < a.size(); ++i) {
                     ~~^~~~~~~~~~
designated_cities.cpp:82:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < a.size(); ++i) {
                     ~~^~~~~~~~~~

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