oj.uz

Submission #592242

# Submission time Handle Problem Language Result Execution time Memory
592242 2022-07-08T19:25:21 Z Lobo Designated Cities (JOI19_designated_cities) C++17
0 / 100
 2000 ms 42276 KB 
#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) {
    vert.pb(u);
    pai[u] = ant;
    dp[u] = mp(0,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);
        dp[u] = max(dp[u],mp(dp[v].fr+w,dp[v].sc));
    }
    return up;
}

void sol(int rt) {
    vert.clear();
    int up = dfsdeep(rt,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;
        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);
    }

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Incorrect 3 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 2083 ms 42168 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Incorrect 3 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

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

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Incorrect 3 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -