Submission #592279

#	Time	Username	Problem	Language	Result	Execution time	Memory
592279		Lobo	Designated Cities (JOI19_designated_cities)	C++17	23 / 100	2073 ms	35892 KiB

designated_cities

#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 2e5+10;

int n, q, comp[maxn], mark[maxn], ans[maxn], pai[maxn];
pair<int,int> dp[maxn];
vector<pair<pair<int,int>,pair<int,int>>> edg;
vector<int> vert, g[maxn];

int dfsdeep(int u, int ant, int val) {
    vert.pb(u);
    pai[u] = ant;
    dp[u] = mp(val,u);
    int up = 0;
    for(auto id : g[u]) {
        int v = u^edg[id].fr.fr^edg[id].fr.sc;
        if(v == ant) continue;
        int w;
        if(edg[id].fr.fr == u) w = edg[id].sc.fr;
        else w = edg[id].sc.sc;
        if(ant == 0) 
            comp[v] = v;
        else
            comp[v] = comp[u];
        up+= edg[id].sc.fr+edg[id].sc.sc-w;
        up+= dfsdeep(v,u,w);
        dp[u] = max(dp[u],mp(dp[v].fr+val,dp[v].sc));
    }
    return up;
}

void sol(int rt) {
    vert.clear();
    int up = dfsdeep(rt,0,0);
    vector<pair<int,int>> deeps;
    //pego eu mesmo e os melhores dos outros
    for(auto v : vert) {
        mark[v] = 0;
        deeps.pb(mp(dp[v].fr,v));
    }
    sort(all(deeps),greater<pair<int,int>>());

    int qtdc = 1;
    int ans1 = up;
    ans[1] = max(ans[1],ans1);
    for(auto X : deeps) {
        int v = X.sc;
        if(mark[v]) continue;
        ans1+= dp[v].fr;
        qtdc++;
        ans[qtdc] = max(ans[qtdc],ans1);
        v = dp[v].sc;
        // cout << v << " " << X.fr << endl;

        while(v != 0 && mark[v] == 0) {
            mark[v] = 1;
            v = pai[v];
        }
    }

    //obriga a escolher de subs diferentes
    ans1 = up;
    qtdc = 2;
    for(auto v : vert) {
        mark[v] = 0;
    }
    int v1 = dp[rt].sc;
    ans1+= dp[rt].fr;
    int comp1 = comp[v1];
    while(v1 != 0 && mark[v1] == 0) {
        mark[v1] = 1;
        v1 = pai[v1];
    }

    for(auto X : deeps) {
        int v = X.sc;
        if(mark[v] || comp[dp[v].sc] == comp1) continue;
        ans1+= dp[v].fr;
        qtdc++;
        ans[qtdc] = max(ans[qtdc],ans1);
        v = dp[v].sc;
        // cout << v << " " << X.fr << endl;

        while(v != 0 && mark[v] == 0) {
            mark[v] = 1;
            v = pai[v];
        }
        break;
    }
    
    for(auto X : deeps) {
        int v = X.sc;
        if(mark[v]) continue;
        ans1+= dp[v].fr;
        qtdc++;
        ans[qtdc] = max(ans[qtdc],ans1);
        v = dp[v].sc;
        // cout << v << " " << X.fr << endl;

        while(v != 0 && mark[v] == 0) {
            mark[v] = 1;
            v = pai[v];
        }
    }

}

void solve() {
    cin >> n;
    for(int i = 0; i < n-1; i++) {
        int u,v,w1,w2;
        cin >> u >> v >> w1 >> w2;
        g[u].pb(i);
        g[v].pb(i);
        ans[0]+= w1+w2;
        edg.pb(mp(mp(u,v),mp(w1,w2)));
    }

    for(int i = 1; i <= n; i++) {
        sol(i);
    }
    for(int i = 2; i <= n; i++) {
        ans[i] = max(ans[i],ans[i-1]);
    }

    cin >> q;
    while(q--) {
        int x; cin >> x;
        cout << ans[0]-ans[x] << endl;
    }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

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