Submission #223968

#	Time	Username	Problem	Language	Result	Execution time	Memory
223968		osaaateiasavtnl	Designated Cities (JOI19_designated_cities)	C++14	23 / 100	2080 ms	59056 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 LG = 20, N = 2e5 + 7;
const ll INF = 1e18;
vector <ii> g[N];
int n;
bool used[N], centr[N];
 
int cnt[N];
void calc(int u, int p) {
    cnt[u] = 1;
    used[u] = 1;
    for (auto e : g[u]) {
        int v = e.f, c = e.s;
        if (v != p && !centr[v]) {
            calc(v, u);
            cnt[u] += cnt[v];
        }   
    }   
}   
int get(int u, int p, int all) {
    int mx = -1;
    for (auto e : g[u]) {
        int v = e.f;
        if (v != p && !centr[v]) {
            if (mx == -1 || cnt[mx] < cnt[v])
                mx = v;
        }   
    }   
    if (mx == -1 || cnt[mx] * 2 <= all)
        return u;
    else
        return get(mx, u, all);
}   
ll out[N], sum[N];
void calc_sum(int u, int p) {
    sum[u] = 0;
    for (auto e : g[u]) {
        int v = e.f, c = e.s;
        if (v != p && !centr[v]) {
            calc_sum(v, u);
            sum[u] += sum[v] + c;
        }   
    }   
}   
void add_out(int u, int p, ll x) {
    out[u] += x;
    for (auto e : g[u]) {
        int v = e.f, c = e.s;
        if (v != p && !centr[v]) {
            add_out(v, u, x);
        }   
    }   
}
 
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 && !centr[v]) {
            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];
void solve(int c) {    
    build(c, c);
    ll sum = 0;
    ladder(c, 0, sum);
    vector <pair <ll, int> > a;
    print(c, c, 0, a, 1);
    sort(all(a)); reverse(all(a));
 
    ans[1] = min(ans[1], out[c] + 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], out[c] + sum);
        }       
        else {
            ans[i + 1] = min(ans[i + 1], out[c] + sum + a[i].f - a[l].f);
        }   
    }   
}
 
map <ii, int> d;
int edge(int u, int v) {
    return d[mp(u, v)];
}
 
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));
        d[mp(u,v)] = a;
        d[mp(v,u)] = b;
    }   
    for (int i = 0; i < N; ++i)
        ans[i] = INF;
             
    for (int t = 0; t < LG; ++t) {
        memset(used, 0, sizeof used);
        for (int i = 1; i <= n; ++i) {
            if (!used[i] && !centr[i]) {
 
                calc(i, i);
                int c = get(i, i, cnt[i]);
                solve(c);
                calc_sum(c, c);
                for (auto e : g[c]) {
                    int v = e.f, cost = e.s;
                    if (!centr[v]) {
                        add_out(v, c, sum[c] - sum[v] - cost + edge(v, c));
                    }   
                }   
                centr[c] = 1;
 
            }   
        }   
    }   
    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 calc(int, int)':
designated_cities.cpp:25:22: warning: unused variable 'c' [-Wunused-variable]
         int v = e.f, c = e.s;
                      ^
designated_cities.cpp: In function 'void add_out(int, int, long long int)':
designated_cities.cpp:60:22: warning: unused variable 'c' [-Wunused-variable]
         int v = e.f, c = e.s;
                      ^
designated_cities.cpp: In function 'void solve(int)':
designated_cities.cpp:123:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < a.size(); ++i) {
                     ~~^~~~~~~~~~
designated_cities.cpp:130: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: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 17 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44