oj.uz

Submission #223957

# Submission time Handle Problem Language Result Execution time Memory
223957 2020-04-16T22:32:08 Z osaaateiasavtnl Designated Cities (JOI19_designated_cities) C++14
23 / 100
 2000 ms 70032 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#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, 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);
}   
int 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, int 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], h[N];
void ladder(int u, int cur, int &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, int cur, vector <ii> &a, bool root) {
    //cout << "print " << u << ' ' << ded << ' ' << cur << endl;

    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;

        int c = cur;
        if (to[u] != e.f)
            c = 0;
        c += e.s;            

        print(e.f, d, c, a, 0);
    }   
}   

int ans[N];
void solve(int c) {
    
    //cout << "solve " << c << endl;
    //cout << out[c] << endl;
    
    build(c, c);
    int sum = 0;
    ladder(c, 0, sum);
    vector <ii> 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;
        }   
    }   
    /*
    cout << "sum " << sum << endl;
    cout << "a : ";
    for (auto e : a)
        cout << e.f << "," << e.s << ' ';
    cout << endl;            
    */
    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]);

                //cout << "t " << t << ", c " << c << endl;

                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;
    }   
}

Compilation message

designated_cities.cpp: In function 'void calc(long long int, long long int)':
designated_cities.cpp:24:22: warning: unused variable 'c' [-Wunused-variable]
         int v = e.f, c = e.s;
                      ^
designated_cities.cpp: In function 'void add_out(long long int, long long int, long long int)':
designated_cities.cpp:59:22: warning: unused variable 'c' [-Wunused-variable]
         int v = e.f, c = e.s;
                      ^
designated_cities.cpp: In function 'void solve(long long int)':
designated_cities.cpp:127:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < a.size(); ++i) {
                     ~~^~~~~~~~~~
designated_cities.cpp:141:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < a.size(); ++i) {
                     ~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11520 KB Output is correct
2 Correct 11 ms 11520 KB Output is correct
3 Correct 10 ms 11520 KB Output is correct
4 Correct 12 ms 11520 KB Output is correct
5 Correct 12 ms 11520 KB Output is correct
6 Correct 10 ms 11520 KB Output is correct
7 Correct 11 ms 11520 KB Output is correct
8 Correct 12 ms 11520 KB Output is correct
9 Correct 12 ms 11520 KB Output is correct
10 Correct 11 ms 11520 KB Output is correct
11 Correct 11 ms 11520 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11520 KB Output is correct
2 Execution timed out 2068 ms 69896 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11520 KB Output is correct
2 Execution timed out 2079 ms 70032 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11520 KB Output is correct
2 Correct 11 ms 11520 KB Output is correct
3 Correct 10 ms 11520 KB Output is correct
4 Correct 12 ms 11520 KB Output is correct
5 Correct 12 ms 11520 KB Output is correct
6 Correct 10 ms 11520 KB Output is correct
7 Correct 11 ms 11520 KB Output is correct
8 Correct 12 ms 11520 KB Output is correct
9 Correct 12 ms 11520 KB Output is correct
10 Correct 11 ms 11520 KB Output is correct
11 Correct 11 ms 11520 KB Output is correct
12 Correct 12 ms 11520 KB Output is correct
13 Correct 18 ms 12212 KB Output is correct
14 Correct 18 ms 12288 KB Output is correct
15 Correct 18 ms 12160 KB Output is correct
16 Correct 22 ms 12160 KB Output is correct
17 Correct 16 ms 12160 KB Output is correct
18 Correct 19 ms 12160 KB Output is correct
19 Correct 18 ms 12160 KB Output is correct
20 Correct 17 ms 12160 KB Output is correct
21 Correct 17 ms 12160 KB Output is correct
22 Correct 18 ms 12160 KB Output is correct
23 Correct 19 ms 12160 KB Output is correct
24 Correct 15 ms 12160 KB Output is correct
25 Correct 21 ms 12288 KB Output is correct
26 Correct 17 ms 12160 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11520 KB Output is correct
2 Execution timed out 2068 ms 69896 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11520 KB Output is correct
2 Correct 11 ms 11520 KB Output is correct
3 Correct 10 ms 11520 KB Output is correct
4 Correct 12 ms 11520 KB Output is correct
5 Correct 12 ms 11520 KB Output is correct
6 Correct 10 ms 11520 KB Output is correct
7 Correct 11 ms 11520 KB Output is correct
8 Correct 12 ms 11520 KB Output is correct
9 Correct 12 ms 11520 KB Output is correct
10 Correct 11 ms 11520 KB Output is correct
11 Correct 11 ms 11520 KB Output is correct
12 Correct 11 ms 11520 KB Output is correct
13 Execution timed out 2068 ms 69896 KB Time limit exceeded
14 Halted 0 ms 0 KB -