oj.uz

답안 #223975

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
223975 2020-04-16T23:28:11 Z osaaateiasavtnl Designated Cities (JOI19_designated_cities) C++14
0 / 100
 330 ms 30172 KB 
#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 {
int 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 ans = INF;
int root = -1;
void dfs2(int u, int p, int up) {
    for (auto e : g[u]) {
        int v = e.f, c = e.s;
        if (v == p) {
            up += c;
        }   
    }   
    if (up + sum[u] < ans) {
        ans = up + sum[u];
        root = 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);
        }   
    }   
}
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);
            
    int q;
    cin >> q;
    while (q--) {
        int k;
        cin >> k;
        cout << ans[k] << endl;
    }   
    
    #ifdef HOME
    cerr << Time << endl;
    #endif
}

Compilation message

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
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 11264 KB Output is correct
2 Incorrect 10 ms 11392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 11264 KB Output is correct
2 Incorrect 330 ms 30160 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 11392 KB Output is correct
2 Incorrect 296 ms 30172 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 11264 KB Output is correct
2 Incorrect 10 ms 11392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 11264 KB Output is correct
2 Incorrect 330 ms 30160 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 11264 KB Output is correct
2 Incorrect 10 ms 11392 KB Output isn't correct
3 Halted 0 ms 0 KB -